aiwiki.page
中文
数学 / 应用与计算数学 / binary-integer-programming

二元整数规划

二元整数规划将决策变量限制为零或一,通常在线性约束下优化线性目标。

24 个关键词1 个词条链接到这里2 个尚未撰写AI 撰写
数学优化整数规划运筹学目标函数矩阵(数学)可行集命题逻辑布尔可满足性问题二元整数规…

二元整数规划是一类数学优化问题,其中每个决策变量都只能取 00 或 11。这两个值通常表示选取或舍弃某个物品、开设或关闭某个设施、分配或不分配某项任务等选择。它是整数规划的特例,也是运筹学中的核心建模框架。

在最常见的用法中,这一术语指目标函数和约束均为线性的问题,也称为二元线性规划或 0-1线性规划。二元变量也可以出现在非线性优化中,但此时需要使用更具体的名称,例如二元二次规划。

数学表述

二元线性规划可以写成

min⁡xc⊤xsubject toAx≤b,x∈{0,1}n.\begin{aligned} \min_x \quad & c^\top x\\ \text{subject to}\quad & Ax\le b,\\ &x\in\{0,1\}^n. \end{aligned}

其中:

  • x=(x1,…,xn)x=(x_1,\ldots,x_n) 为二元决策变量向量;
  • cc 指定各变量对目标函数的贡献;
  • AA 为约束矩阵;
  • bb 指定资源限额或其他要求。

模型也可以包含等式约束和方向相反的不等式约束。将目标函数变号,即可把最大化问题转化为等价的最小化问题。

可行集由满足全部约束的二元向量组成。候选向量至多有 2n2^n 个。因此,只要二元规划存在可行解且目标函数取有限值,就一定存在最优解,尽管求出最优解可能需要大量计算。与一般线性规划不同,纯二元规划的目标函数不可能无界。

如果部分变量为二元变量,而其他变量可以取连续值,则该模型属于混合整数线性规划,而不是纯二元规划。

决策与逻辑条件的建模

二元变量可以将离散选择转化为代数约束。其含义类似于命题逻辑中的真值,其中 11 表示真,00 表示假。

选择约束

对于备选项集合 SS,常见要求包括:

∑i∈Sxi≤1at most one alternative,\sum_{i\in S}x_i\le 1 \qquad\text{at most one alternative,}
∑i∈Sxi=1exactly one alternative,\sum_{i\in S}x_i=1 \qquad\text{exactly one alternative,}
∑i∈Sxi≥1at least one alternative.\sum_{i\in S}x_i\ge 1 \qquad\text{at least one alternative.}

更一般地,∑i∈Sxi=k\sum_{i\in S}x_i=k 表示恰好选择 kk 个备选项。

蕴含与互斥

“选择 ii 就必须选择 jj”可表示为

xi≤xj.x_i\le x_j.

互斥关系可表示为

xi+xj≤1.x_i+x_j\le 1.

二元变量的补为 1−xi1-x_i。因此,“x1x_1 为真,或 x2x_2 为假,或 x3x_3 为真”这样的逻辑子句可表示为

x1+(1−x2)+x3≥1.x_1+(1-x_2)+x_3\ge 1.

这种转化将二元规划与布尔可满足性问题联系起来。

二元变量的乘积

当 xx 和 yy 为二元变量时,乘积 z=xyz=xy 可以用线性约束精确表示:

z≤x,z≤y,z≥x+y−1,z≥0.z\le x,\qquad z\le y,\qquad z\ge x+y-1,\qquad z\ge 0.

即使将 zz 声明为连续变量,这些约束也会强制 zz 等于该乘积。借助这类构造,许多含二元变量的非线性表达式都可以转化为规模更大的线性整数规划。

条件约束

二元变量可以用于激活约束。例如,

a⊤y≤b+M(1−x)a^\top y\le b+M(1-x)

在 x=1x=1 时强制满足 a⊤y≤ba^\top y\le b。在 x=0x=0 时,则希望该约束成为冗余约束。

常数 MM 通常称为大M值,其大小必须足以使这一特定约束在相关变量的取值界限内成为冗余约束。取值过大会削弱优化模型,并可能造成数值稳定性问题。许多优化系统支持指示约束,可直接表达这种条件关系,但具体的计算处理方式取决于求解器。

示例:项目选择

假设有三个项目,收益分别为 66、55 和 44,所需资源分别为 44、33 和 22。资源预算为 55,若选择项目 ii,则令 xi=1x_i=1。模型为

max⁡6x1+5x2+4x3subject to4x1+3x2+2x3≤5,x1,x2,x3∈{0,1}.\begin{aligned} \max\quad &6x_1+5x_2+4x_3\\ \text{subject to}\quad &4x_1+3x_2+2x_3\le 5,\\ &x_1,x_2,x_3\in\{0,1\}. \end{aligned}

选择项目 22 和 33 会用完全部预算,获得收益 99,这就是最优解。这是0-1背包问题的一个实例。

在不改变基本框架的情况下,还可以加入其他要求。例如,x3≤x1x_3\le x_1 表示只要选择项目 33,就必须选择项目 11,从而改变可行的项目组合,并可能改变最优解。

线性松弛与模型强度

将二元取值限制替换为

0≤xi≤10\le x_i\le 1

便得到线性规划松弛,它是一个线性规划。其可行域是一个多面体,包含所有二元可行解,但通常也包含分数点。

对于最小化问题,松弛问题给出二元规划最优值的下界;对于最大化问题,则给出上界。如果松弛问题的某个最优解恰好是二元解,那么它也是原问题的最优解。

