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?
Add a comment
|
1 Answer
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.
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)) <= 3The 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.
2 Comments
oakenshield1
But don't you think these constraints eventually lead all of the
x_it to be 1 ?
Erwin Kalvelagen
Yes. I will add some different approaches.