流动等值面技术求解整数线性规划新算法

"本文介绍了一种新的算法，用于求解整数线性规划问题，该方法结合了流动等值面技术和原单纯形方法，并在必要时应用Gomory割平面来寻找整数可行解。这种方法既保留了割平面法保持整数可行解的优势，又具有对偶割平面法灵活使用割平面的优点。论文由燕子宗撰写，他在最优化理论方面有深入的研究。整数线性规划问题的解决通常依赖于割平面算法和分支定界技术，而新算法试图通过改进策略避免传统方法中的缺点，如割平面选择的单一性和可能导致的退化问题。该方法从一个初始的整数可行解开始，逐步寻找更优的解，直至找到原问题的最优解。" 整数线性规划是运筹学中的一个重要领域，涉及到寻找满足一系列线性约束的整数解，以最大化或最小化一个线性目标函数。传统的解决方法包括割平面算法和分支定界法，其中割平面算法通过引入割平面逐步缩小问题的松弛解的可行域，而分支定界则通过分支和约束相结合的方式加速收敛。 本文提出的新型算法对原始割平面法进行了改良。首先，它采用流动等值面技术，这是一种分析线性规划问题的有效工具，能够帮助构建和理解问题的几何结构。其次，新算法从一个整数可行解开始，而不是从松弛问题的解开始，这有助于直接寻找整数解，减少了转化过程中的损失。再者，当需要寻找新的整数可行解时，Gomory割平面技术被应用，这是一种经典且强大的割平面生成方法，可以有效地排除非整数解。 传统割平面法的一个主要问题是其选择割平面的方式可能导致算法的退化，即解的质量没有显著改善。新算法试图通过更加灵活的策略避免这一问题，同时借鉴了对偶割平面法的灵活性，能够在处理割平面时更加高效。尽管有Young的原割平面算法和其他改进尝试，但它们在计算效率上仍存在不足。燕子宗的新方法旨在克服这些限制，提供一种更有效、更直接的整数线性规划求解策略。 这篇论文对整数线性规划的求解算法做出了创新性的贡献，通过融合不同方法的优点，提高了寻找整数最优解的速度和准确性。这对于实际应用中需要解决大规模或复杂整数线性规划问题的领域，如资源分配、生产计划和网络设计等，具有重要的理论和实践意义。