MIP对偶退化性：全面计算分析与新度量

混合整数规划对偶退化性是优化理论中的一个重要概念，它涉及在解决混合整数线性规划（MIP）时，由于对偶问题中存在多个最优基导致的问题特征。对偶简并性指的是即使在MIP中存在多个最优解，但对应的线性规划（LP）松弛可能产生相同的最优值，这可能导致求解过程中的复杂性增加，因为不同的最优基会指导算法采用不同的分支策略，从而可能找到不同的解决方案。 本研究论文由杰拉尔德·甘拉特、蒂莫·贝特霍尔德和多梅尼科·萨瓦宁共同完成，发表于《欧洲计算优化期刊》(EUROJournal on Computational Optimization) 2020年第8期。他们对一项著名公共MIP实例集进行了深入的计算分析，旨在回答一系列关键问题：哪些实例受到对偶退化的影响，这些退化如何影响模型的分支策略，是通过增加还是减少变量来体现的，以及能否识别不同类型且具有简并性的MIP问题。 为了量化和理解对偶退化的影响，作者引入了一个新的度量——最优面的可变约束比，该指标衡量了基础中一个基本变量发生旋转的可能性。这个度量有助于评估在分枝定界算法中，随着最佳面的LP松弛投影到个体变量的变化，对搜索树结构和分支候选选择的影响程度。 论文的贡献包括了对对偶简并性存在的全面统计分析，以及对解决策略的实际影响的深入探讨。通过对这一现象的研究，论文不仅提供了理论洞察，还可能为改进MIP求解算法的设计提供实用指导，帮助优化算法在处理此类复杂问题时更加高效。 这篇论文的重要性在于其对混合整数规划求解中的核心挑战进行了系统性的定量分析，为提高MIP求解的效率和稳定性提供了有价值的数据支持和理论依据。