Learning Mixed-Integer Linear Programs from Contextual Examples
- URL: http://arxiv.org/abs/2107.07136v1
- Date: Thu, 15 Jul 2021 05:45:52 GMT
- Title: Learning Mixed-Integer Linear Programs from Contextual Examples
- Authors: Mohit Kumar, Samuel Kolb, Luc De Raedt and Stefano Teso
- Abstract summary: Mixed-integer linear programs (MILPs) are widely used in artificial intelligence and operations research.
In this paper, we study the problem of acquiring MILPs from contextual examples.
We also contribute MISSLE, an algorithm for learning MILPs from contextual examples.
- Score: 37.56298025474654
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Mixed-integer linear programs (MILPs) are widely used in artificial
intelligence and operations research to model complex decision problems like
scheduling and routing. Designing such programs however requires both domain
and modelling expertise. In this paper, we study the problem of acquiring MILPs
from contextual examples, a novel and realistic setting in which examples
capture solutions and non-solutions within a specific context. The resulting
learning problem involves acquiring continuous parameters -- namely, a cost
vector and a feasibility polytope -- but has a distinctly combinatorial flavor.
To solve this complex problem, we also contribute MISSLE, an algorithm for
learning MILPs from contextual examples. MISSLE uses a variant of stochastic
local search that is guided by the gradient of a continuous surrogate loss
function. Our empirical evaluation on synthetic data shows that MISSLE acquires
better MILPs faster than alternatives based on stochastic local search and
gradient descent.
Related papers
- Optimization by Parallel Quasi-Quantum Annealing with Gradient-Based Sampling [0.0]
This study proposes a different approach that integrates gradient-based update through continuous relaxation, combined with Quasi-Quantum Annealing (QQA)
Numerical experiments demonstrate that our method is a competitive general-purpose solver, achieving performance comparable to iSCO and learning-based solvers.
arXiv Detail & Related papers (2024-09-02T12:55:27Z) - 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) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
We introduce a novel theoretical framework for analyzing the effectiveness of DeepMatching Networks and Reinforcement Learning methods.
Our main contribution holds for a broad class of problems including Max-and Min-Cut, Max-$k$-Bipartite-Bi, Maximum-Weight-Bipartite-Bi, and Traveling Salesman Problem.
As a byproduct of our analysis we introduce a novel regularization process over vanilla descent and provide theoretical and experimental evidence that it helps address vanishing-gradient issues and escape bad stationary points.
arXiv Detail & Related papers (2023-10-08T23:39:38Z) - A Deep Instance Generative Framework for MILP Solvers Under Limited Data
Availability [66.37474135424637]
We propose G2MILP, the first deep generative framework for MILP instances.
G2MILP represents MILP instances as bipartite graphs, and applies a masked variational autoencoder to iteratively corrupt and replace parts of the original graphs to generate new ones.
We design a suite of benchmarks to evaluate the quality of the generated MILP instances.
arXiv Detail & Related papers (2023-10-04T13:34:34Z) - Tackling Diverse Minorities in Imbalanced Classification [80.78227787608714]
Imbalanced datasets are commonly observed in various real-world applications, presenting significant challenges in training classifiers.
We propose generating synthetic samples iteratively by mixing data samples from both minority and majority classes.
We demonstrate the effectiveness of our proposed framework through extensive experiments conducted on seven publicly available benchmark datasets.
arXiv Detail & Related papers (2023-08-28T18:48:34Z) - Global and Preference-based Optimization with Mixed Variables using Piecewise Affine Surrogates [0.6083861980670925]
This paper proposes a novel surrogate-based global optimization algorithm to solve linearly constrained mixed-variable problems.
We assume the objective function is black-box and expensive-to-evaluate, while the linear constraints are quantifiable unrelaxable a priori known.
We introduce two types of exploration functions to efficiently search the feasible domain via mixed-integer linear programming solvers.
arXiv Detail & Related papers (2023-02-09T15:04:35Z) - Provable Reinforcement Learning with a Short-Term Memory [68.00677878812908]
We study a new subclass of POMDPs, whose latent states can be decoded by the most recent history of a short length $m$.
In particular, in the rich-observation setting, we develop new algorithms using a novel "moment matching" approach with a sample complexity that scales exponentially.
Our results show that a short-term memory suffices for reinforcement learning in these environments.
arXiv Detail & Related papers (2022-02-08T16:39:57Z) - Minimizing Entropy to Discover Good Solutions to Recurrent Mixed Integer
Programs [0.0]
Current solvers for mixed-integer programming (MIP) problems are designed to perform well on a wide range of problems.
Recent works have shown that machine learning (ML) can be integrated with an MIP solver to inject domain knowledge and efficiently close the optimality gap.
This paper proposes an online solver that uses the notion of entropy to efficiently build a model with minimal training data and tuning.
arXiv Detail & Related papers (2022-02-07T18:52:56Z) - Adaptive neighborhood Metric learning [184.95321334661898]
We propose a novel distance metric learning algorithm, named adaptive neighborhood metric learning (ANML)
ANML can be used to learn both the linear and deep embeddings.
The emphlog-exp mean function proposed in our method gives a new perspective to review the deep metric learning methods.
arXiv Detail & Related papers (2022-01-20T17:26:37Z) - Knowledge engineering mixed-integer linear programming: constraint
typology [2.4002205752931625]
We investigate the constraint typology of mixed-integer linear programming MILP formulations.
MILP is a commonly used mathematical programming technique for modelling and solving real-life scheduling, routing, planning, resource allocation, timetabling optimization problems.
arXiv Detail & Related papers (2021-02-20T20:07:24Z)
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.