摘要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整数规划成为数学建模中最常用的工具之一。