Operator splitting can be used to design easy-to-train models for predict-and-optimize tasks, which scale effortlessly to problems with thousands of variables.
In many practical settings, a combinatorial problem must be repeatedly solved with similar, but distinct parameters. Yet, the parameters are not directly observed; only contextual data that correlates with is available. It is tempting to use a neural network to predict given , but training such a model requires reconciling the discrete nature of combinatorial optimization with the gradient-based frameworks used to train neural networks. One approach to overcoming this issue is to consider a continuous relaxation of the combinatorial problem.
While existing such approaches have shown to be highly effective on small problems (10--100 variables) they do not scale well to large problems. In this work, we show how recent results in operator splitting can be used to design such a system which is easy to train and scales effortlessly to problems with thousands of variables.
Citation
@article{mckenzie2023faster,
title={{Faster Predict-and-Optimize with Davis-Yin Splitting}},
author={McKenzie, Daniel and Wu Fung, Samy and Heaton, Howard},
journal={arXiv preprint arXiv:2301.13395},
year={2023}
}