Smart Predict-­‐and-­‐Optimize for Hard Combinatorial Optimization Problems

Jayanta Mandi, Emir Demirović, Peter J. Stuckey, Tias Guns

Onderzoeksoutput: Conference paper

4 Citaten (Scopus)

Samenvatting

Combinatorial optimization assumes that all parameters of the optimization problem, e.g. the weights in the objective function, are fixed. Often, these weights are mere estimates and increasingly machine learning techniques are used to for their estimation. Recently, Smart Predict and Optimize (SPO) has been proposed for problems with a linear objective function over the predictions, more specifically linear programming problems. It takes the regret of the predictions on the linear problem into account, by repeatedly solving it during learning. We investigate the use of SPO to solve more realistic discrete optimization problems. The main challenge is the repeated solving of the optimization problem. To this end, we investigate ways to relax the problem as well as warm-starting the learning and the solving. Our results show that even for discrete problems it often suffices to train by solving the relaxation in the SPO loss. Furthermore, this approach outperforms the state-of-the-art approach of wilder2018melding. We experiment with weighted knapsack problems as well as complex scheduling problems, and show for the first time that a predict-and-optimize approach can successfully be used on large-scale combinatorial optimization problems.
Originele taal-2English
TitelAAAI-20 Technical Tracks 2
Plaats van productiePalo Alto, California USA
UitgeverijAAAI Press
HoofdstukAAAI Technical Track on Constraint Satisfaction and Optimization
Pagina's1603-1610
Aantal pagina's8
Volume34
ISBN van elektronische versie978-1-57735-835-0
ISBN van geprinte versie978-1-57735-835-0
StatusPublished - 15 jun 2020
EvenementThirty-Fourth AAAI Conference on Artificial Intelligence - New York Hilton Midtown, New York, United States
Duur: 7 feb 202012 mrt 2020
https://aaai.org/Conferences/AAAI-20/

Publicatie series

NaamAAAI-20 Technical Tracks 2
UitgeverijAAAI Press
Nummer02
Volume34
ISSN van geprinte versie2159-5399
ISSN van elektronische versie2374-3468

Conference

ConferenceThirty-Fourth AAAI Conference on Artificial Intelligence
Verkorte titelAAAI-20
LandUnited States
StadNew York
Periode7/02/2012/03/20
Internet adres

Vingerafdruk

Duik in de onderzoeksthema's van 'Smart Predict-­‐and-­‐Optimize for Hard Combinatorial Optimization Problems'. Samen vormen ze een unieke vingerafdruk.

Citeer dit