用GLPSOL AMPL/MathProg进行线性规划的或条件

Question

我想编写一个优化模型，根据某些约束选择两个任务中较小的一个。

minimize obj: (doT1 * T1) + (doT2*T2) + (additional variables)

T1和T2表示任务的持续时间，doT1表示完成这些任务的标志。我希望这个优化在需要时只选择其中一个。

当我输入约束

s.t. c15: 0<= doT1 <= 1;
s.t. c15: 0<= doT2 <= 1;

我得到一个错误消息，在glpsol中，它说不允许线性形式的乘法。

是否有可能表示线性规划中的OR条件?

Answer 1

gplsol最有可能抱怨变量doT1 * T1和doT2 * T2的乘积。

我假设doT1和doT2是二元变量，T1和T2是连续变量(代表任务的持续时间)。(注意，这意味着您将不得不使用混合整数规划求解器，而不是纯线性规划求解器。您可能还想尝试使用强大的MIP求解器(如Gurobi)。

你可以通过重写约束和目标来构建你的模型

  minimize  T1 + T2 + (additional variables)
   st        T1 <= UT1*doT1
             T2 <= UT2*doT2
             doT1 + doT2 <= 1
             doT1, doT2 binary
             (plus any additional constraints)

，其中UT1为任务T1的持续时间上界，UT2为任务T2的持续时间上界。如果doT1 = 0然后是T1 <= 0，那么任务将不会完成。如果是doT1 = 1，则是T1 <= UT1，这意味着允许任务T1占用一定的时间。对于T2也是如此。

OR条件由约束doT1 + doT2 <= 1表示。这个约束意味着doT1和doT2不能同时为1。也就是说只能选择一个作业。注意，<=约束还允许您不执行这两个任务。如果至少有一个任务必须完成，则需要使用约束doT1 + doT2 == 1。