用GLPSOL AMPL/MathProg实现线性规划中的Or条件

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条件由constraint doT1 + doT2 <= 1表示。此约束意味着doT1和doT2不能同时为1。即只能选择一个作业。请注意，<=约束还允许您不执行任何一项任务。如果至少必须完成一项任务，则需要使用constraint doT1 + doT2 == 1。