Learning to Reformulate for Linear Programming

• URL: http://arxiv.org/abs/2201.06216v1
• Date: Mon, 17 Jan 2022 04:58:46 GMT
• Title: Learning to Reformulate for Linear Programming
• Authors: Xijun Li, Qingyu Qu, Fangzhou Zhu, Jia Zeng, Mingxuan Yuan, Kun Mao and Jie Wang
• Abstract summary: We propose a reinforcement learning-based reformulation method for linear programming (LP) to improve the performance of solving process. We implement the proposed method over two public research LP datasets and one large-scale LP dataset collected from practical production planning scenario.
• Score: 11.628932152805724
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: It has been verified that the linear programming (LP) is able to formulate many real-life optimization problems, which can obtain the optimum by resorting to corresponding solvers such as OptVerse, Gurobi and CPLEX. In the past decades, a serial of traditional operation research algorithms have been proposed to obtain the optimum of a given LP in a fewer solving time. Recently, there is a trend of using machine learning (ML) techniques to improve the performance of above solvers. However, almost no previous work takes advantage of ML techniques to improve the performance of solver from the front end, i.e., the modeling (or formulation). In this paper, we are the first to propose a reinforcement learning-based reformulation method for LP to improve the performance of solving process. Using an open-source solver COIN-OR LP (CLP) as an environment, we implement the proposed method over two public research LP datasets and one large-scale LP dataset collected from practical production planning scenario. The evaluation results suggest that the proposed method can effectively reduce both the solving iteration number ($25\%\downarrow$) and the solving time ($15\%\downarrow$) over above datasets in average, compared to directly solving the original LP instances.

Related papers

• OptiBench Meets ReSocratic: Measure and Improve LLMs for Optimization Modeling [62.19438812624467]
  Large language models (LLMs) have exhibited their problem-solving abilities in mathematical reasoning. We propose OptiBench, a benchmark for End-to-end optimization problem-solving with human-readable inputs and outputs.
  arXiv  Detail & Related papers  (2024-07-13T13:27:57Z)
• Learning Constrained Optimization with Deep Augmented Lagrangian Methods [54.22290715244502]
  A machine learning (ML) model is trained to emulate a constrained optimization solver. This paper proposes an alternative approach, in which the ML model is trained to predict dual solution estimates directly. It enables an end-to-end training scheme is which the dual objective is as a loss function, and solution estimates toward primal feasibility, emulating a Dual Ascent method.
  arXiv  Detail & Related papers  (2024-03-06T04:43:22Z)
• Relative-Interior Solution for the (Incomplete) Linear Assignment Problem with Applications to the Quadratic Assignment Problem [2.149302375766032]
  We study the set of optimal solutions of the dual linear programming formulation of the linear assignment problem (LAP) We propose a method for computing a solution from the relative interior of this set.
  arXiv  Detail & Related papers  (2023-01-26T16:22:01Z)
• Teaching Networks to Solve Optimization Problems [13.803078209630444]
  We propose to replace the iterative solvers altogether with a trainable parametric set function. We show the feasibility of learning such parametric (set) functions to solve various classic optimization problems.
  arXiv  Detail & Related papers  (2022-02-08T19:13:13Z)
• Solving Multistage Stochastic Linear Programming via Regularized Linear Decision Rules: An Application to Hydrothermal Dispatch Planning [77.34726150561087]
  We propose a novel regularization scheme for linear decision rules (LDR) based on the AdaSO (adaptive least absolute shrinkage and selection operator) Experiments show that the overfit threat is non-negligible when using the classical non-regularized LDR to solve MSLP. For the LHDP problem, our analysis highlights the following benefits of the proposed framework in comparison to the non-regularized benchmark.
  arXiv  Detail & Related papers  (2021-10-07T02:36:14Z)
• Learning to Optimize: A Primer and A Benchmark [94.29436694770953]
  Learning to optimize (L2O) is an emerging approach that leverages machine learning to develop optimization methods. This article is poised to be the first comprehensive survey and benchmark of L2O for continuous optimization.
  arXiv  Detail & Related papers  (2021-03-23T20:46:20Z)
• 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)
• Decomposition and Adaptive Sampling for Data-Driven Inverse Linear Optimization [12.610576072466895]
  This work addresses inverse linear optimization where the goal is to infer the unknown cost vector of a linear program. We introduce a new formulation of the problem that, compared to other existing methods, allows the recovery of a less restrictive and generally more appropriate admissible set of cost estimates.
  arXiv  Detail & Related papers  (2020-09-16T22:25:31Z)
• Initializing Successive Linear Programming Solver for ACOPF using Machine Learning [0.0]
  This paper examines various machine learning (ML) algorithms available in the Scikit-Learn library to initialize an SLP-ACOPF solver. We evaluate the quality of each of these machine learning algorithms for predicting variables needed for a power flow solution. The approach is tested on a congested and non-congested 3 bus systems.
  arXiv  Detail & Related papers  (2020-07-17T20:01:55Z)
• 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.