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: |
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. |
(This model had originally only binary and continuous variables).
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.
ReplyDeleteWhile you are probably right, I would run some instances each way to check.
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