Monday, October 31, 2011

Slacks (with penalties) should not be integer variables

In the paper http://www.cs.nott.ac.uk/~jxm/timetabling/gor2007-paper.pdf a number of integer models for timetabling are discussed. The author also published the models used in this paper http://www.cs.nott.ac.uk/~jxm/timetabling/gor2007-empirical.zip (this should be very much applauded). Of course that means that I can provide some criticism.

In the scheduling models some soft constraints are modeled by introducing slacks, in this case CourseMinDayViolations:

subto ctCountWorkingDays:
  forall <c> in Courses:
  sum <d> in Days:
  CourseSchedule[c,d] >= CourseHasMindays[c] - CourseMinDayViolations[c];

This variable can then be minimized in the objective:

minimize value:
    (sum <p> in Periods: sum <r> in Rooms: sum <c> in Courses with CourseHasStudents[c] > RoomHasCapacity[r]:
      (Taught[p,r,c] * (CourseHasStudents[c] - RoomHasCapacity[r]))
    )
  + 2 * (sum <cu> in Curricula: sum <d> in Days: sum <sc> in DaySingletonChecks: SingletonChecks[cu,d,sc])
  + 5 * (sum <c> in Courses: CourseMinDayViolations[c])
;

That looks all good. But I don’t agree with the declaration:

var CourseMinDayViolations[Courses] integer >= 0 <= nbDays;

A slack variable like this should be declared as a positive continuous variable. It will be integer automatically. With this declaration there is the possibility the solver will branch on this variable.

My simplest argument would be: a model with fewer integer variables is likely to solve faster.

But sometimes solvers actually add integer variables! See:

Tried aggregator 1 time.
MIP Presolve eliminated 1634 rows and 5 columns.
MIP Presolve modified 10 coefficients.
Reduced MIP has 2401 rows, 11512 columns, and 92222 nonzeros.
Reduced MIP has 11028 binaries, 0 generals, 0 SOSs, and 0 indicators.
Probing time =    0.02 sec.
Tried aggregator 1 time.
MIP Presolve eliminated 10 rows and 0 columns.
Reduced MIP has 2391 rows, 11512 columns, and 91732 nonzeros.
Reduced MIP has 11032 binaries, 480 generals, 0 SOSs, and 0 indicators.
Presolve time =    0.20 sec.

(This model had originally only binary and continuous variables).

2 comments:

  1. Is it clear that one would not want to branch on this? For instance, the branch with CourseMinDayViolations[c]<=0 does the search for no violations, which seems a pretty good branch to explore. I would agree if the slack did not appear in something with a sum constraint.

    While you are probably right, I would run some instances each way to check.

    ReplyDelete
  2. I think you definitely want to declare it as an integer variable. In fact, as you noticed, some solvers will automatically re-categorize variables as part of the pre-processing processing. Sometimes, as Mike suggests, it can be better to branch on these variables. But I think this trick can have more effective by allowing for the generation of stronger cutting planes. (Think Gomory cuts, for example...)

    ReplyDelete