linear-programming - 如何线性化 AND 和 OR 约束的组合

Question

我有一个变量 t，我想有以下约束:

a <= t <= b 

and 

(c <= t <= d) or (e <= t <= f)

这是我在 Julia 中使用的代码:

using JuMP, Cbc, StatsBase
import Random

model = Model(with_optimizer(Cbc.Optimizer));

@variable(model, T, Int);

@constraint(model, 5 <= T <= 1000);
@constraint(model, (100 <= T <= 200) | (1100 <= T <= 1300) );

# which fails with error:
# ERROR: LoadError: In `@constraint(model, (100 <= T[i] <= 200) | (1100 <= T[i] <= 1300))`: Unrecognized sense |

有没有办法将这些约束线性化？或者，是否存在可以处理这些约束的非线性求解器？

Answer 1

特殊情况:

5 ≤ T ≤ 1000
and
(100 ≤ T ≤ 200) or (1100 ≤ T ≤ 1300)  

很简单。结果只是:

100 ≤ T ≤ 200

一般来说:

a ≤ t ≤ b 
and 
(c ≤ t ≤ d) or (e ≤ t ≤ f)

(其中 a、b、c、d、e、f 是常量)可以使用二进制变量进行线性化:

a ≤ t ≤ b 
c + (a-c)δ ≤ t ≤ d + (b-d)δ 
e + (a-e)(1-δ) ≤ t ≤ f + (b-f)(1-δ)
δ ∈ {0,1}

---

现在是奖金问题:怎么做

a ≤ t ≤ b 
and 
(c ≤ t ≤ d) or (e ≤ t ≤ f) or (g ≤ t ≤ h)

同样，这里唯一的变量是t。所有其他量都是常数。下面是我们之前所做的直接扩展:

a ≤ t ≤ b 
c + (a-c)δ1 ≤ t ≤ d + (b-d)δ1 
e + (a-e)δ2 ≤ t ≤ f + (b-f)δ2
g + (a-g)δ3 ≤ t ≤ h + (b-h)δ3
δ1+δ2+δ3 = 2
δ1,δ2,δ3 ∈ {0,1}