linear-programming - 在 GNU Mathprog/AMPL 中实现基于先前变量值的约束

Question

我有一个二进制程序，我的一个变量x_it在两个集合上定义，beingI: Set of objects和T: Set of the weeks of the year，因此x_it是一个二进制变量，表示 object 是否i在 week 被分配给某物t。我在 AMPL/GNU Mathprog 中未能实现的约束是如果x_it等于1thenx_i(t+1)并且x_i(t+2)也应该取1. 有没有办法用简单的数学编程语言来实现这个约束？

Answer 1

您要实现的含义是：

 x(i,t) = 1 ==> x(i,t+1) = 1, x(i,t+2) = 1

AMPL 支持含义（使用 ==> 运算符），因此我们可以直接编写它。MathProg 没有。

将蕴含实现为直接线性不等式的一种简单方法是：

x(i,t+1) >= x(i,t)    
x(i,t+2) >= x(i,t)

这可以很容易地用 AMPL、MathProg 或任何建模工具表示。

这是问题的纯粹、幼稚的翻译。然而，这意味着一旦一个单一的x(i,t)=1所有以下x(i,t+1),x(i,t+2),x(i,t+3)..=1。这可以通过约束来完成x(i,t+1) >= x(i,t)。

更好的解释是：我们不想要非常短的运行长度。ie 模式：不允许使用 010 和 0110。这有时被称为机器调度中的最小正常运行时间，并且可以以不同的方式建模。

1. 禁止使用 010 和 0110 模式：

    (1-x(i,t-1))+x(i,t)+(1-x(i,t+1)) <= 2
    (1-x(i,t-1))+x(i,t)+x(i,t+1)+(1-x(i,t+2)) <= 3
   

2. 模式 01 意味着 0111：

     x(i,t+1)+x(i,t+2) >= 2*(x(i,t)-x(i,t-1))
   

这两种方法都可以防止出现 010 和 0110 模式。