Smart Predict-and-Optimize for Hard Combinatorial Optimization Problems
  Combinatorial optimization assumes that all parameters of the optimization
problem, e.g. the weights in the objective function is 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 warmstarting 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, for most instances, 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.
