摘要

0-1整数规划作为运筹学与组合优化领域的核心分支，在管理科学、工程设计和人工智能等众多学科中扮演着不可或缺的角色。其决策变量的二元特性使得模型能够精确刻画现实世界中“是/否”“选择/不选择”等本质离散决策，但同时也带来了计算复杂性的根本挑战——该类问题已被证明为NP-难问题。在求解0-1整数规划的各种方法中，分支定界法以其系统性搜索与智能剪枝相结合的独特优势，成为最成功、应用最广泛的精确算法框架之一。本文从0-1整数规划的基本理论出发，系统阐述分支定界法的算法原理、关键组件与实现技术，深入讨论可行性泵、割平面法等现代改进策略，并通过多个典型应用案例验证算法的有效性与实用性，最后探讨该领域的前沿发展方向。本文旨在为数学建模竞赛参赛者提供既有理论深度又有实践指导的综合性参考。

关键词：0-1整数规划；分支定界法；NP-难问题；组合优化；线性规划松弛；剪枝策略；数学建模

目录

摘要

1 引言

1.1 研究背景

1.2 研究意义

1.3 文章结构安排

2 0-1整数规划理论基础

2.1 数学模型与标准形式

2.2 0-1变量的建模能力

2.3 几何解释与组合结构

2.4 计算复杂性分析

3 分支定界法：原理与实现

3.1 算法基本思想

3.2 算法框架与流程

3.3 关键组件详解

3.3.1 分支策略

3.3.2 节点选择策略

3.3.3 剪枝规则

3.3.4 初始可行解的获取

3.4 数值示例：逐步演示

4 分支定界法的现代改进

4.1 预处理技术

4.2 可行性泵

4.3 割平面法

4.4 启发式算法与元启发式

4.5 并行化策略

5 典型应用案例分析

5.1 案例一：多项目投资组合选择

5.2 案例二：应急设施选址问题

5.3 案例三：旅行商问题

5.4 案例四：机器学习中的特征选择

6 前沿发展与未来展望

6.1 大规模分布式求解

6.2 机器学习辅助的分支定界

6.3 量子计算的影响

6.4 总结与展望

参考文献

1 引言

1.1 研究背景

在人类社会的各个领域，决策问题无处不在。从企业的生产计划与物流调度，到国家的资源配置与政策制定，再到人工智能中的特征选择与路径规划，决策者总希望在众多可行方案中选出最优者。数学规划为此提供了强有力的定量分析工具，其中整数规划（Integer Programming，IP）因能够自然处理离散决策变量而占据特殊地位。

整数规划的历史可追溯至20世纪50年代。1954年，Dantzig、Fulkerson和Johnson利用割平面方法成功求解了49个城市的旅行商问题，这一里程碑标志着整数规划作为独立学科的诞生。1958年，Gomory提出了第一个通用的割平面算法，为整数规划的求解奠定了理论基础。然而，真正使整数规划走向广泛应用的是1960年Land和Doig提出的分支定界法（Branch and Bound），该方法以其直观的几何解释和灵活的框架设计，迅速成为求解整数规划问题的标准方法。

0-1整数规划是整数规划中最基本也最重要的特殊情形，其中每个变量仅取0或1两个值。这种简单的二元结构看似限制性极强，实则具有惊人的表达能力——任何有界整数变量都可以通过二进制展开转化为多个0-1变量，而大量实际问题天然具有“是/否”决策的本质特征。正是这种表达能力与结构简洁性的完美结合，使得0-1整数规划成为数学建模中最常用的工具之一。<