跳到主要导航 跳到搜索 跳到主要内容

An efficient branch-and-cut algorithm for the minimum covering location problem with distance constraints

  • Bo Rui Wang
  • , Wei Kun Chen*
  • , Yu Hai Zhang
  • , Jian Hua Yuan
  • , Yu Hong Dai
  • *此作品的通讯作者
  • Beijing University of Posts and Telecommunications
  • Beijing Institute of Technology
  • CAS - Academy of Mathematics and System Sciences
  • University of Chinese Academy of Sciences

科研成果: 期刊稿件 › 文章 › 同行评审

摘要

We consider the minimum covering location problem with distance constraints (MCLPDC), which attempts to locate a set of undesirable facilities subject to the minimum distance constraints between any pair of located facilities while minimizing the negative impact caused by these facilities. The mixed integer programming (MIP) formulations of the MCLPDC are difficult to be solved by state-of-the-art MIP solvers due to the poor linear programming (LP) relaxation and the large problem size. To bypass the difficulties, we propose two families of valid inequalities for the MCLPDC. The proposed inequalities can effectively strengthen the LP relaxation of the MCLPDC and enable to provide a compact MIP formulation for the MCLPDC that has a potentially much smaller problem size. Moreover, we propose an efficient branch-and-cut algorithm, which starts with the compact MIP formulation and separates the exponential family of inequalities on the fly. Computational results on benchmark instances show that thanks to the tight LP relaxation and small problem size of the formulation, the proposed branch-and-cut algorithm outperforms a state-of-the-art approach by at least one order of magnitude.

源语言英语
期刊Journal of Global Optimization
DOI
出版状态已接受/待刊 - 2025
已对外发布是

学术指纹

探究 'An efficient branch-and-cut algorithm for the minimum covering location problem with distance constraints' 的科研主题。它们共同构成独一无二的学术指纹。

引用此