Supervised neighborhood selection and MIP-based primal heuristics

Resource type
Thesis type
(Thesis) M.Sc.
Date created
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.
Copyright statement
Copyright is held by the author.
This thesis may be printed or downloaded for non-commercial research and scholarly purposes.
Scholarly level
Supervisor or Senior Supervisor
Thesis advisor: Krishnamurti, Ramesh
Member of collection
Attachment Size
etd20696.pdf 978.04 KB