Differentiable Initialization-Accelerated CPU-GPU Hybrid Combinatorial Scheduling

• URL: http://arxiv.org/abs/2603.28943v1
• Date: Mon, 30 Mar 2026 19:35:31 GMT
• Title: Differentiable Initialization-Accelerated CPU-GPU Hybrid Combinatorial Scheduling
• Abstract summary: This paper presents a hybrid-GPU framework for solving scheduling problems formulated as Linear Programming (ILP)<n>We introduce a novel approach that combines differentiable optimization with classical ILP. Specifically, we utilize differentiable presolving to rapidly generate high-quality partial solutions, which serve as warm-starts for commercial ILP solvers and rising open-source HiGHS.<n> Empirical results across industry-scale benchmarks demonstrate up to a $10times$ performance gain over baselines, narrowing the optimality gap to $0.1%$.
• Score: 9.29687794194811
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper presents a hybrid CPU-GPU framework for solving combinatorial scheduling problems formulated as Integer Linear Programming (ILP). While scheduling underpins many optimization tasks in computing systems, solving these problems optimally at scale remains a long-standing challenge due to their NP-hard nature. We introduce a novel approach that combines differentiable optimization with classical ILP solving. Specifically, we utilize differentiable presolving to rapidly generate high-quality partial solutions, which serve as warm-starts for commercial ILP solvers (CPLEX, Gurobi) and rising open-source solver HiGHS. This method enables significantly improved early pruning compared to state-of-the-art standalone solvers. Empirical results across industry-scale benchmarks demonstrate up to a $10\times$ performance gain over baselines, narrowing the optimality gap to $<0.1\%$. This work represents the first demonstration of utilizing differentiable optimization to initialize exact ILP solvers for combinatorial scheduling, opening new opportunities to integrate machine learning infrastructure with classical exact optimization methods across broader domains.

Related papers

• Efficient Optimization Accelerator Framework for Multistate Ising Problems [0.0]
  Ising Machines are emerging hardware architectures that efficiently solve NP-Hard optimization problems.<n>We model spin interactions as generalized logic function to significantly reduce the exploration space.<n>We also design 1024-neuron all-to-all connected probabilistic Ising accelerator on FPGA with the proposed approach.
  arXiv  Detail & Related papers  (2025-05-26T17:23:47Z)
• Greedy Restart Schedules: A Baseline for Dynamic Algorithm Selection on Numerical Black-box Optimization Problems [0.0]
  We present a scheduling approach that iteratively selects the algorithm performing best on the distribution of unsolved training problems at time of selection, resulting in a problem-independent solver schedule.<n>We demonstrate our approach using well-knowns from numerical black-box optimization on the BBOB testbed, bridging much of the gap between single and virtual best solver from the original portfolio across various evaluation protocols.
  arXiv  Detail & Related papers  (2025-04-15T17:54:21Z)
• Direct comparison of stochastic driven nonlinear dynamical systems for combinatorial optimization [0.669087470775851]
  Combinatorial optimization problems are ubiquitous in industrial applications.<n>Tremendous effort has been devoted to developing solvers for Ising-type problems over the past decades.<n>Recent advances in controlling and manipulating both quantum and classical systems have enabled novel computing paradigms.
  arXiv  Detail & Related papers  (2025-03-19T17:08:55Z)
• Learning Multiple Initial Solutions to Optimization Problems [52.9380464408756]
  Sequentially solving similar optimization problems under strict runtime constraints is essential for many applications.<n>We propose learning to predict emphmultiple diverse initial solutions given parameters that define the problem instance.<n>We find significant and consistent improvement with our method across all evaluation settings and demonstrate that it efficiently scales with the number of initial solutions required.
  arXiv  Detail & Related papers  (2024-11-04T15:17:19Z)
• Analyzing and Enhancing the Backward-Pass Convergence of Unrolled Optimization [50.38518771642365]
  The integration of constrained optimization models as components in deep networks has led to promising advances on many specialized learning tasks. A central challenge in this setting is backpropagation through the solution of an optimization problem, which often lacks a closed form. This paper provides theoretical insights into the backward pass of unrolled optimization, showing that it is equivalent to the solution of a linear system by a particular iterative method. A system called Folded Optimization is proposed to construct more efficient backpropagation rules from unrolled solver implementations.
  arXiv  Detail & Related papers  (2023-12-28T23:15:18Z)
• Backpropagation of Unrolled Solvers with Folded Optimization [55.04219793298687]
  The integration of constrained optimization models as components in deep networks has led to promising advances on many specialized learning tasks. One typical strategy is algorithm unrolling, which relies on automatic differentiation through the operations of an iterative solver. This paper provides theoretical insights into the backward pass of unrolled optimization, leading to a system for generating efficiently solvable analytical models of backpropagation.
  arXiv  Detail & Related papers  (2023-01-28T01:50:42Z)
• Learning Primal Heuristics for Mixed Integer Programs [5.766851255770718]
  We investigate whether effective primals can be automatically learned via machine learning. We propose a new method to represent an optimization problem as a graph, and train a Graph Conal Network on solved problem instances with known optimal solutions. The prediction of variable solutions is then leveraged by a novel configuration of the B&B method, Probabilistic Branching with guided Depth-first Search.
  arXiv  Detail & Related papers  (2021-07-02T06:46:23Z)
• A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs [91.07247251502564]
  We propose a hybrid approach to combine the best of the two worlds, in which a bi-level framework is developed with an upper-level learning method to optimize the graph. Such a bi-level approach simplifies the learning on the original hard CO and can effectively mitigate the demand for model capacity.
  arXiv  Detail & Related papers  (2021-06-09T09:18:18Z)
• Divide and Learn: A Divide and Conquer Approach for Predict+Optimize [50.03608569227359]
  The predict+optimize problem combines machine learning ofproblem coefficients with a optimization prob-lem that uses the predicted coefficients. We show how to directlyexpress the loss of the optimization problem in terms of thepredicted coefficients as a piece-wise linear function. We propose a novel divide and algorithm to tackle optimization problems without this restriction and predict itscoefficients using the optimization loss.
  arXiv  Detail & Related papers  (2020-12-04T00:26:56Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)
• A General Large Neighborhood Search Framework for Solving Integer Linear Programs [46.62993477453986]
  We focus on solving integer programs, and ground our approach in the large neighborhood search (SLN) paradigm. We show that our LNS framework can significantly outperform compared to state-of-the-art commercial solvers such as Gurobi.
  arXiv  Detail & Related papers  (2020-03-29T23:08:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.