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 sequentially solving restricted mixed integer programs (MIPs) to optimality. These are obtained from the master problem MIP by limiting the number of variable flips for structured subsets of the binary edge variables which are selected based on the underlying network cost structure. We introduce generalized local branching cuts which enforce the latter using two parameters at the same time: the number of considered variables and the number of allowed variable flips.Using this concept we develop an efficient algorithm for the capacitated ring tree problem (CRTP), a recent network design model for partially reliable capacitated networks that combines cycle and tree structures. Our implementation operates on top of an efficient branch and cut algorithm for the CRTP. The sets of refinement variables are deduced from single-ball network node clusters. We provide computational results and an extensive analysis of the algorithm for a set of literature instances. We show that the approach is capable of improving existing best results for the CRTP and outperforms the pure refinement or local branching approaches. (C) 2017 Elsevier B.V. All rights reserved.