Supervised neighborhood selection and MIP-based primal heuristics

Mixed integer programming provides a unifying framework for solving a medley of hard combinatorial optimization problems of practical interest. A mixed integer program (MIP) is typically solved using linear programming (LP) based branch-and-bound algorithm. Primal heuristics are a key component of MIP solvers and enable finding good feasible solutions early in the tree search. The literature is rich with a variety of hybrid primal heuristics that combine both heuristic and exact methods. In this thesis, we propose a new supervised large neighborhood search heuristic for the general MIP, as well as, a new analytical MIP-based primal heuristic for the linear ordering problem. We present our work in two parts. Part I: Supervised Neighborhood Selection for Mixed Integer Programs. Large neighborhood search (LNS) heuristics are employed as improvement procedures within the branch-and-bound algorithm. They formulate the neighborhoods as an auxiliary MIP with a restricted search space, which is then solved to search for an improving solution. The neighborhoods are typically defined by handcrafted rules, guided by human intuition and offline experimentation. Alternatively, a neighborhood should be defined such that it has a high likelihood of success. We apply a data-driven approach to predict an ideal neighborhood for the neighborhood search. We propose a supervised large neighborhood search heuristic for the general mixed integer programs and compare it with Relaxation Induced Neighborhood Search (RINS), a popular LNS heuristic. Our heuristic not only finds an improving solution more often but also improves the solver performance on key metrics. Part II: MIP-based Primal Heuristic for the Linear Ordering Problem. Linear ordering problem (LOP) is a quintessential combinatorial optimization problem and has been well studied in the literature. We present a new MIP-based primal heuristic for the LOP. The heuristic decomposes the LOP instance into sub-problems albeit sub-optimal ones, solves each sub-problem optimally and concatenates the partial solutions to construct a solution to the original problem instance. We present empirical results that show that our heuristics achieves good performance on benchmark instances.