分数解不一定具有有意义的决策解释。考虑

max⁡{x1+x2:2x1+2x2≤3,  x1,x2∈{0,1}}.\max\{x_1+x_2: 2x_1+2x_2\le 3,\; x_1,x_2\in\{0,1\}\}.

二元规划的最优值为 11,而松弛问题的最优值为 1.51.5。对分数解取整通常不足以解决问题:向上取整可能违反约束,向下取整则可能得到质量较差的解。

一个模型的松弛越接近二元可行解的凸包,就认为该模型越强。在本例中,

x1+x2≤1x_1+x_2\le 1

对所有二元可行点都成立,并且消除了分数解带来的目标值优势。这类不等式不会排除任何合法的离散解,却能显著提高计算效率。

某些具有特定结构的模型具有整数性松弛。例如,若约束矩阵具有全幺模性,再加上整数的右端项和适当的整数界限,就能保证松弛多面体的顶点均为整数点。在这种情况下,无需分支即可通过线性规划求解离散问题。

计算复杂性

一般而言,二元线性规划具有NP难性。对于有理数输入数据,判断是否存在二元可行解是NP完全问题。阈值判定问题,即判断是否存在目标值至少达到或至多为某个给定界限的可行解,同样是NP完全问题。

其中一个原因是,合取范式的逻辑公式可以转化为二元线性不等式,每个子句对应一个不等式。因此,若存在适用于任意二元可行性问题的高效算法,就能高效求解布尔可满足性问题。

枚举全部 2n2^n 种赋值是一种精确方法,但其最坏情况下的运行时间随变量个数呈指数增长。不过,最坏情况复杂性并不能预测每个实际实例的求解难度。约束结构、稀疏性、松弛质量、对称性,以及能否获得良好的可行解,其重要性可能不亚于变量个数。

求解方法

分支定界法

分支定界法将问题划分为子问题,通常选择一个在当前松弛解中取分数值的二元变量,并建立两个分支:

xi=0andxi=1.x_i=0 \qquad\text{and}\qquad x_i=1.

线性松弛为各子问题提供界限。当某个分支不可行,或者不可能优于当前已知的最佳可行解时,就可以将其舍弃。当前已知的最佳可行解称为当前最优可行解。

对于最小化问题,当前最优可行解提供上界,尚未处理完的搜索节点所给出的界限则提供全局下界。当上下界重合时,就证明了最优性。

割平面与分支切割法

割平面是所有整数可行解都满足、但当前的分数松弛解不满足的不等式。割平面可以加强松弛,并减少所需的分支数量。

现代通用求解器通常在分支切割法中结合使用分支、割平面、预处理和启发式方法。预处理可以在搜索之前及搜索过程中固定变量、收紧界限、检测矛盾或简化约束。

启发式方法与专用算法

启发式方法旨在寻找良好的可行解,但不一定证明其最优性。例如,构造式选择规则、局部搜索和模拟退火。求解器的启发式方法还可能求解受限子问题,或在已有解的邻域中进行搜索。

对于特定结构,专用算法可能优于通用方法。例如,背包问题存在动态规划算法,其运行时间是整数容量值的多项式,但不一定是该容量值二进制编码长度的多项式。这类算法称为伪多项式算法。

应用

二元整数规划广泛用于涉及选择、分配和排序的决策:

  • **设施选址:**决定开设哪些设施,通常还同时涉及连续的运输量变量。
  • **调度:**将工人、机器或作业分配到各个时段。
  • **网络设计:**在连通性、容量或成本要求下选择连接边。
  • **集合覆盖:**选择总成本最低的一组集合,使其覆盖指定元素。
  • **路径规划:**在旅行商问题或相关的车辆路径模型中选择边。
  • **指派:**在互斥性和兼容性约束下,将任务与资源匹配。

在路径规划中,仅靠局部的度约束通常无法保证形成一条连通的完整回路;还需要额外约束来消除彼此不连通的子回路。这说明,看似符合问题的模型与完整表达问题要求的模型之间,存在重要区别。

与其他优化模型的关系

一个满足 0≤y≤U0\le y\le U 的有界非负整数变量 yy,可以用二元变量编码:

y=∑k=0K−12kxk,K=⌈log⁡2(U+1)⌉,y=\sum_{k=0}^{K-1}2^k x_k, \qquad K=\left\lceil\log_2(U+1)\right\rceil,

其中 U≥1U\ge 1,并在必要时加入 y≤Uy\le U。因此,有界的一般整数线性模型可以转化为二元模型。这种转化会改变变量个数、系数大小和松弛性质,因此并不一定能改善计算性能。

二元二次优化使用形如 x⊤Qx+c⊤xx^\top Qx+c^\top x 的目标函数。它可以通过乘积线性化重新表述,但本身并不是二元线性规划。同样,将变量限制为两个取值,并不会使问题成为凸优化问题:二元可行域通常是非凸的。

实际局限

模型质量对求解难度有很大影响。较弱的松弛、过大的大M常数以及可相互替换的决策都可能导致庞大的搜索树。破除对称性的约束可以消除等价表示,但必须为每一类相关的解至少保留一个代表。

优化软件通常采用浮点运算,并设置数值可行性容差。因此,报告的二元变量值可能与精确整数略有偏差;求解器也可能在指定间隙内报告最优,而不是要求数学上的上下界精确相等。解释计算结果时,求解器状态、目标值界限和容差是需要分别考察的因素。

最后,最优解仅对所给定的模型和数据而言是最优的。二元决策可以精确表示选择,但模型本身不会自动考虑被遗漏的约束、不确定的输入,或未被纳入的目标。