English

运筹学学报 ›› 2015, Vol. 19 ›› Issue (4): 1-13.doi: 10.15960/j.cnki.issn.1007-6093.2015.04.001

• 运筹学 •    下一篇

基于分支割平面的一类无容量限制设施选址问题求解算法

安邦1, 程朋1,*   

  1. 1.清华大学自动化系, 北京 100084
  • 收稿日期:2014-09-03 出版日期:2015-12-15 发布日期:2015-12-15
  • 通讯作者: 程朋 chengp@tsinghua.edu.cn
  • 基金资助:

    国家自然科学基金(No.61179052)

 An algorithm for a class of uncapacitated facility location problem based on branch-and-cut method

AN Bang1,CHENG Peng1,*   

  1. 1.Department of Automation, Tsinghua University, Beijing 100084, China
  • Received:2014-09-03 Online:2015-12-15 Published:2015-12-15

PDF

920

被引次数

2

摘要：

无容量限制设施选址问题是经典的组合优化问题, 具有广泛的应用价值,然而该问题已被证明是NP难问题, 并且传统的分支定界方法求解速度较慢.研究以最大化总收益费用与总投建费用之差为目标的无容量限制设施选址问题,将其转化为节点包装问题,并根据模型的图形特点提出了新的合法不等式族------轴不等式族,经过严格的数学证明后得出轴不等式要强于原有的奇洞不等式. 同时,设计出切割不等式快速搜索算法嵌入到分支割平面方法中. 最后,通过实验验证了轴不等式族的强有效性,
以及分支割平面方法比分支定界方法求解速度快、节点数量少的优点.

关键词: 无容量限制设施选址问题, 分支割平面, 轴不等式

Abstract:

The uncapacitated facility location problem is a classic combinatorial optimization problem with wide applications. However, this problem had been proven to be NP-hard and the traditional solving method based on branch-and-bound is slow. In this paper, we studies a class of UFLP problem aiming at maximizing the gap between total income and total investment cost, we transform this problem into a node packing problem and propose a new family of valid inequalities-axis inequalities based on graphic features of the model, which are stronger than the odd-hole inequalities after a strict proof. We also design a fast searching algorithm for cut inequalities and embed it in the branch-and-cut method. In the end, strong validity of axis inequalities are validated by experiments. The experimental results also showed that compared with the branch-and-bound method, the branch-and-cut method can reduce the number of branch nodes as
well as speed up the solving process.

Key words: uncapacitated facility location problem, branch-and-cut, axis inequalities