期刊
NETWORKS
卷 44, 期 2, 页码 61-72出版社
JOHN WILEY & SONS INC
DOI: 10.1002/net.20017
关键词
mixed-integer programs; heuristics; facility location problems
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. (C) 2004 Wiley Periodicals, Inc.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据