BTBS-LNS: A Binarized-Tightening, Branch and Search Approach of Learning Large Neighborhood Search Policies for MIP

Abstract

Learning to solve large-scale Mixed Integer Program (MIP) problems is an emerging research topic, and policy learning-based Large Neighborhood Search (LNS) has recently shown its effectiveness. However, prevailing approaches predominantly concentrated on binary variables and local search strategies, often susceptible to becoming ensnared in local optima. In response to these challenges, we introduce a novel technique, termed Binarized-Tightening Branch-and-Search LNS (BTBS-LNS). Specifically, we propose the ``Binarized Tightening" technique for integer variables to deal with their wide range by encoding and bound tightening, and design an attention-based tripartite graph to capture global correlations within MIP instances. Furthermore, we devised an extra branching network at each step, to identify and optimize some wrongly-fixed backdoor variables by pure LNS. We empirically show that our approach can effectively escape local optimum. Extensive experiments on different problems, including instances from Mixed Integer Programming Library (MIPLIB), show that it significantly outperforms the open-source solver SCIP and LNS baselines. It performs competitively with, and sometimes even better than the commercial solver Gurobi (v9.5.0), especially at an early stage. Source code will be made publicly available.