Learning Fast Optimizers for Contextual Stochastic Integer Programs

Vinod Nair, Dj Dvijotham, Iain Dunning, Oriol Vinyals
Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, PMLR R16:590-599, 2018.

Abstract

We present a novel reinforcement learning (RL) approach to learning a fast and highly scalable solver for a two-stage stochastic integer pro- gram in the large-scale data setting. Mixed inte- ger programming solvers do not scale to large datasets for this problem class. Additionally, they solve each instance independently, without any knowledge transfer across instances. We address these limitations with a learnable local search solver that jointly learns two policies, one to generate an initial solution and another to iteratively improve it with local moves. The policies use contextual features for a problem instance as input, which enables learning across instances and generalization to new ones. We also propose learning a policy to compute a bound on the objective using dual decompo- sition. Benchmark results show that on test instances our approach rapidly achieves approx- imately 30% to 2000% better objective value, which a state of the art integer programming solver (SCIP) requires more than an order of magnitude more running time to match. Our approach also achieves better solution quality on seven out of eight benchmark problems than standard baselines such as Tabu Search and Pro- gressive Hedging.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR16-nair18a, title = {Learning Fast Optimizers for Contextual Stochastic Integer Programs}, author = {Nair, Vinod and Dvijotham, Dj and Dunning, Iain and Vinyals, Oriol}, booktitle = {Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence}, pages = {590--599}, year = {2018}, editor = {Globerson, Amir and Silva, Ricardo}, volume = {R16}, series = {Proceedings of Machine Learning Research}, month = {06--10 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r16/main/assets/nair18a/nair18a.pdf}, url = {https://proceedings.mlr.press/r16/nair18a.html}, abstract = {We present a novel reinforcement learning (RL) approach to learning a fast and highly scalable solver for a two-stage stochastic integer pro- gram in the large-scale data setting. Mixed inte- ger programming solvers do not scale to large datasets for this problem class. Additionally, they solve each instance independently, without any knowledge transfer across instances. We address these limitations with a learnable local search solver that jointly learns two policies, one to generate an initial solution and another to iteratively improve it with local moves. The policies use contextual features for a problem instance as input, which enables learning across instances and generalization to new ones. We also propose learning a policy to compute a bound on the objective using dual decompo- sition. Benchmark results show that on test instances our approach rapidly achieves approx- imately 30% to 2000% better objective value, which a state of the art integer programming solver (SCIP) requires more than an order of magnitude more running time to match. Our approach also achieves better solution quality on seven out of eight benchmark problems than standard baselines such as Tabu Search and Pro- gressive Hedging.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Learning Fast Optimizers for Contextual Stochastic Integer Programs %A Vinod Nair %A Dj Dvijotham %A Iain Dunning %A Oriol Vinyals %B Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2018 %E Amir Globerson %E Ricardo Silva %F pmlr-vR16-nair18a %I PMLR %P 590--599 %U https://proceedings.mlr.press/r16/nair18a.html %V R16 %X We present a novel reinforcement learning (RL) approach to learning a fast and highly scalable solver for a two-stage stochastic integer pro- gram in the large-scale data setting. Mixed inte- ger programming solvers do not scale to large datasets for this problem class. Additionally, they solve each instance independently, without any knowledge transfer across instances. We address these limitations with a learnable local search solver that jointly learns two policies, one to generate an initial solution and another to iteratively improve it with local moves. The policies use contextual features for a problem instance as input, which enables learning across instances and generalization to new ones. We also propose learning a policy to compute a bound on the objective using dual decompo- sition. Benchmark results show that on test instances our approach rapidly achieves approx- imately 30% to 2000% better objective value, which a state of the art integer programming solver (SCIP) requires more than an order of magnitude more running time to match. Our approach also achieves better solution quality on seven out of eight benchmark problems than standard baselines such as Tabu Search and Pro- gressive Hedging. %Z Reissued by PMLR on 04 October 2026.
APA
Nair, V., Dvijotham, D., Dunning, I. & Vinyals, O.. (2018). Learning Fast Optimizers for Contextual Stochastic Integer Programs. Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R16:590-599 Available from https://proceedings.mlr.press/r16/nair18a.html. Reissued by PMLR on 04 October 2026.

Related Material