  Large Neighborhood Search (LNS) is a popular heuristic algorithm for solving
combinatorial optimization problems (COP). It starts with an initial solution
to the problem and iteratively improves it by searching a large neighborhood
around the current best solution. LNS relies on heuristics to select
neighborhoods to search in. In this paper, we focus on designing effective and
efficient heuristics in LNS for integer linear programs (ILP) since a wide
range of COPs can be represented as ILPs. Local Branching (LB) is a heuristic
that selects the neighborhood that leads to the largest improvement over the
current solution in each iteration of LNS. LB is often slow since it needs to
solve an ILP of the same size as input. Our proposed heuristics, LB-RELAX and
its variants, use the linear programming relaxation of LB to select
neighborhoods. Empirically, LB-RELAX and its variants compute as effective
neighborhoods as LB but run faster. They achieve state-of-the-art anytime
performance on several ILP benchmarks.
