Branch-and-cut algorithms are widely used for solving integer programming (IP) problems by integrating the branch-and-bound method with the cutting plane approach. A critical component of such algorithms is the handling of subtour elimination constraints (SECs), which ensure connectivity in various combinatorial optimization problems. However, key design choices in the separation and addition of violated SECs significantly impact computational performance. Despite their importance, these choices have not been thoroughly analyzed in the literature. This paper presents an empirical analysis of different strategies for identifying and incorporating SECs in branch-and-cut algorithms. Specifically, we investigate (i) the effectiveness of exact versus heuristic separation procedures, (ii) whether selecting all, a random one, or only the most-violated inequalities leads to better performance, and (iii) whether adding SECs as global or local cuts enhances computational efficiency. Our experiments, conducted on four well-known integer programs and 268 instances, provide valuable insights into optimizing branch-and-cut algorithms for integer programming applications.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Empirical Analysis of Strategies for Identifying and Incorporating Subtour Elimination Constraints in Branch-and-Cut Algorithms for Integer Programming

  • Quoc-Trung Bui,
  • Quang-Dung Pham

摘要

Branch-and-cut algorithms are widely used for solving integer programming (IP) problems by integrating the branch-and-bound method with the cutting plane approach. A critical component of such algorithms is the handling of subtour elimination constraints (SECs), which ensure connectivity in various combinatorial optimization problems. However, key design choices in the separation and addition of violated SECs significantly impact computational performance. Despite their importance, these choices have not been thoroughly analyzed in the literature. This paper presents an empirical analysis of different strategies for identifying and incorporating SECs in branch-and-cut algorithms. Specifically, we investigate (i) the effectiveness of exact versus heuristic separation procedures, (ii) whether selecting all, a random one, or only the most-violated inequalities leads to better performance, and (iii) whether adding SECs as global or local cuts enhances computational efficiency. Our experiments, conducted on four well-known integer programs and 268 instances, provide valuable insights into optimizing branch-and-cut algorithms for integer programming applications.