如何强制连续变量具有相同的值？

Question

我有一个二进制变量 y[k][t]，其中 k = 1..3（机器）和 t = 1..10（时间）。如果机器处于活动状态，则变量 Y 为 1，否则为 0。

在优化中，如果机器 1 在周期 1 中处于活动状态，例如Y[1][1] = 1，我希望机器至少连续运行3个时间段。即 Y[1][1] = Y[1][2] = Y[1][3] = Y[1][4] = 1。

我只希望 t+1,t+2,t+3 的后继变量与 t 相同，如果它是活动的。

我如何在 cplex studio 中做到这一点？

Answer 1

这有时称为最小运行长度。有不同的方法来处理这个问题。假设我们有 x(t) 作为二进制变量，指示机器是否在时间 t 运行。第一件事是引入一个二进制变量 start(t) 来指示运行何时开始。这就是我的意思：

  t      1 2 3 4 5 6 7 8
  x      0 1 1 1 0 1 1 0
  start  0 1 0 0 0 1 0 0

A 运行在 x(t-1)=0 and x(t)=1 时开始，或者更正式地说：

start(t) = x(t)*(1-x(t-1))

这是非线性的。我们可以使用以下方法对其进行线性化：

start(t) <= x(t)
start(t) <= 1-x(t-1)
start(t) >= x(t)-x(t-1)

通常我们只使用边界：

start(t) >= x(t)-x(t-1)

接下来我们需要：

start(t) = 1 ==> x(t)...x(t+K-1) = 1

其中 K 是最小运行长度。

这可以建模为：

x(t+1) >= start(t)
...
x(t+K-1) >= start(t)

（我们已经知道 x(t)=1 if start(t)=1）。

Answer 2

Erwin 写的关于最小运行长度的内容很好。如果您依赖 CPLEX 中可用的逻辑约束，则模型会更简单一些：

range K=1..3;
range T=1..10;

dvar boolean Y[K][T];
dvar boolean start[K][T];


subject to
{
forall(k in K) start[k][1]==Y[k][1];
forall(k in K,t in T:t!=1) start[k][t] ==  ((Y[k][t]==1) && (Y[k][t-1]==0));

forall(k in K) forall(l in 1..3) 
  forall(t in T:(t+l) in T) (start[k][t]==1) => (Y[k][t+l]==1);


}

但是，如果您延长时间范围，我们会枚举时间，这可能会导致求解时间过长。在 CPLEX 和 OPL 中，您还可以使用 CPOptimizer 及其专用的调度概念：间隔。

然后你会写

using CP;

range K=1..3;
range T=1..10;

int nbMaxIntervals=4;

dvar interval itvs[K][1..nbMaxIntervals] optional in T size 3..10;

subject to
{
forall(k in K) forall(i in 1..nbMaxIntervals-1) 
     endBeforeStart(itvs[k][i],itvs[k][i+1]);


}

确保您至少开启 3 个时间段的是

size 3..10;

注意：更多关于 CPOptimizer

如何强制连续变量具有相同的值？

how to force succesive variable to be of same value?

optimization

mathematical-optimization

cplex