整数和逻辑建模

整数约束允许您创建具有以下重要特征的模型：

蕴涵，例如“如果条件 A 成立，则条件 B 成立”。
交易成本或设置成本，例如“如果我购买 0 件商品，则该商品的成本为 0，但如果我购买超过 0 件，则每件商品的成本为 $A 交易成本加上 $B”。请参阅示例：固定成本。
逻辑约束，例如“气闸门 A 和门 B 不能同时打开”。

许多建模问题等同于使用指示变量的逻辑模型。本主题介绍如何使用指示变量和逻辑模型。这些模型基于Big-M表示，其中假定变量 x 和常数 M 满足不等式 –M ≤ x ≤ M。

回想一下，优化中的约束有一个隐含的“和”。当 c1、c2 和 c3 这三个约束均满足时，约束 c1、c2 和 c3 也得到满足。

大 M 表示

假设有一个连续变量 x，其上界为常数 M：

x ≤ M.

您想要将二元指示变量 z 与 x 关联起来，以便每当 x > 0 时都会出现 z = 1。为此，请使用大 M 表示并加入约束：

x ≤ M z.

这个约束确保只要有 x > 0，就必然有 z = 1。Big-M 表示具有更多的应用，如使用实函数和二元指示变量表达逻辑约束中所述。

基本问题：水库流量

假设您想要用整数时间对水库进行建模。在固定范围内的每个正整数时间 t，水库可以接受水量 xin(t)，或排出水量 xout(t)，连续不断的进水或出水，直至最大值 M。您的模型应该强制执行“如果 xin(t) > 0 则 xout(t) = 0，如果 xout(t) > 0 则 xin(t) = 0”。您怎样模拟这一约束？一种方法是限制

xin(t) * xout(t) = 0.

然而，这种约束导致问题变得非线性，求解器通常难以处理这种类型的约束。

实现约束的更好方法是使用指示二元变量 zin(t)，每当 xin(t) > 0 时为 1，以及类似的二元变量 zout(t)，每当 xout(t) > 0 时为 1。假设您有这样的变量，添加约束

zin(t) + zout(t) ≤ 1,

这确保了 xin(t) 和 xout(t) 不会同时为正数。

为了确保 xin(t) > 0 时 zin(t) = 1，请使用 Big-M 表示。假设对于所有 t，xin(t) 的上下界均为正数 M。包括约束

xin(t) ≤ M*zin(t).

为了确保每当 xin(t) = 0 时 zin(t) = 0，请在目标函数中包含 zin(t)。通过这种方式，最小化目标函数会使 zin(t) 尽可能为零。

类似地，要连接 zout(t) 和 xout(t)，请合并约束

xout(t) <= M*zout(t).

总之，为了强制执行 xin(t) 和 xout(t) 不能同时为正的约束，需要为每个时间 t 创建两个二元变量 zin(t) 和 zout(t)，并包含以下三个约束：

xin(t) <= M*zin(t) % Ensures that zin(t) = 1 whenever xin(t) > 0.

xout(t) <= M*zout(t) % Ensures that zout(t) = 1 whenever xout(t) > 0.

zin(t) + zout(t) <= 1 % Ensures that zin(t) and zout(t) are not both positive.

基于问题的方法中的 MATLAB^® 命令如下：

T = 50; % Number of times
M = 40; % Maximum size of x variables
xin = optimvar('xin',T,'LowerBound',0,'UpperBound',M);
xout = optimvar('xout',T,'LowerBound',0,'UpperBound',M);
zin = optimvar('zin',T,'Type','integer','LowerBound',0,'UpperBound',1);
zout = optimvar('zout',T,'Type','integer','LowerBound',0,'UpperBound',1);
prob = optimproblem;

xinzin = xin <= M*zin;
xoutzout = xout <= M*zout;
zinzout = zin + zout <= 1;
prob.Constraints.xinzin = xinzin;
prob.Constraints.xoutzout = xoutzout;
prob.Constraints.zinzout = zinzout;

prob.Objective = sum(zin + zout);

请注意以下事项：

所有约束都是长度为 T 的约束向量，优化变量和指示变量也是如此。
所有约束都是用单个语句定义的，而不是循环定义的，这可以提供最佳的性能。

使用二元变量表达逻辑约束

