Learning Hard Optimization Problems: A Data Generation Perspective
- URL: http://arxiv.org/abs/2106.02601v1
- Date: Fri, 4 Jun 2021 17:03:44 GMT
- Title: Learning Hard Optimization Problems: A Data Generation Perspective
- Authors: James Kotary, Ferdinando Fioretto, Pascal Van Hentenryck
- Abstract summary: This paper demonstrates the volatility of the training data to the ability to approximate it.
It proposes a method for producing (exact or approximate) solutions to optimization problems that are amenable to supervised tasks.
- Score: 44.4747903763245
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Optimization problems are ubiquitous in our societies and are present in
almost every segment of the economy. Most of these optimization problems are
NP-hard and computationally demanding, often requiring approximate solutions
for large-scale instances. Machine learning frameworks that learn to
approximate solutions to such hard optimization problems are a potentially
promising avenue to address these difficulties, particularly when many closely
related problem instances must be solved repeatedly. Supervised learning
frameworks can train a model using the outputs of pre-solved instances.
However, when the outputs are themselves approximations, when the optimization
problem has symmetric solutions, and/or when the solver uses randomization,
solutions to closely related instances may exhibit large differences and the
learning task can become inherently more difficult. This paper demonstrates
this critical challenge, connects the volatility of the training data to the
ability of a model to approximate it, and proposes a method for producing
(exact or approximate) solutions to optimization problems that are more
amenable to supervised learning tasks. The effectiveness of the method is
tested on hard non-linear nonconvex and discrete combinatorial problems.
Related papers
- 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) - Decomposition of Difficulties in Complex Optimization Problems Using a Bilevel Approach [0.30723404270319693]
Practical optimization problems may contain different kinds of difficulties that are often not tractable if one relies on a particular optimization method.
We propose a decomposition strategy that allows us to apply two approaches at the same time on a complex optimization problem.
arXiv Detail & Related papers (2024-07-03T18:59:17Z) - Looking Ahead to Avoid Being Late: Solving Hard-Constrained Traveling
Salesman Problem [36.88003015541172]
We propose a novel learning-based method that uses looking-ahead information as the feature to improve the legality of TSP with Time Windows (TSPTW) solutions.
With comprehensive experiments on diverse datasets, MUSLA outperforms existing baselines and shows generalizability potential.
arXiv Detail & Related papers (2024-03-08T13:49:21Z) - 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 Framework for Inherently Interpretable Optimization Models [0.0]
Solution of large-scale problems that seemed intractable decades ago are now a routine task.
One major barrier is that the optimization software can be perceived as a black box.
We propose an optimization framework to derive solutions that inherently come with an easily comprehensible explanatory rule.
arXiv Detail & Related papers (2022-08-26T10:32:00Z) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
We present an end-to-end method to learn the proximal operator across non-family problems.
We show that for weakly-ized objectives and under mild conditions, the method converges globally.
arXiv Detail & Related papers (2022-01-28T05:53:28Z) - Contrastive Losses and Solution Caching for Predict-and-Optimize [19.31153168397003]
We use a Noise Contrastive approach to motivate a family of surrogate loss functions.
We address a major bottleneck of all predict-and-optimize approaches.
We show that even a very slow growth rate is enough to match the quality of state-of-the-art methods.
arXiv Detail & Related papers (2020-11-10T19:09:12Z) - Automatically Learning Compact Quality-aware Surrogates for Optimization
Problems [55.94450542785096]
Solving optimization problems with unknown parameters requires learning a predictive model to predict the values of the unknown parameters and then solving the problem using these values.
Recent work has shown that including the optimization problem as a layer in a complex training model pipeline results in predictions of iteration of unobserved decision making.
We show that we can improve solution quality by learning a low-dimensional surrogate model of a large optimization problem.
arXiv Detail & Related papers (2020-06-18T19:11:54Z) - 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.