Generalized local branching heuristics and the capacitated ring tree problem

In this paper we present a heuristic framework that is based on mathematical programming to solve network design problems. Our techniques combine local branching with locally exact refinements. In an iterative strategy an existing solution is refined by solving restricted mixed integer programs (MIPs) to optimality. These are obtained from the master problem MIP by (1) fixing a subset of binary variables and (2) limiting the number of variable flips among the unfixed variables. We introduce generalized local branching cuts which enforce (1) and (2). Using these concepts we develop an efficient algorithm for the capacitated ring tree problem (CRTP), a recent network design model for reliable capacitated networks that combines cycle and tree structures. Our implementation operates on top of an efficient branch & cut algorithm for the CRTP. The sets of refinement variables are deduced from single and multi-ball CRTP-tailored network node clusters. We provide computational results using a set of literature instances. We show that the approach is capable of improving existing best results for the CRTP when integrated into a multi-start local search heuristic, but is also efficient when used independently.