linear-programmingamplinteger-programmingmathprog

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


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?


Solution

  • 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.