本节包含逻辑语句和带有二元变量的相应 MATLAB 命令。这些语句假设变量 z、w 和 f 是二元优化变量，这意味着每个变量都有类型 "integer"、下界 0 和上界 1。

描述	逻辑语句	MATLAB 命令
`z` 和 `w` 具有相反的值	`z = not w`	z = 1 - w;
`z` 或 `w` 中至少有一个为真	`z or w`	z + w >= 1;
`z` 或 `w` 中最多有一个为真	`(not z) or (not w)`	z + w <= 1;
当 `z` 为真或 `w` 为真时，`f` 也为真	`f` = `z or w`	f >= z; f >= w; f <= z + w;
当 `z` 和 `w` 同时为真时，`f` 才为真	`f` = `z and w`	f <= z; f <= w; f >= z + w - 1;
当 `z` 或 `w` 之一为真时，`f` 也为真	`f` = `z xor w`	f >= z - w; f >= w - z; f <= z + w; f <= 2 - (z + w);

使用实函数和二元指示变量表达逻辑约束

本节连接一个实数函数 g(x)和一个二元变量 z。通常，您会将 z 引入到问题中作为指示变量来模拟问题的某些方面，例如 g(x) > 0 何时发生的指示。所有这些约束均基于大 M 表示。

假设常数 M 和函数 g(x) 满足边界

–M ≤ g(x) ≤ M.

条件	约束代码
如果 z = 1 则 g(x) ≤ 0	g(x) <= M*(1 - z);
如果 z = 1 则 g(x) ≥ 0	g(x) >= -M*(1 - z);
如果 z = 1 则 g(x) = 0	g(x) <= M(1 - z); g(x) >= -M(1 - z);
如果 g(x) ≤ 0 则 z = 1	g(x) >= -M*z;
如果 g(x) ≥ 0 则 z = 1	g(x) <= M*z;
如果 g(x) > 0 则 z = 1 如果 g(x) < 0 则 z = 0	创建一个新的二元变量 `z1` 来指示 g(x) < 0。 g(x) <= Mz; g(x) >= -Mz1; z + z1 == 1; 当 g(x) = 0 时，此表示不确定。

结合逻辑约束来创建新公式

使用先前的逻辑约束和二元指示变量来创建实现新公式的代码。

条件约束代码

条件	约束代码
对于满足边界约束 M 的标量函数 g(x) 和 h(x)，实现条件：如果 g(x) ≥ 0 则 h(x) ≥ 0	引入一个二元指示变量 `z` ，指示 g(x) ≥ 0。然后引入约束：如果 z = 1 则 h(x) ≥ 0。 g(x) <= Mz; h(x) >= -M(1 - z);
g(x) = z*x 其中 z 是二元变量	将此条件表示为两个约束：如果 z = 1 则 g(x) - x = 0 如果 z = 0 则 g(x) = 0 g(x) <= x + M(1-z); g(x) >= x - M(1-z); g(x) <= Mz; g(x) >= -Mz;

对于满足边界约束 M 的标量函数 g(x) 和 h(x)，实现条件：

如果 g(x) ≥ 0 则 h(x) ≥ 0

引入一个二元指示变量 z ，指示 g(x) ≥ 0。然后引入约束：如果 z = 1 则 h(x) ≥ 0。

g(x) <= M*z;
h(x) >= -M*(1 - z);

g(x) = z*x 其中 z 是二元变量

将此条件表示为两个约束：

如果 z = 1 则 g(x) - x = 0

如果 z = 0 则 g(x) = 0

g(x) <= x + M*(1-z);
g(x) >= x - M*(1-z);
g(x) <= M*z;
g(x) >= -M*z;

示例：固定成本

假设生产数量为 x 的物品的成本为

