Smart Predict-and-Optimize for Hard Combinatorial Optimization Problems
Smart Predict-and-Optimize for Hard Combinatorial Optimization Problems
复制标题
硬组合优化问题的智能预测和优化
DOI：
10.1609/aaai.v34i02.5521
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Tias Guns
中科院分区：
文献类型：
--
作者：
Jaynta Mandi;Emir Demirovi'c;Peter James Stuckey;Tias Guns
组合优化假设优化问题的所有参数，例如目标函数中的权重都是固定的。通常，这些权重只是估计，越来越多的机器学习技术被用于估计。最近，智能预测和优化(SPO)被提出用来解决具有线性目标函数的预测问题，更具体地说是线性规划问题。它通过在学习过程中反复解决线性问题，考虑了对线性问题预测的遗憾。研究了SPO算法在求解更现实的离散优化问题中的应用。主要的挑战是优化问题的反复求解。为此，我们探索了放松问题的方法，并温暖地启动了学习和解决。我们的结果表明，即使对于离散问题，通过解决SPO损失中的松弛来训练通常也是足够的。此外，这种方法的性能优于怀尔德、迪尔金娜和坦贝的最先进的方法。我们对加权背包问题和复杂调度问题进行了实验，并首次证明了预测优化方法可以成功地用于大规模组合优化问题。
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 Wilder, Dilkina, and Tambe. 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.