Machine Learning for $K$-adaptability in Two-stage Robust Optimization
- URL: http://arxiv.org/abs/2210.11152v1
- Date: Thu, 20 Oct 2022 10:43:23 GMT
- Title: Machine Learning for $K$-adaptability in Two-stage Robust Optimization
- Authors: Esther Julien, Krzysztof Postek, \c{S}. \.Ilker Birbil
- Abstract summary: Two-stage robust optimization problems constitute one of the hardest optimization problem classes.
One of the solution approaches to this class of problems is $K$-adaptability.
We propose a machine learning-based node selection strategy.
We experimentally show that using our learned node selection strategy outperforms a vanilla, random node selection strategy when tested on problems of the same type as the training problems.
- Score: 1.2891210250935143
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Two-stage robust optimization problems constitute one of the hardest
optimization problem classes. One of the solution approaches to this class of
problems is $K$-adaptability. This approach simultaneously seeks the best
partitioning of the uncertainty set of scenarios into $K$ subsets, and
optimizes decisions corresponding to each of these subsets. In general case, it
is solved using the $K$-adaptability branch-and-bound algorithm, which requires
exploration of exponentially-growing solution trees. To accelerate finding
high-quality solutions in such trees, we propose a machine learning-based node
selection strategy. In particular, we construct a feature engineering scheme
based on general two-stage robust optimization insights that allows us to train
our machine learning tool on a database of resolved B\&B trees, and to apply it
as-is to problems of different sizes and/or types. We experimentally show that
using our learned node selection strategy outperforms a vanilla, random node
selection strategy when tested on problems of the same type as the training
problems, also in case the $K$-value or the problem size differs from the
training ones.
Related papers
- Interpretable Decision Tree Search as a Markov Decision Process [8.530182510074983]
Finding an optimal decision tree for a supervised learning task is a challenging problem to solve at scale.
It was recently proposed to frame the problem as a Markov Decision Problem (MDP) and use deep reinforcement learning to tackle scaling.
We propose instead to scale the resolution of such MDPs using an information-theoretic tests generating function that generates for every state.
arXiv Detail & Related papers (2023-09-22T08:18:08Z) - A Machine Learning Approach to Two-Stage Adaptive Robust Optimization [6.943816076962257]
We propose an approach based on machine learning to solve two-stage linear adaptive robust optimization problems.
We encode the optimal here-and-now decisions, the worst-case scenarios associated with the optimal here-and-now decisions, and the optimal wait-and-see decisions.
We train a machine learning model that predicts high-quality strategies for the here-and-now decisions, the worst-case scenarios associated with the optimal here-and-now decisions, and the wait-and-see decisions.
arXiv Detail & Related papers (2023-07-23T19:23:06Z) - Landscape Surrogate: Learning Decision Losses for Mathematical
Optimization Under Partial Information [48.784330281177446]
Recent works in learning-integrated optimization have shown promise in settings where the optimization is only partially observed or where general-purposes perform poorly without expert tuning.
We propose using a smooth and learnable Landscape Surrogate as a replacement for $fcirc mathbfg$.
This surrogate, learnable by neural networks, can be computed faster than the $mathbfg$ solver, provides dense and smooth gradients during training, can generalize to unseen optimization problems, and is efficiently learned via alternating optimization.
arXiv Detail & Related papers (2023-07-18T04:29:16Z) - Let the Flows Tell: Solving Graph Combinatorial Optimization Problems
with GFlowNets [86.43523688236077]
Combinatorial optimization (CO) problems are often NP-hard and out of reach for exact algorithms.
GFlowNets have emerged as a powerful machinery to efficiently sample from composite unnormalized densities sequentially.
In this paper, we design Markov decision processes (MDPs) for different problems and propose to train conditional GFlowNets to sample from the solution space.
arXiv Detail & Related papers (2023-05-26T15:13:09Z) - A Novel Approach for Auto-Formulation of Optimization Problems [66.94228200699997]
In the Natural Language for Optimization (NL4Opt) NeurIPS 2022 competition, competitors focus on improving the accessibility and usability of optimization solvers.
In this paper, we present the solution of our team.
Our proposed methods have achieved the F1-score of 0.931 in subtask 1 and the accuracy of 0.867 in subtask 2, which won the fourth and third places respectively in this competition.
arXiv Detail & Related papers (2023-02-09T13:57:06Z) - 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) - Quant-BnB: A Scalable Branch-and-Bound Method for Optimal Decision Trees
with Continuous Features [5.663538370244174]
We present a new discrete optimization method based on branch-and-bound (BnB) to obtain optimal decision trees.
Our proposed algorithm Quant-BnB shows significant speedups compared to existing approaches for shallow optimal trees on various real datasets.
arXiv Detail & Related papers (2022-06-23T17:19:29Z) - ES-Based Jacobian Enables Faster Bilevel Optimization [53.675623215542515]
Bilevel optimization (BO) has arisen as a powerful tool for solving many modern machine learning problems.
Existing gradient-based methods require second-order derivative approximations via Jacobian- or/and Hessian-vector computations.
We propose a novel BO algorithm, which adopts Evolution Strategies (ES) based method to approximate the response Jacobian matrix in the hypergradient of BO.
arXiv Detail & Related papers (2021-10-13T19:36:50Z) - 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) - Generalized and Scalable Optimal Sparse Decision Trees [56.35541305670828]
We present techniques that produce optimal decision trees over a variety of objectives.
We also introduce a scalable algorithm that produces provably optimal results in the presence of continuous variables.
arXiv Detail & Related papers (2020-06-15T19:00:11Z) - 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.