A learning-based mathematical programming formulation for the automatic configuration of optimization solvers

• URL: http://arxiv.org/abs/2401.04237v1
• Date: Mon, 8 Jan 2024 21:10:56 GMT
• Title: A learning-based mathematical programming formulation for the automatic configuration of optimization solvers
• Authors: Gabriele Iommazzo, Claudia D'Ambrosio, Antonio Frangioni, Leo Liberti
• Abstract summary: We employ a set of solved instances and configurations in order to learn a performance function of the solver. We formulate a mixed-integer nonlinear program where the objective/constraints explicitly encode the learnt information.
• Score: 0.8075866265341176
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We propose a methodology, based on machine learning and optimization, for selecting a solver configuration for a given instance. First, we employ a set of solved instances and configurations in order to learn a performance function of the solver. Secondly, we formulate a mixed-integer nonlinear program where the objective/constraints explicitly encode the learnt information, and which we solve, upon the arrival of an unknown instance, to find the best solver configuration for that instance, based on the performance function. The main novelty of our approach lies in the fact that the configuration set search problem is formulated as a mathematical program, which allows us to a) enforce hard dependence and compatibility constraints on the configurations, and b) solve it efficiently with off-the-shelf optimization tools.

Related papers

• 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)
• 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)
• Learning to Configure Mathematical Programming Solvers by Mathematical Programming [0.8075866265341176]
  We discuss the issue of finding a good mathematical programming solver configuration for a particular instance of a given problem. A specific difficulty of learning a good solver configuration is that parameter settings may not all be independent. We tackle this issue in the second phase of our approach, where we use the learnt information to construct and solve an optimization problem.
  arXiv  Detail & Related papers  (2024-01-10T10:02:01Z)
• 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)
• 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)
• 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)
• A machine learning framework for neighbor generation in metaheuristic search [4.521119623956821]
  We propose a general machine learning framework for neighbor generation in metaheuristic search. We validate our methodology on two metaheuristic applications.
  arXiv  Detail & Related papers  (2022-12-22T01:58:04Z)
• 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)
• 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)
• SeaPearl: A Constraint Programming Solver guided by Reinforcement Learning [0.0]
  This paper presents the proof of concept for SeaPearl, a new constraint programming solver implemented in Julia. SeaPearl supports machine learning routines in order to learn branching decisions using reinforcement learning. Although not yet competitive with industrial solvers, SeaPearl aims to provide a flexible and open-source framework.
  arXiv  Detail & Related papers  (2021-02-18T07:34:38Z)
• Optimizing Wireless Systems Using Unsupervised and Reinforced-Unsupervised Deep Learning [96.01176486957226]
  Resource allocation and transceivers in wireless networks are usually designed by solving optimization problems. In this article, we introduce unsupervised and reinforced-unsupervised learning frameworks for solving both variable and functional optimization problems.
  arXiv  Detail & Related papers  (2020-01-03T11:01:52Z)

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.