0-1 规划

一、直观理解：用开关变量编码「做或不做」

0-1 规划（Binary Integer Programming）是整数规划的特殊情形：决策变量只取 $0$ 或 $1$ 。可以把每个变量想成开关：

$x_j=1$ ：选择第 $j$ 个方案 / 打开设施 / 选中物品；
$x_j=0$ ：不选。

很多看似「逻辑题」的优化问题，一旦引入 0-1 变量，就能写成线性约束。例如：

背包：带或不带某件物品；
选址：建或不建某仓库；
指派：某人是否做某任务；
路径：是否使用某条边（TSP 的边变量）。

0-1 变量也能配合大 M 法表达「若 A 则 B」「至多选 K 个」等规则，因此是组合优化建模的核心语言。能写成 0-1 线性模型时，优先用 intlinprog 精确求解。

二、适用场景与优缺点

类型	说明
适用场景	选址、指派、背包、集合覆盖/划分、项目是否立项、线路是否开通、设备开关机（与连续变量配合时见 MILP）。
核心优点	逻辑表达清晰；中小规模可全局最优；大量经典不等式与紧化技巧；与图论问题联系紧密。
局限与缺点	变量多时组合爆炸；大 M 过松会严重拖慢；非线性逻辑若线性化不当会引入数值问题；对称性常见。

使用前确认：

每个 0-1 变量的业务含义是否单一清晰；
逻辑约束是否都已写成线性不等式；
大 M 能否取「刚好够大」的业务上界；
问题规模（变量数、约束数）是否适合精确求解。

三、核心原理：线性逻辑与组合约束

1. 基本模型

\begin{aligned} \min\quad & c^\mathsf{T}x \\ \text{s.t.}\quad & Ax\le b \\ & x\in\{0,1\}^n \end{aligned}

最大化、等式约束与一般 IP 相同。MATLAB 中对 intcon 指定的变量设 lb=0, ub=1 即表示 0-1。

2. 常用逻辑线性化

逻辑含义	线性写法（示意）
至多选 $K$ 个	$\sum_j x_j\le K$
至少选 $K$ 个	$\sum_j x_j\ge K$
恰好选 $K$ 个	$\sum_j x_j=K$
若 $x=1$ 则 $y=1$	$y\ge x$
若 $x=1$ 则 $y=0$	$x+y\le 1$
$x,y$ 不同时为 1	$x+y\le 1$
$z=x\land y$ （ $x,y,z\in\{0,1\}$ ）	$z\le x,\ z\le y,\ z\ge x+y-1$
$z=x\lor y$	$z\ge x,\ z\ge y,\ z\le x+y$

3. 大 M 与连续变量联动

「若开厂（ $y=1$ ）则产量 $x\le U$ ，否则 $x=0$ 」：

0\le x\le U y,\quad y\in\{0,1\}

$U$ 应取产量真实上界。 $U$ 过大 → 松弛弱 → 分支慢。

4. 经典问题：0-1 背包

\max\sum_j v_j x_j\quad \text{s.t.}\ \sum_j w_j x_j\le W,\ x_j\in\{0,1\}

小规模可用 DP 或 IP；大规模 IP 仍常很快，因约束结构简单。

5. 集合覆盖

客户 $i$ 可被集合 $S_j$ 覆盖，费用 $c_j$ ：

\min\sum_j c_j x_j\quad \text{s.t.}\ \sum_{j:i\in S_j}x_j\ge 1,\ x_j\in\{0,1\}

四、关键决策

1. 变量定义决定模型难度

同一问题可有多种 0-1 编码（点选 vs 边选）。优先选约束好写、对称性少、LP 松弛紧的定义。

2. 大 M 能小则小

用业务最大可能值，或引入多个分层约束，避免 $10^{9}$ 量级。

3. 破对称

若设施完全同质，可加 $x_1\ge x_2\ge\cdots$ 或按指标排序，减少等价排列。

4. 先松弛再整数

查看 LP 松弛是否接近 0-1；若大量 $0.5$ ，说明公式可能过松，需加有效不等式。

5. 与启发式的分工

精确法超时后，可用贪心、局部搜索提供初始可行解（warm start），而不是直接放弃数学模型。

五、MATLAB 示例

例 1：0-1 背包

v = [10; 8; 15; 6; 12];   % 价值
w = [5;  4;  8; 3;  6];   % 重量
W = 15;
n = numel(v);

f = -v;                   % 最大化价值
A = w';
b = W;
lb = zeros(n, 1);
ub = ones(n, 1);
intcon = 1:n;

opts = optimoptions("intlinprog", "Display", "final");
[x, fval, exitflag, output] = intlinprog( ...
    f, intcon, A, b, [], [], lb, ub, opts);

