Threshold-aware Learning to Generate Feasible Solutions for Mixed
  Integer Programs
Taehyun Yoon Jinwon Choi Hyokun Yun Sungbin Lim
Finding a high-quality feasible solution to a combinatorial optimization (CO)
problem in a limited time is challenging due to its discrete nature. Recently,
there has been an increasing number of machine learning (ML) methods for
addressing CO problems. Neural diving (ND) is one of the learning-based
approaches to generating partial discrete variable assignments in Mixed Integer
Programs (MIP), a framework for modeling CO problems. However, a major drawback
of ND is a large discrepancy between the ML and MIP objectives, i.e., variable
value classification accuracy over primal bound. Our study investigates that a
specific range of variable assignment rates (coverage) yields high-quality
feasible solutions, where we suggest optimizing the coverage bridges the gap
between the learning and MIP objectives. Consequently, we introduce a post-hoc
method and a learning-based approach for optimizing the coverage. A key idea of
our approach is to jointly learn to restrict the coverage search space and to
predict the coverage in the learned search space. Experimental results
demonstrate that learning a deep neural network to estimate the coverage for
finding high-quality feasible solutions achieves state-of-the-art performance
in NeurIPS ML4CO datasets. In particular, our method shows outstanding
performance in the workload apportionment dataset, achieving the optimality gap
of 0.45%, a ten-fold improvement over SCIP within the one-minute time limit.