An Investigation Into Predict-and-Optimize Machine Learning

An Investigation Into Predict-and-Optimize Machine Learning

Puppels, Thomas (TU Delft Electrical Engineering, Mathematics and Computer Science)

Yorke-Smith, N. (mentor)
Verwer, S.E. (graduation committee)
Oliehoek, F.A. (graduation committee)

Delft University of Technology

Computer Science | Software Technology

2020-09-10

Predict-and-Optimize (PnO) is a relatively new machine learning paradigm that has attracted recent interest: it concerns the prediction of parameters that determine the value of solutions to an optimization problem, such that the optimizer ends up picking a good solution. Training estimators with standard loss functions like mean squared error and cross-entropy provides no guarantees that their predictions aid the optimizer in this aim. A number of approaches have been suggested over the past few years on how to most effectively tackle the PnO-setting, such as Smart "Predict, then Optimize" (SPO) and the Quadratic Programming Task Loss (QPTL). We investigate an experiment of the paper that introduced QPTL, and find that an estimator used as baseline approach was set back by two factors: a class imbalance, and a training duration that was too short. However, QPTL still outperforms the baseline approach. We consider the use of the Gumbel-Softmax Straight-Through Estimator for SPO and QPTL when training neural networks on a multi-class classification dataset (MNIST) in a PnO-setting. We compare the results for SPO and QPTL for different
output activation functions (linear output, sigmoid output, gumbel-softmax output) when predicting the objective parameters in 0-1 unweighted Knapsack problems and Bipartite Matching problems using this dataset. We find that neural networks trained via SPO with a linear output tend to show best performance, and that neural networks trained via QPTL are relatively unaffected by the output activation function of choice. Finally we find that PnO approaches, SPO in particular, can see large performance increases by constructing a large number of optimisation problems from a small pool of training data.

Machine Learning
Integer Programming
Combinatorial Optimization

http://resolver.tudelft.nl/uuid:5f5e1719-a460-4481-b6f9-80a26e8668c3

Student theses

master thesis

© 2020 Thomas Puppels