Cut-Based Conflict Analysis in Mixed Integer Programming

doi:10.1287/ijoc.2024.0999

Cut-Based Conflict Analysis in Mixed Integer Programming

2025-11-01

0

PRE

AI

DOI：10.1287/ijoc.2024.0999

原文链接

原文求助

摘要

En 中文

近二十年来，混合整数规划（MIP）求解器一直采用基于图的冲突分析，在分支定界搜索过程中从局部不可行性中学习。在本文中，我们通过使用受伪布尔优化冲突驱动求解器发展启发而得到的割平面推理方法，改进了MIP冲突分析。用MIP术语表述，这种冲突分析可以理解为一系列线性组合、整数舍入和割平面生成。我们利用这种MIP视角设计了一种基于混合整数舍入割的新冲突分析算法，该算法在理论上优于使用Chvatal-Gomory割的伪布尔优化领域当前最佳方法。此外，我们将这种基于割的冲突分析从纯二进制规划扩展到混合二进制规划，并在有限形式下扩展到包含整数变量的通用MIP。我们在开源MIP求解器Solving Constraint Integer Programs（SCIP）中实现了基于割的冲突分析，并在MIPLIB2017中的大量多样化MIP实例集上进行了测试。我们的实验结果表明，新算法在运行时间、搜索树节点数和已解决问题实例数方面提升了SCIP的默认性能。

Keyword:

mixed integer linear programming

infeasibility analysis

conflict analysis

pseudo-Boolean solving and optimization

cutting planes proof system

Cut-Based Conflict Analysis in Mixed Integer Programming

摘要

期刊

机构