Variable neighborhood search and local branching
Variable neighborhood search and local branching
复制标题
DOI：
10.1016/j.cor.2005.02.033
复制
发表时间：
2004-06
期刊：
影响因子：
--
通讯作者：
P. Hansen;N. Mladenović;D. Urošević
中科院分区：
文献类型：
--
作者：
P. Hansen;N. Mladenović;D. Urošević
在本文中，我们开发了一种用于求解混合整数规划（MIPs）的可变邻域搜索（VNS）启发式算法。它使用CPLEX，通用MIP求解器，作为一个黑盒。如Fischetti和Lodi（Mathematical Programming Series B 2003;98：23-47）最近的局部分支（LB）方法中所建议的，通过向原始问题添加约束来定义现任解周围的邻域。LB和VNS都使用相同的工具：CPLEX和对现任者周围社区的相同定义。然而，我们的VNS是更简单，更系统的邻域探索。因此，在相同的时间限制内，我们能够从用于测试LB的29个难题实例中改进14倍的最佳已知解决方案。
In this paper we develop a variable neighborhood search (VNS) heuristic for solving mixed-integer programs (MIPs). It uses CPLEX, the general-purpose MIP solver, as a black-box. Neighborhoods around the incumbent solution are defined by adding constraints to the original problem, as suggested in the recent local branching (LB) method of Fischetti and Lodi (Mathematical Programming Series B 2003;98:23–47). Both LB and VNS use the same tools: CPLEX and the same definition of the neighborhoods around the incumbent. However, our VNS is simpler and more systematic in neighborhood exploration. Consequently, within the same time limit, we were able to improve 14 times the best known solution from the set of 29 hard problem instances used to test LB.