$cost = {\begin{array}{l} a + b x & if x > 0 \\ 0 & if x = 0. \end{array}$

您可以使用线性变量 x 和二元指示变量 z 来对该非线性成本进行建模。创建约束，使得每当 x > 0 时都会出现 z = 1，并在目标函数中包含 z，使得每当 x = 0 时都会出现 z = 0。假设问题包含边界 M 使得 x ≤ M。

x <= M*z; % Constraint, makes z = 1 when x > 0
cost = a*z + b*x;

如果您最小化成本，当 x = 0 时，z 也 = 0。

示例：OR 约束

有时您想要对在条件 A 成立、条件 B 成立或条件 C 成立时强制执行的约束进行建模。为此，创建二元指示变量 zA、zB 和 zC，指示相应条件 A、B 和 C 何时成立，并包括附加约束

zA + zB + zC >= 1;

再比如，对绝对值约束 |x| = 5 进行建模，也就是 x = 5 或 x = –5。创建两个指示变量 z1 和 z2，分别指示 x = 5 和 x = –5 的时间。然后加入约束

z1 + z2 >= 1;

在 x = 5 时设置 z1 = 1 的一种方法是针对以下条件引入三个新的指示变量 z11、z12 和 z13：

当 x < 5 且 z1 = 0 时，z11 = 1，

当 x = 5 且 z1 = 1 时，z12 = 1，

当 x > 5 且 z1 = 0 时，z13 = 1。

然后引入约束

z11 + z12 + z13 = 1;

要指定 z11，请使用这三个约束。

-(1 - z11) <= z1;
z1 <= (1 - z11);
x - 5 <= M(1 - z11);

要指定 z12，请使用这四个约束。

-(1 - z12) <= z1 - 1;
z1 - 1 <= (1 - z12);
-M(1 - z12) <= x - 5;
x - 5 <= M(1 - z12);

要指定 z13，请使用这三个约束。

-(1 - z13) <= z1;
z1 <= (1 - z13);
x - 5 >= -M(1 - z13);

为了完成模型，请为与 z2 和条件 x = –5 相对应的 z21、z22 和 z23 指定类似的约束。

示例：将二元二次问题转换为二元线性问题

考虑二元变量 x_i 中的最小化问题

x^TQx,

其中 x 是长度为 N 的优化变量的列向量，而 Q 是给定的 N×N 矩阵。为了在 N 不是太大的情况下求解这个问题，使用二元变量 xij 的 N×N 数组将二元二次问题转换为二元线性问题。如果 xij(i,j) = x(i)*x(j)，那么您可以将目标函数表示为：

sum(Q.*xij,"all")

为了确保 xij 变量等于 x(i)*x(j)，请使用以下三个线性不等式约束。该代码采用基于问题的方法。

N = 100; % Specify the number of variables
x = optimvar("x",N,Type="integer",LowerBound=0,UpperBound=1);
xij = optimvar("xij",N,N,Type="integer",LowerBound=0,UpperBound=1);
prob = optimproblem;

% Constraint xij = 1 when x(i) = 1 and x(j) = 1
prob.Constraints.f = xij >= repmat(x,1,N) + repmat(x',N,1) - 1;
% Constraint xij = 0 when x(i) = 0
prob.Constraints.g = xij <= repmat(x,1,N);
% Constraint xij = 0 when x(j) = 0
prob.Constraints.h = xij <= repmat(x',N,1);

prob.Objective = sum(Q.*xij,"all");

现在问题在优化变量和约束中是线性的，solve 调用 intlinprog 来计算解。

[sol,fval] = solve(prob);

Solving problem using intlinprog.
...

对于 N ≤ 100，intlinprog 解相当快，但对于较大的 N 值，解会变慢，并且为了获得合理的性能，变量数限制为大约 200 个。

扩展阅读

关于优化建模的经典书籍是 Williams [1]。有关二元指示变量的大 M 表示为何在数学上是完整且不可扩展的讨论，请参阅 Hooker [2]。有关在数学建模中使用二元指示变量的更多示例，请参阅 Brown 和 Dell [3] 以及 Stevens 和 Palocsay [4]。

参考

[1] Williams, H. Paul. Model Building in Mathematical Programming, 5th Edition. Wiley, 2013.

[2] Hooker, John. A Principled Approach to MILP Modeling. Carnegie Mellon University, 2008. Available at https://coral.ise.lehigh.edu/mip-2008/talks/hooker.pdf.

[3] Brown, Gerald G. and Robert F. Dell. Formulating Integer Linear Programs: A Rogues' Gallery. INFORMS Transactions on Education 7 (2), 2007, pp. 153–159. Available at https://doi.org/10.1287/ited.7.2.153.

[4] Stevens, Scott P. and Susan W. Palocsay. Teaching Use of Binary Variables in Integer Linear Programs: Formulating Logical Conditions. INFORMS Transactions on Education 18 (1), 2017, pp. 28–36. Available at https://doi.org/10.1287/ited.2017.0177.