fprintf("选中物品：");
disp(find(x > 0.5)');
fprintf("总重量=%g，总价值=%g，gap=%g\n", ...
    w' * x, -fval, output.relativegap);

例 2：设施选址（简化无容量）

3 个候选仓，4 个客户；建仓固定成本 + 服务成本，每客户恰好由一个已建仓服务。

% y_j: 是否建仓 j；x_ij: 客户 i 是否由仓 j 服务
fixed = [12; 10; 15];
% service(i,j) 成本
service = [
    4, 6, 9;
    5, 4, 7;
    6, 3, 5;
    8, 7, 4
];
m = 4; n = 3;  % 客户数、仓数

% 变量顺序：[x11..x1n, x21..x2n, ..., xm1..xmn, y1..yn]
numX = m * n;
numY = n;
Nvar = numX + numY;
f = [service'(:); fixed];  % 列优先展开 service' 需与索引一致
% 更稳妥：按 (i,j) 双重循环填目标
f = zeros(Nvar, 1);
for i = 1:m
    for j = 1:n
        f((i-1)*n + j) = service(i, j);
    end
end
f(numX+1:end) = fixed;

% 约束1：每个客户恰好一个仓
Aeq = zeros(m, Nvar);
beq = ones(m, 1);
for i = 1:m
    Aeq(i, (i-1)*n+1:i*n) = 1;
end

% 约束2：x_ij <= y_j
A = zeros(m*n, Nvar);
b = zeros(m*n, 1);
row = 0;
for i = 1:m
    for j = 1:n
        row = row + 1;
        A(row, (i-1)*n + j) = 1;
        A(row, numX + j) = -1;
    end
end

lb = zeros(Nvar, 1);
ub = ones(Nvar, 1);
intcon = 1:Nvar;

[xsol, fval, ef, out] = intlinprog(f, intcon, A, b, Aeq, beq, lb, ub);
X = reshape(xsol(1:numX), n, m)';  % m x n
Y = xsol(numX+1:end);

fprintf("exitflag=%d, 总成本=%g, gap=%g\n", ef, fval, out.relativegap);
disp("建仓方案 y："); disp(Y');
disp("服务矩阵 x："); disp(X);

六、如何解释结果

报告要点：

每个 0-1 变量的含义与最优 0/1 取值；
目标值的业务解释（总价值、总成本、覆盖数）；
关键逻辑约束是否按预期激活（例如选中了哪些设施）；
求解状态与相对间隙；
LP 松弛对照：分数解说明哪些决策「摇摆」；
若有多种最优，说明并列方案及破除对称后的选择。

避免只贴一串 0/1。应写成：「在仓库 1、3 建设，客户分配为……，固定成本 27，服务成本 18，合计 45。」

七、常见误区

1. 用连续 $[0,1]$ 代替 0-1 却不说明

LP 松弛的分数解不是合法开关决策。只有证明全幺模等特殊结构时，松弛顶点才自动整数。

2. 大 M 随意取极大

导致数值不稳与弱界。应取最小充分大的业务常数。

3. 逻辑漏写

只写费用不写「未建仓不能服务」，会得到「空中楼阁」式最优。每个 if-then 都要落成不等式。

4. 把二次 0-1 项直接相乘

$x_i x_j$ 需引入新变量并线性化，否则不是 0-1 线性规划。

5. 规模很大仍坚持默认参数硬刚

应加强割、设时限、给初始解，或分解问题；必要时才用启发式兜底，并报告与 IP 下界的差距。

八、小结

0-1 规划的核心思想可以概括为：

用取值仅 0 或 1 的变量编码离散选择，把逻辑与组合关系写成线性约束，在精确求解器中求全局最优（或可证明间隙的近优）。

它是选址、背包、指派、覆盖等题型的首选建模语言。写好变量含义、收紧大 M、报告间隙与方案解释，比堆砌算法名词更重要。与连续产量、流量联立时，扩展为混合整数线性规划。

一、直观理解：用开关变量编码「做或不做」​

二、适用场景与优缺点​

三、核心原理：线性逻辑与组合约束​

1. 基本模型​

2. 常用逻辑线性化​

3. 大 M 与连续变量联动​

4. 经典问题：0-1 背包​

5. 集合覆盖​

四、关键决策​

1. 变量定义决定模型难度​

2. 大 M 能小则小​

3. 破对称​

4. 先松弛再整数​

5. 与启发式的分工​

五、MATLAB 示例​

例 1：0-1 背包​

例 2：设施选址（简化无容量）​

六、如何解释结果​

七、常见误区​

1. 用连续 [0,1][0,1][0,1] 代替 0-1 却不说明​

2. 大 M 随意取极大​

3. 逻辑漏写​

4. 把二次 0-1 项直接相乘​

5. 规模很大仍坚持默认参数硬刚​

八、小结​