整数规划

1. 基本概念
   整数规划是数学规划的一个重要分支，其核心特点是要求全部或部分决策变量的取值为整数。在标准的线性规划问题中，决策变量可以取任何实数。然而，在实际问题中，很多决策对象是不可分割的，例如需要安排多少台机器、派遣多少名员工、在某个地点是否建厂（是或否，对应0或1），这些都需要整数解。整数规划就是在包含线性约束条件和线性目标函数的基础上，增加了变量的整数性约束。

2. 问题分类
   根据整数性约束的范围，整数规划主要分为两类：

   • 纯整数规划：所有决策变量都被要求取整数值。
   • 混合整数规划：只有一部分决策变量被要求取整数值，其余变量可以是连续的。
     在整数规划中，一个极其重要且应用广泛的子类是0-1整数规划（或称二进制整数规划），其决策变量仅限于取0或1，常用于表示“是/否”、“开/关”、“选择/不选择”等逻辑决策。

3. 与线性规划的关系与复杂性
   整数规划问题可以看作是在其对应的线性规划松弛问题的可行域中，寻找满足整数要求的“格点”。线性规划松弛是指忽略原整数规划问题中的整数约束后得到的普通线性规划问题。
   尽管线性规划问题存在多项式时间复杂度的有效算法（如单纯形法、内点法），但整数规划在计算复杂性上属于NP-难问题。这意味着，在最坏情况下，不存在已知的多项式时间算法能精确求解所有整数规划问题。随着问题规模（变量和约束的数量）增大，求解时间可能呈指数级增长。

4. 常用求解方法
   由于精确求解大规模整数规划非常困难，研究者开发了多种方法，主要分为精确算法和启发式算法。

   • 精确算法：旨在找到问题的全局最优解。
     • 分支定界法：这是最主流的精确求解框架。其核心思想是“分而治之”：首先求解线性规划松弛问题，如果解不满足整数要求，则选择一个分数变量，将原问题分解为两个子问题（分支），分别强制该变量小于等于其下整数和大于等于其上整数。通过不断分支，并利用松弛问题的最优值来界定（剪枝）那些不可能包含最优整数解的子问题，从而避免枚举所有可能的整数解。
     • 割平面法：该方法首先求解线性规划松弛问题。如果得到的最优解是分数解，则设法为原问题增加一个新的线性约束条件（即“割平面”）。这个新约束能够“割掉”当前的分数最优解，但不会“割掉”任何可行的整数解。然后重新求解增加了新约束的线性规划问题，重复此过程，直到找到整数最优解。
   • 启发式算法：当问题规模太大，精确算法在可接受时间内无法求得最优解时，采用启发式算法来寻找高质量（接近最优）的可行解。这类算法不保证找到最优解，但通常效率较高。常见的方法包括遗传算法、模拟退火、禁忌搜索等。

5. 典型应用场景
   整数规划的应用极其广泛，几乎遍及所有需要优化决策的领域：

   • 物流与供应链：车辆路径规划（决定车队的最佳行驶路线）、设施选址（在何处建立仓库或工厂）。
   • 生产制造：生产计划与排程（安排机器、人员和订单）。
   • 金融：投资组合优化（在预算和风险约束下选择投资项目）。
   • 电信：网络设计（如光纤线路布局）和频率分配。
   • 人工智能：在机器学习模型中用于特征选择。