Improvement of Optimization using Learning Based Models in Mixed Integer Linear Programming Tasks

• URL: http://arxiv.org/abs/2506.06291v1
• Date: Sat, 17 May 2025 01:31:53 GMT
• Title: Improvement of Optimization using Learning Based Models in Mixed Integer Linear Programming Tasks
• Authors: Xiaoke Wang, Batuhan Altundas, Zhaoxin Li, Aaron Zhao, Matthew Gombolay,
• Abstract summary: Mixed Linear Programs (MILPs) are essential tools for solving planning and scheduling problems across critical industries such as construction, manufacturing, and logistics.<n>We present a learning-based framework that leverages Behavior Cloning (BC) and Reinforcement Learning (RL) to train Graph Neural Networks (GNNs)<n>Our method reduces optimization time and variance compared to traditional techniques while maintaining solution quality and feasibility.
• Score: 2.1111289252277197
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Mixed Integer Linear Programs (MILPs) are essential tools for solving planning and scheduling problems across critical industries such as construction, manufacturing, and logistics. However, their widespread adoption is limited by long computational times, especially in large-scale, real-time scenarios. To address this, we present a learning-based framework that leverages Behavior Cloning (BC) and Reinforcement Learning (RL) to train Graph Neural Networks (GNNs), producing high-quality initial solutions for warm-starting MILP solvers in Multi-Agent Task Allocation and Scheduling Problems. Experimental results demonstrate that our method reduces optimization time and variance compared to traditional techniques while maintaining solution quality and feasibility.

Related papers

• Efficient End-to-End Learning for Decision-Making: A Meta-Optimization Approach [5.84228364962637]
  We present a meta-optimization method that learns efficient algorithms to approximate optimization problems.<n>We prove exponential convergence, approximation guarantees, and generalization bounds for our learning method.<n>This method offers superior computational efficiency, producing high-quality approximations faster and scaling better with problem size compared to existing techniques.
  arXiv  Detail & Related papers  (2025-05-16T15:27:50Z)
• Offline reinforcement learning for job-shop scheduling problems [1.3927943269211593]
  This paper introduces a novel offline RL method designed for optimization problems with complex constraints.<n>Our approach encodes actions in edge attributes and balances expected rewards with the imitation of expert solutions.<n>We demonstrate the effectiveness of this method on job-shop scheduling and flexible job-shop scheduling benchmarks.
  arXiv  Detail & Related papers  (2024-10-21T07:33:42Z)
• Solving Integrated Process Planning and Scheduling Problem via Graph Neural Network Based Deep Reinforcement Learning [8.497746222687983]
  In this paper, we propose a novel end-to-end Deep Reinforcement Learning (DRL) method for IPPS problem. We model the IPPS problem as a Markov Decision Process (MDP) and employ a Heterogeneous Graph Neural Network (GNN) to capture the complex relationships among operations, machines, and jobs. Experimental results show that, compared to traditional methods, our approach significantly improves solution efficiency and quality in large-scale IPPS instances.
  arXiv  Detail & Related papers  (2024-09-02T06:18:30Z)
• Characterization of Large Language Model Development in the Datacenter [55.9909258342639]
  Large Language Models (LLMs) have presented impressive performance across several transformative tasks. However, it is non-trivial to efficiently utilize large-scale cluster resources to develop LLMs. We present an in-depth characterization study of a six-month LLM development workload trace collected from our GPU datacenter Acme.
  arXiv  Detail & Related papers  (2024-03-12T13:31:14Z)
• Machine Learning Insides OptVerse AI Solver: Design Principles and Applications [74.67495900436728]
  We present a comprehensive study on the integration of machine learning (ML) techniques into Huawei Cloud's OptVerse AI solver. We showcase our methods for generating complex SAT and MILP instances utilizing generative models that mirror multifaceted structures of real-world problem. We detail the incorporation of state-of-the-art parameter tuning algorithms which markedly elevate solver performance.
  arXiv  Detail & Related papers  (2024-01-11T15:02:15Z)
• Taking the human out of decomposition-based optimization via artificial intelligence: Part II. Learning to initialize [0.0]
  The proposed approach can lead to a significant reduction in solution time. Active and supervised learning is used to learn a surrogate model that predicts the computational performance. The results show that the proposed approach can lead to a significant reduction in solution time.
  arXiv  Detail & Related papers  (2023-10-10T23:49:26Z)
• A Multi-Head Ensemble Multi-Task Learning Approach for Dynamical Computation Offloading [62.34538208323411]
  We propose a multi-head ensemble multi-task learning (MEMTL) approach with a shared backbone and multiple prediction heads (PHs) MEMTL outperforms benchmark methods in both the inference accuracy and mean square error without requiring additional training data.
  arXiv  Detail & Related papers  (2023-09-02T11:01:16Z)
• 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)
• 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)
• Large Scale Mask Optimization Via Convolutional Fourier Neural Operator and Litho-Guided Self Training [54.16367467777526]
  We present a Convolutional Neural Operator (CFCF) that can efficiently learn mask tasks. For the first time, our machine learning-based framework outperforms state-of-the-art numerical mask dataset.
  arXiv  Detail & Related papers  (2022-07-08T16:39:31Z)
• 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)

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.