Skip to yearly menu bar Skip to main content


Poster

Contrastive Predict-and-Search for Mixed Integer Linear Programs

Taoan Huang · Aaron Ferber · Arman Zharmagambetov · Yuandong Tian · Bistra Dilkina


Abstract:

Mixed integer linear programs (MILP) are flexible and powerful tools for modeling and solving many difficult real-world combinatorial optimization problems. In this paper, we propose a novel machine learning (ML)-based framework ConPaS that learns to predict solutions to MILPs with contrastive learning. For training, we collect high-quality solutions as positive samples. We also collect low-quality or infeasible solutions as negative samples using novel optimization-based and sampling approaches. We then learn to make discriminative predictions by contrasting the positive and negative samples. During test time, we predict and fix the assignments for a subset of integer variables of a MILP and then solve the resulting reduced MILP to find high-quality solutions. Empirically, 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.

Live content is unavailable. Log in and register to view live content