整数和逻辑建模
整数约束允许您创建具有以下重要特征的模型:
蕴涵,例如“如果条件 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 | 创建一个新的二元变量
g(x) <= M*z;
g(x) >= -M*z1;
z + z1 == 1; 当 g(x) = 0 时,此表示不确定。 |
结合逻辑约束来创建新公式
使用先前的逻辑约束和二元指示变量来创建实现新公式的代码。
条件 | 约束代码 |
---|---|
对于满足边界约束 M 的标量函数 g(x) 和 h(x),实现条件: 如果 g(x) ≥ 0 则 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 的物品的成本为
您可以使用线性变量 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
指定类似的约束。
示例:将二元二次问题转换为二元线性问题
考虑二元变量 xi 中的最小化问题
xTQx,
其中 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.
另请参阅
intlinprog
| ga
(Global Optimization Toolbox) | gamultiobj
(Global Optimization Toolbox) | surrogateopt
(Global Optimization Toolbox)