Implementing a constraint based on previous variable's value in GNU Mathprog/AMPL

Question

I have a binary program and one of my variables, x_it is defined on two sets, being I: Set of objects and T: Set of the weeks of the year, thus x_it is a binary variable standing for whether object i is assigned to something on week t. The constraint I failed to implement in AMPL/GNU Mathprog is that if x_it equals to 1 then x_i(t+1) and x_i(t+2) also should take value of 1. Is there a way to implement this constraint in a simple mathematical programming language?

Answer 1

The implication you want to implement is:

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

AMPL supports implications (with the ==> operator), so we can write this directly. MathProg does not.

A simple way to implement the implication as straightforward linear inequalities is:

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

This can easily be expressed in AMPL, MathProg, or any modeling tool.

This is the pure, naive translation of the question. This means however that once a single x(i,t)=1 all following x(i,t+1),x(i,t+2),x(i,t+3)..=1. That could have been accomplished by just the constraint x(i,t+1) >= x(i,t).

A better interpretation would be: we don't want very short run lengths. I.e. patterns: 010 and 0110 are not allowed. This is sometimes called a minimum up-time in machine scheduling and can be modeled in different ways.

1. Forbid the patterns 010 and 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. The pattern 01 implies 0111:

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

Both these approaches will prevent patterns 010 and 0110 to occur.