Tuesday, March 27, 2012

No holes

In http://www.or-exchange.com/questions/5105/transforming-constraint-with-max-function a question arise how to forbid “holes” in a series of ones. E.g.

image

is allowed, but the following is not allowed:

image

Actually this is a well-known problem in machine scheduling. E.g. often we want to limit the number of start-ups of a generator (e.g. to limit wear and tear).

I believe the suggested solution

image

is not 100% correct as it will only forbid holes of length 1. Of course we can repeat this constraint for holes of size 2,3,….

There is another approach for this: count the number of time we see a startup. This can look like:

image

I.e. a startup happens of we go from 0 to 1.

Notes:

  • s(i) is automatically integer so we can relax if that is beneficial.
  • s(i) is not equal to a startup: it is a bound. Even if all y’s are zero, there may be a nonzero s(i).
  • always pay attention to the boundaries, e.g. what happens if machine is started up in first period.