A local branching heuristic for the capacitated fixed-charge network design problem

We describe in this article a new heuristic approach for the capacitated fixed-charge network design problem. This is a well known NPNP-hard problem that has been extensively studied. We propose to use local branching to tackle it. Local branching is a novel metaheuristic technique presented by Fischetti and Lodi [Local branching. Mathematical Programming Series B 2003;98:23–47] that utilizes a general MIP solver to explore neighborhoods. Our implementation is tested on a large set of benchmark instances. The results show that the method outperforms the best heuristic approaches found in the literature.