Main Content

整数和逻辑建模

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

  • 蕴涵,例如“如果条件 A 成立,则条件 B 成立”。

  • 交易成本或设置成本,例如“如果我购买 0 件商品,则该商品的成本为 0,但如果我购买超过 0 件,则每件商品的成本为 $A 交易成本加上 $B”。请参阅示例:固定成本

  • 逻辑约束,例如“气闸门 A 和门 B 不能同时打开”。

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

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

大 M 表示

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

xM.

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

xM z.

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

基本问题:水库流量

假设您想要用整数时间对水库进行建模。在固定范围内的每个正整数时间 t,水库可以接受水量 xin(t),或排出水量 xout(t),连续不断的进水或出水,直至最大值 M。您的模型应该强制执行“如果 xin(t) > 0xout(t) = 0,如果 xout(t) > 0xin(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) > 0zin(t) = 1,请使用 Big-M 表示。假设对于所有 t,xin(t) 的上下界均为正数 M。包括约束

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

为了确保每当 xin(t) = 0zin(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 命令。这些语句假设变量 zwf 是二元优化变量,这意味着每个变量都有类型 "integer"、下界 0 和上界 1

描述逻辑语句MATLAB 命令
zw 具有相反的值z = not w
z = 1 - w;
zw 中至少有一个为真z or w
z + w >= 1;
zw 中最多有一个为真(not z) or (not w)
z + w <= 1;
z 为真或 w 为真时,f 也为真f = z or w
f >= z;
f >= w;
f <= z + w;
zw 同时为真时,f 才为真f = z and w
f <= z;
f <= w;
f >= z + w - 1;
zw 之一为真时,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) 满足边界

–Mg(x) ≤ M.

条件约束代码
如果 z = 1g(x) ≤ 0
g(x) <= M*(1 - z);
如果 z = 1g(x) ≥ 0
g(x) >= -M*(1 - z);
如果 z = 1g(x) = 0
g(x) <= M*(1 - z);
g(x) >= -M*(1 - z);
如果 g(x) ≤ 0z = 1
g(x) >= -M*z;
如果 g(x) ≥ 0z = 1
g(x) <= M*z;

如果 g(x) > 0z = 1

如果 g(x) < 0z = 0

创建一个新的二元变量 z1 来指示 g(x) < 0

g(x) <= M*z;

g(x) >= -M*z1;

z + z1 == 1;

g(x) = 0 时,此表示不确定。

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

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

条件约束代码

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

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

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

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

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

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

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

如果 z = 0g(x) = 0

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

示例:固定成本

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

cost={a+bxif x>00if x=0.

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

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

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

示例:OR 约束

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

zA + zB + zC >= 1;

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

z1 + z2 >= 1;

x = 5 时设置 z1 = 1 的一种方法是针对以下条件引入三个新的指示变量 z11z12z13

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 相对应的 z21z22z23 指定类似的约束。

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

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

xTQx,

其中 x 是长度为 N 的优化变量的列向量,而 Q 是给定的 N×N 矩阵。为了在 N 不是太大的情况下求解这个问题,使用二元变量 xijN×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.

另请参阅

| (Global Optimization Toolbox) | (Global Optimization Toolbox) | (Global Optimization Toolbox)

相关主题