@inproceedings{
huang2023contrastive,
title={Contrastive Predict-and-Search for Mixed Integer Linear Programs},
author={Taoan Huang and Aaron M Ferber and Arman Zharmagambetov and Yuandong Tian and Bistra Dilkina},
booktitle={OPT 2023: Optimization for Machine Learning},
year={2023},
url={https://openreview.net/forum?id=5yGwzxRVcg}
}
Mixed integer linear programs  (MILP) are flexible and powerful tool for modeling and solving many difficult real-world  combinatorial optimization problems. In this paper, we propose a novel machine learning-based framework ConPaS that learns to predict solutions to MILPs with contrastive learning. For training, we collect high-quality solutions as positive samples and low-quality or infeasible solutions as negative samples. We then learn to make discriminative predictions by contrasting the positive and negative samples.   During test time, we predict  assignments for a subset of integer variables of a MILP and then solve the resulting reduced MILP to construct high-quality solutions. Empirically, we show that ConPaS achieves state-of-the-art results compared to other ML-based approaches in terms of the quality of and the speed at which the solutions are found.
Contrastive Predict-and-Search for Mixed Integer Linear Programs
Taoan Huang Aaron M Ferber Arman Zharmagambetov Yuandong Tian Bistra Dilkina