A local branching heuristic for mixed-integer programs with 2-level variables, with an application to a telecommunication network design problem

Effective heuristic solution methods for general Mixed-Integer Programs (MIPs) are strongly required in many practical applications, and have been the subject of an intensive research effort in the recent years. Fischetti and Lodi recently proposed an exact solution technique based on the use of branching conditions expressed through (invalid) linear inequalities called local branching cuts. In the concluding remarks of their article, these authors anticipated the possibility their method be used to design a genuine MIP metaheuristic framework akin to Tabu Search (TS) or Variable Neighborhood Search (VNS), based on an external MIP solver. In the present article we introduce and analyze computationally a specific implementation of the above idea. In particular, we address MIPs with binary variables, and propose a variant of the classical VNS scheme that we call Diversification, Refining, and Tight-refining (DRT). The new approach is intended to be of high generality, but exploits the specific structure of some MIPs where the set of binary variables partitions naturally into two levels, with the property that fixing the value of the first-level variables produces an easier-to-solve (but still hard) subproblem. This is often the case, for example, in hard facility location problems arising in telecommunication network design. Our method detects automatically the presence in the MIP model of the first-level binary variables, if any, according to simple heuristic criteria. This information is then exploited during the intensification phase of the local search, so as to explore nested solution neighborhoods defined by local branching cuts affecting the first- and second-level variables in a different way. Computational results for a hard facility location problem arising in telecommunication UMTS network design are presented, with a comparison among different heuristic methods: the general-purpose commercial ILOG-Cplex 7.0 MIP code, the original Fischetti-Lodi local branching heuristic scheme, the new DRT method, and (for some instances) ad hoc TS and VNS heuristics. The results show that the DRT method, though very simple to implement, provides better heuristic solutions than the alternative methods on all the instances of our test bed. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(2), 61–72 2004