整数规划求解方法
简介
整数规划 (IP) 是一种数学优化问题，其中决策变量仅能取整数值。IP 比线性规划 (LP) 更难求解，因为整数约束会使可行解空间变得离散。
分支定界法
分支定界法是用于求解 IP 的最常用方法。该方法通过将可行解空间递归地划分为更小的子空间来工作。
分支：
选择一个连续决策变量并将其固定为整数。这将创建一个新问题的两个子问题，其中一个决策变量的值为向上舍入的整数，另一个为向下取整的整数。
定界：
对每个子问题求解 LP 松弛，该松弛是忽略整数约束的 IP 的线性近似。使用 LP 解来计算每个子问题的下界 (UB) 和上界 (LB)。
递归：
选择分支变量和相应子问题，其间隙 (UB - LB) 最小。重复分支和定界过程，直到所有子问题都已求解。
回溯：
一旦所有子问题都已求解，算法将回溯并选择具有最小上界的子问题。该子问题包含一个可行的整数解。
割平面法
割平面法是一种迭代方法，用于通过添加称为割平面的线性不等式来缩小 IP 的可行解空间。
初始化：
从 IP 的 LP 松弛开始。
寻找割平面：
检查 LP 解是否违反整数约束。如果违反，则使用 Gomory 切割平面技术生成一个割平面，该平面切断 LP 解并只包含可行的 IP 解。
添加割平面：
将割平面添加到 LP 松弛。
重复：
重复寻找和添加割平面的过程，直到 LP 解满足整数约束。
求解 LP：
现在 LP 松弛等效于 IP，因此可以求解以获得 IP 的可行整数解。
混合整数规划
混合整数规划 (MIP) 是 IP 的一种类型，其中一些决策变量为连续变量，而另一些为整数变量。求解 MIP 通常需要分支定界法和割平面法的组合。
启发式方法
对于大型或复杂 IP，求解可能需要很长时间。启发式方法，例如贪婪算法、禁忌搜索和模拟退火，可用于快速找到近似解。
应用
IP 在许多领域都有应用，包括：
生产计划
供应链管理
调度
金融建模
**整数规划求解方法****简介**整数规划 (IP) 是一种数学优化问题，其中决策变量仅能取整数值。IP 比线性规划 (LP) 更难求解，因为整数约束会使可行解空间变得离散。**分支定界法**分支定界法是用于求解 IP 的最常用方法。该方法通过将可行解空间递归地划分为更小的子空间来工作。* **分支：** 选择一个连续决策变量并将其固定为整数。这将创建一个新问题的两个子问题，其中一个决策变量的值为向上舍入的整数，另一个为向下取整的整数。 * **定界：** 对每个子问题求解 LP 松弛，该松弛是忽略整数约束的 IP 的线性近似。使用 LP 解来计算每个子问题的下界 (UB) 和上界 (LB)。 * **递归：** 选择分支变量和相应子问题，其间隙 (UB - LB) 最小。重复分支和定界过程，直到所有子问题都已求解。 * **回溯：** 一旦所有子问题都已求解，算法将回溯并选择具有最小上界的子问题。该子问题包含一个可行的整数解。**割平面法**割平面法是一种迭代方法，用于通过添加称为割平面的线性不等式来缩小 IP 的可行解空间。* **初始化：** 从 IP 的 LP 松弛开始。 * **寻找割平面：** 检查 LP 解是否违反整数约束。如果违反，则使用 Gomory 切割平面技术生成一个割平面，该平面切断 LP 解并只包含可行的 IP 解。 * **添加割平面：** 将割平面添加到 LP 松弛。 * **重复：** 重复寻找和添加割平面的过程，直到 LP 解满足整数约束。 * **求解 LP：** 现在 LP 松弛等效于 IP，因此可以求解以获得 IP 的可行整数解。**混合整数规划**混合整数规划 (MIP) 是 IP 的一种类型，其中一些决策变量为连续变量，而另一些为整数变量。求解 MIP 通常需要分支定界法和割平面法的组合。**启发式方法**对于大型或复杂 IP，求解可能需要很长时间。启发式方法，例如贪婪算法、禁忌搜索和模拟退火，可用于快速找到近似解。**应用**IP 在许多领域都有应用，包括：* 生产计划 * 供应链管理 * 调度 * 金融建模
