Differentiable Combinatorial Scheduling at Scale

• URL: http://arxiv.org/abs/2406.06593v1
• Date: Thu, 6 Jun 2024 02:09:39 GMT
• Title: Differentiable Combinatorial Scheduling at Scale
• Authors: Mingju Liu, Yingjie Li, Jiaqi Yin, Zhiru Zhang, Cunxi Yu,
• Abstract summary: We propose a differentiable scheduling framework, utilizing Gumbel-Softmax differentiable sampling technique. To encode inequality constraints for scheduling tasks, we introduce textitconstrained Gumbel Trick, which adeptly encodes arbitrary inequality constraints. Our method facilitates an efficient and scalable scheduling via gradient descent without the need for training data.
• Score: 18.09256072039255
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper addresses the complex issue of resource-constrained scheduling, an NP-hard problem that spans critical areas including chip design and high-performance computing. Traditional scheduling methods often stumble over scalability and applicability challenges. We propose a novel approach using a differentiable combinatorial scheduling framework, utilizing Gumbel-Softmax differentiable sampling technique. This new technical allows for a fully differentiable formulation of linear programming (LP) based scheduling, extending its application to a broader range of LP formulations. To encode inequality constraints for scheduling tasks, we introduce \textit{constrained Gumbel Trick}, which adeptly encodes arbitrary inequality constraints. Consequently, our method facilitates an efficient and scalable scheduling via gradient descent without the need for training data. Comparative evaluations on both synthetic and real-world benchmarks highlight our capability to significantly improve the optimization efficiency of scheduling, surpassing state-of-the-art solutions offered by commercial and open-source solvers such as CPLEX, Gurobi, and CP-SAT in the majority of the designs.

Related papers

• Optimization-Driven Adaptive Experimentation [7.948144726705323]
  Real-world experiments involve batched & delayed feedback, non-stationarity, multiple objectives & constraints, and (often some) personalization. Tailoring adaptive methods to address these challenges on a per-problem basis is infeasible, and static designs remain the de facto standard. We present a mathematical programming formulation that can flexibly incorporate a wide range of objectives, constraints, and statistical procedures.
  arXiv  Detail & Related papers  (2024-08-08T16:29:09Z)
• A Penalty-Based Guardrail Algorithm for Non-Decreasing Optimization with Inequality Constraints [1.5498250598583487]
  Traditional mathematical programming solvers require long computational times to solve constrained minimization problems. We propose a penalty-based guardrail algorithm (PGA) to efficiently solve them.
  arXiv  Detail & Related papers  (2024-05-03T10:37:34Z)
• Accelerating Exact Combinatorial Optimization via RL-based Initialization -- A Case Study in Scheduling [1.3053649021965603]
  This research aims to develop an innovative approach that employs machine learning (ML) for addressing optimization problems. We introduce a novel two-phase RL-to-ILP scheduling framework, which includes three steps: 1) solver as coarse-grain scheduler, 2) solution relaxation and 3) exact solving via ILP. Our framework demonstrates the same scheduling performance compared with using exact scheduling methods while achieving up to 128 $times$ speed improvements.
  arXiv  Detail & Related papers  (2023-08-19T15:52:43Z)
• An End-to-End Reinforcement Learning Approach for Job-Shop Scheduling Problems Based on Constraint Programming [5.070542698701157]
  This paper proposes a novel end-to-end approach to solving scheduling problems by means of CP and Reinforcement Learning (RL) Our approach leverages existing CP solvers to train an agent learning a Priority Dispatching Rule (PDR) that generalizes well to large instances, even from separate datasets.
  arXiv  Detail & Related papers  (2023-06-09T08:24:56Z)
• Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets [86.43523688236077]
  Combinatorial optimization (CO) problems are often NP-hard and out of reach for exact algorithms. GFlowNets have emerged as a powerful machinery to efficiently sample from composite unnormalized densities sequentially. In this paper, we design Markov decision processes (MDPs) for different problems and propose to train conditional GFlowNets to sample from the solution space.
  arXiv  Detail & Related papers  (2023-05-26T15:13:09Z)
• A Hierarchical Temporal Planning-Based Approach for Dynamic Hoist Scheduling Problems [11.66506213335498]
  Hoist scheduling has become a bottleneck in electroplating industry applications with the development of autonomous devices. We formulate the hoist scheduling problem as a new temporal planning problem in the form of adapted PDDL. We provide a collection of real-life benchmark instances that can be used to evaluate solution methods for the problem.
  arXiv  Detail & Related papers  (2022-12-11T05:30:44Z)
• Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning [70.65666982566655]
  Permutation flow shop scheduling (PFSS) is widely used in manufacturing systems. We propose to train the model via expert-driven imitation learning, which accelerates convergence more stably and accurately. Our model's network parameters are reduced to only 37% of theirs, and the solution gap of our model towards the expert solutions decreases from 6.8% to 1.3% on average.
  arXiv  Detail & Related papers  (2022-10-31T09:46:26Z)
• 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)
• A Two-stage Framework and Reinforcement Learning-based Optimization Algorithms for Complex Scheduling Problems [54.61091936472494]
  We develop a two-stage framework, in which reinforcement learning (RL) and traditional operations research (OR) algorithms are combined together. The scheduling problem is solved in two stages, including a finite Markov decision process (MDP) and a mixed-integer programming process, respectively. Results show that the proposed algorithms could stably and efficiently obtain satisfactory scheduling schemes for agile Earth observation satellite scheduling problems.
  arXiv  Detail & Related papers  (2021-03-10T03:16:12Z)
• 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)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  We propose two novel conditional gradient-based methods for solving structured convex optimization problems. The most important feature of our framework is that only a subset of the constraints is processed at each iteration. Our algorithms rely on variance reduction and smoothing used in conjunction with conditional gradient steps, and are accompanied by rigorous convergence guarantees.
  arXiv  Detail & Related papers  (2020-07-07T21:26:35Z)

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.