Enhancing Constraint Programming via Supervised Learning for Job Shop Scheduling

• URL: http://arxiv.org/abs/2211.14492v2
• Date: Wed, 12 Apr 2023 07:20:31 GMT
• Title: Enhancing Constraint Programming via Supervised Learning for Job Shop Scheduling
• Authors: Yuan Sun, Su Nguyen, Dhananjay Thiruvady, Xiaodong Li, Andreas T. Ernst and Uwe Aickelin
• Abstract summary: In CP solvers, the variable ordering strategy used to select which variable to explore first has a significant impact on solver effectiveness. We propose a novel variable ordering strategy based on supervised learning, which we evaluate in the context of job shop scheduling problems. Our learning-based methods predict the optimal solution of a problem instance and use the predicted solution to order variables for CP solvers.
• Score: 6.4778725014634615
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Constraint programming (CP) is a powerful technique for solving constraint satisfaction and optimization problems. In CP solvers, the variable ordering strategy used to select which variable to explore first in the solving process has a significant impact on solver effectiveness. To address this issue, we propose a novel variable ordering strategy based on supervised learning, which we evaluate in the context of job shop scheduling problems. Our learning-based methods predict the optimal solution of a problem instance and use the predicted solution to order variables for CP solvers. \added[]{Unlike traditional variable ordering methods, our methods can learn from the characteristics of each problem instance and customize the variable ordering strategy accordingly, leading to improved solver performance.} Our experiments demonstrate that training machine learning models is highly efficient and can achieve high accuracy. Furthermore, our learned variable ordering methods perform competitively when compared to four existing methods. Finally, we demonstrate that hybridising the machine learning-based variable ordering methods with traditional domain-based methods is beneficial.

Related papers

• Self-Evaluation for Job-Shop Scheduling [1.3927943269211593]
  Combinatorial optimization problems, such as scheduling and route planning, are crucial in various industries but are computationally intractable due to their NP-hard nature. We propose a novel framework that generates and evaluates subsets of assignments, moving beyond traditional stepwise approaches.
  arXiv  Detail & Related papers  (2025-02-12T11:22:33Z)
• Learning Joint Models of Prediction and Optimization [56.04498536842065]
  Predict-Then-Then framework uses machine learning models to predict unknown parameters of an optimization problem from features before solving. This paper proposes an alternative method, in which optimal solutions are learned directly from the observable features by joint predictive models.
  arXiv  Detail & Related papers  (2024-09-07T19:52:14Z)
• Take a Step and Reconsider: Sequence Decoding for Self-Improved Neural Combinatorial Optimization [1.1510009152620668]
  We present a simple and problem-independent sequence decoding method for self-improved learning. By modifying the policy to ignore previously sampled sequences, we force it to consider only unseen alternatives. Our method outperforms previous NCO approaches on the Job Shop Scheduling Problem.
  arXiv  Detail & Related papers  (2024-07-24T12:06:09Z)
• Control in Stochastic Environment with Delays: A Model-based Reinforcement Learning Approach [3.130722489512822]
  We introduce a new reinforcement learning method for control problems in environments with delayed feedback. Specifically, our method employs planning, versus previous methods that used deterministic planning. We show that this formulation can recover the optimal policy for problems with deterministic transitions.
  arXiv  Detail & Related papers  (2024-02-01T03:53:56Z)
• Adaptive Robust Learning using Latent Bernoulli Variables [50.223140145910904]
  We present an adaptive approach for learning from corrupted training sets. We identify corrupted non-corrupted samples with latent Bernoulli variables. The resulting problem is solved via variational inference.
  arXiv  Detail & Related papers  (2023-12-01T13:50:15Z)
• Predict-Then-Optimize by Proxy: Learning Joint Models of Prediction and Optimization [59.386153202037086]
  Predict-Then- framework uses machine learning models to predict unknown parameters of an optimization problem from features before solving. This approach can be inefficient and requires handcrafted, problem-specific rules for backpropagation through the optimization step. This paper proposes an alternative method, in which optimal solutions are learned directly from the observable features by predictive models.
  arXiv  Detail & Related papers  (2023-11-22T01:32:06Z)
• Reinforcement Learning Methods for Wordle: A POMDP/Adaptive Control Approach [0.3093890460224435]
  We address the solution of the popular Wordle puzzle, using new reinforcement learning methods. For the Wordle puzzle, they yield on-line solution strategies that are very close to optimal at relatively modest computational cost.
  arXiv  Detail & Related papers  (2022-11-15T03:46:41Z)
• Logistic Q-Learning [87.00813469969167]
  We propose a new reinforcement learning algorithm derived from a regularized linear-programming formulation of optimal control in MDPs. The main feature of our algorithm is a convex loss function for policy evaluation that serves as a theoretically sound alternative to the widely used squared Bellman error.
  arXiv  Detail & Related papers  (2020-10-21T17:14:31Z)
• Learning with Differentiable Perturbed Optimizers [54.351317101356614]
  We propose a systematic method to transform operations into operations that are differentiable and never locally constant. Our approach relies on perturbeds, and can be used readily together with existing solvers. We show how this framework can be connected to a family of losses developed in structured prediction, and give theoretical guarantees for their use in learning tasks.
  arXiv  Detail & Related papers  (2020-02-20T11:11:32Z)
• Model-based Multi-Agent Reinforcement Learning with Cooperative Prioritized Sweeping [4.5497948012757865]
  We present a new model-based reinforcement learning algorithm, Cooperative Prioritized Sweeping. The algorithm allows for sample-efficient learning on large problems by exploiting a factorization to approximate the value function. Our method outperforms the state-of-the-art algorithm sparse cooperative Q-learning algorithm, both on the well-known SysAdmin benchmark and randomized environments.
  arXiv  Detail & Related papers  (2020-01-15T19:13:44Z)
• Hierarchical Variational Imitation Learning of Control Programs [131.7671843857375]
  We propose a variational inference method for imitation learning of a control policy represented by parametrized hierarchical procedures (PHP) Our method discovers the hierarchical structure in a dataset of observation-action traces of teacher demonstrations, by learning an approximate posterior distribution over the latent sequence of procedure calls and terminations. We demonstrate a novel benefit of variational inference in the context of hierarchical imitation learning: in decomposing the policy into simpler procedures, inference can leverage acausal information that is unused by other methods.
  arXiv  Detail & Related papers  (2019-12-29T08:57:02Z)

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.