论文标题
整数线性程序的本地分支放松启发式
Local Branching Relaxation Heuristics for Integer Linear Programs
论文作者
论文摘要
大型邻里搜索（LNS）是一种用于解决组合优化问题（COP）的流行启发式算法。它从解决问题的初始解决方案开始，并通过在当前最佳解决方案周围搜索大型社区来迭代地改进它。 LNS依靠启发式方法来选择要搜索的社区。在本文中，我们专注于在整数线性程序（ILP）中设计有效有效的LNS启发式方法，因为可以将广泛的COPS表示为ILP。局部分支（LB）是一种启发式方法，它选择了在每次LNS迭代中的当前解决方案的最大改进的邻域。 LB通常很慢，因为它需要求解与输入相同的ILP。我们提出的启发式方法，LB-Relax及其变体，使用LB的线性编程放松来选择社区。从经验上讲，LB-Relax及其变体的计算与LB一样有效，但运行速度更快。他们随时可以在几个ILP基准上实现最先进的性能。
Large Neighborhood Search (LNS) is a popular heuristic algorithm for solving combinatorial optimization problems (COP). It starts with an initial solution to the problem and iteratively improves it by searching a large neighborhood around the current best solution. LNS relies on heuristics to select neighborhoods to search in. In this paper, we focus on designing effective and efficient heuristics in LNS for integer linear programs (ILP) since a wide range of COPs can be represented as ILPs. Local Branching (LB) is a heuristic that selects the neighborhood that leads to the largest improvement over the current solution in each iteration of LNS. LB is often slow since it needs to solve an ILP of the same size as input. Our proposed heuristics, LB-RELAX and its variants, use the linear programming relaxation of LB to select neighborhoods. Empirically, LB-RELAX and its variants compute as effective neighborhoods as LB but run faster. They achieve state-of-the-art anytime performance on several ILP benchmarks.
