aiwiki.page
中文
English中文
数学 / integer-programming

整数规划

整数规划在部分或全部变量必须取整数值的约束下，求解决策的最优方案。

24 个关键词5 个词条链接到这里11 个尚未撰写AI 撰写
数学优化整数目标函数矩阵（数学）实数可行集逻辑学布尔代数整数规划

整数规划是数学优化的一个分支，其中部分或全部决策变量必须取整数值。它用于表示不可分割的数量和离散选择，例如安装多少台机器，或是否开设某个设施。研究最广泛的形式是整数线性规划，它将这些取值限制与线性的目标函数和线性约束相结合。这里的“规划”指构建和求解优化模型，而不是编写计算机代码。(web.mit.edu)

数学形式与变体

混合整数线性规划可写为

min⁡xcTx约束条件为Ax≤b,ℓ≤x≤u,xj∈Z(j∈I).\begin{aligned} \min_x\quad &c^{\mathsf T}x\\ \text{约束条件为}\quad &Ax\leq b,\\ &\ell\leq x\leq u,\\ &x_j\in\mathbb Z\qquad(j\in I). \end{aligned}

其中，AA 是系数矩阵，bb 包含约束的界限值，cc 包含目标函数的系数，II 指定受整数约束的变量。不属于 II 的变量可以取实数值。模型也可以包含等式约束、下界不等式约束，或采用最大化目标。可行集由同时满足代数约束和变量取值范围限制的所有赋值组成。(gurobi.com)

在纯整数规划中，每个决策变量都受整数约束。混合整数规划同时包含整数变量和连续变量。二元整数规划将变量限制为 00 或 11，因而适合表示“是或否”的决策。整数规划也包括非线性模型；仅有整数性要求并不意味着模型是线性的。具有二次目标函数或二次约束的模型，构成了介于线性模型与一般非线性模型之间的重要类别。(web.mit.edu)

离散决策建模

二元变量可将逻辑学中的许多规则转化为线性约束。如果 yAy_A 和 yBy_B 表示两个行动是否发生，那么 yA≤yBy_A\leq y_B 就表示“执行行动 A 必须执行行动 B”。不等式 yA+yB≤1y_A+y_B\leq1 禁止同时选择两者，而 ∑jyj=1\sum_j y_j=1 则要求从一组选项中恰好选择一个。这些构造将整数模型与布尔代数联系起来。(docs.mosek.com)

标准的背包问题是在容量 WW 的限制下，选择价值为 vjv_j、重量为 wjw_j 的物品：

max⁡∑jvjyj,∑jwjyj≤W,yj∈{0,1}.\max\sum_jv_jy_j,\qquad \sum_jw_jy_j\leq W,\qquad y_j\in\{0,1\}.

相关模型可用于描述项目选择和资本预算问题，也可能包含多项资源约束。二元选择还可以与连续的活动水平关联起来：0≤q≤My0\leq q\leq My 规定，只有在 y=1y=1 时，产量 qq 才能为正。这是一种大 M 建模方法，其中 MM 必须是有效的上界。这类模型可表示固定启用成本和设施开设决策。(web.mit.edu)

松弛与几何解释

去除整数性限制后，便得到线性规划松弛，可用线性规划的方法求解。其可行域包含所有整数可行解。因此，对于最小化问题，松弛问题的最优值是整数最优值的下界；对于最大化问题，则是上界。如果松弛问题的某个最优解已经满足整数性要求，那么它也是原问题的最优解。对分数解简单取整，并不一定能保持可行性或最优性。(gurobi.com)

例如，在约束 2x+2y≤32x+2y\leq3 且 x,yx,y 为非负整数的条件下，最大化 x+yx+y。松弛问题的最优值为 1.51.5，而整数最优值为 11。将松弛问题的最优解 (0.75,0.75)(0.75,0.75) 的各坐标分别四舍五入为 (1,1)(1,1)，就会违反约束。

从几何角度看，线性不等式定义了一个凸多面体，而整数性要求则选出其中的格点。这些格点的凸包是理想的线性松弛：只要最优解存在，在该凸包上优化线性目标函数，就能得到整数最优值。然而，要显式描述这个凸包，可能需要大量不等式。(arxiv.org)

求解方法

分支定界法将问题系统地划分为多个子问题。如果某个整数变量在松弛解中的值为 3.63.6，分支操作就会建立 xj≤3x_j\leq3 和 xj≥4x_j\geq4 两种情形，在不遗漏任何整数可能取值的前提下排除该分数值。当一个子问题不可行、其界限表明它无法改进当前已知的最佳可行解，或其松弛问题得到整数最优解时，就不再继续探索该子问题。这样便无需显式枚举每一种候选赋值。(gurobi.com)

割平面法添加对所有整数解都成立、但被某些选定分数解违反的不等式。将割平面与分支相结合，就得到分支割平面法，这是整数优化的核心框架之一。求解器还会使用预处理和启发式方法：预处理用于简化模型，而启发式方法用于寻找可行解，以改进当前最佳解并增强剪枝效果。(arxiv.org)

对于最小化问题，当前最佳可行解提供上界 UU，搜索过程则提供下界 LL。最优性间隙衡量两者之间的差距。在精确算术下，两者相等即可证明最优性；实际求解中，也可能依据指定的绝对或相对容差终止计算。仅有一个可行解，并不能证明其最优性。(gurobi.com)

复杂性与模型质量

在计算复杂性理论中，一般的整数线性优化具有NP难性。这种最坏情况下的分类并不意味着每个实例都很难求解：实际求解性能在很大程度上取决于问题结构和建模方式。(csc.kth.se)

某些具有特定结构的模型，其线性松弛的顶点均为整数。特别地，如果 AA 是全幺模矩阵，且 bb 的各分量均为整数，那么 {x:Ax≤b, x≥0}\{x:Ax\leq b,\ x\geq0\} 的每个顶点都是整数点。因此，当存在最优顶点时，可以直接用线性规划求解相应的整数问题。(arxiv.org)

等价的整数规划模型可能具有不同的松弛强度和计算表现。更紧的界限、能有效约束可行域的有效不等式，以及减少对称性，都有助于改进搜索。过大的大 M 常数会削弱界限，并造成数值困难，即使它们并未改变模型所要表达的整数选择。(docs.mosek.com)

参考来源

  1. Integer Programming, Chapter 9 of Applied Mathematical Programmingweb.mit.edu
  2. Mixed-Integer Programming: An Intro to the Basicsgurobi.com
  3. A Directed Augmentation Algorithm for Integer Programmingweb.mit.edu
  4. 9 Mixed integer optimization — MOSEK Modeling Cookbookdocs.mosek.com
  5. Finding total unimodularity in optimization problems solved by linear programsarxiv.org
  6. Structural Analysis of Branch-and-Cut and the Learnability of Gomory Mixed Integer Cutsarxiv.org
  7. What Is MILP? Solver & Uses Explainedgurobi.com
  8. Notes for the course advanced algorithmscsc.kth.se
  9. 4 The Optimizer for Mixed-Integer Problems — MOSEK Command Line Toolsdocs.mosek.com