Learning Primal Heuristics for Mixed Integer Programs
  This paper proposes a novel primal heuristic for Mixed Integer Programs, by
employing machine learning techniques. Mixed Integer Programming is a general
technique for formulating combinatorial optimization problems. Inside a solver,
primal heuristics play a critical role in finding good feasible solutions that
enable one to tighten the duality gap from the outset of the Branch-and-Bound
algorithm (B&B), greatly improving its performance by pruning the B&B tree
aggressively. In this paper, we investigate whether effective primal heuristics
can be automatically learned via machine learning. We propose a new method to
represent an optimization problem as a graph, and train a Graph Convolutional
Network on solved problem instances with known optimal solutions. This in turn
can predict the values of decision variables in the optimal solution for an
unseen problem instance of a similar type. The prediction of variable solutions
is then leveraged by a novel configuration of the B&B method, Probabilistic
Branching with guided Depth-first Search (PB-DFS) approach, aiming to find
(near-)optimal solutions quickly. The experimental results show that this new
heuristic can find better primal solutions at a much earlier stage of the
solving process, compared to other state-of-the-art primal heuristics.
