Wednesday, January 20, 2010

MIP solver performance (GLPK,SCIP,GUROBI)

I am modelling a project in which doing some tasks before others will save time. I think that the model is correct - but even though I have only entered the savings for 1 task into the objective function, it is taking too long to run. I believe that the problem lies in my "before1" and "before2" conditions, each of which contain 15^4=50625 modelling variables. These conditions are needed to enable the before[] variable, where before[a,b]=1 means that task a will be completed before task b.

The variable position[] is working correctly (position[5]=3 means that task five will be done third). I could eliminate the huge amount of work being done in the "before1" and "before2" conditions if I could make use of these position variables. Could anyone advise me how I can achieve the following, please?

* if position[a] > position[b], then before[a,b] = 0
* if position[a] < position[b], then before[a,b] = 1

Thanks for any suggestions!

Model appended below:

/*
The project consists of 15 tasks. Completion of any of these tasks will save time on other tasks in the project as follows:
Task 1 savings: 2 hours on task 2: 2 hours on task 4: 1 hours on task 9
Task 2 savings: 2 hours on task 1: 3 hours on task 15
Task 3 savings: 4 hours on task 1: 1 hours on task 5
Task 4 savings: 1 hours on task 1: 1 hours on task 3: 2 hours on task 5: 1 hours on task 10
Task 5 savings: 1 hours on task 2: 1 hours on task 10: 1 hours on task 13: 1 hours on task 14: 1 hours on task 15
Task 6 savings: 1 hours on task 4: 1 hours on task 8: 2 hours on task 11: 1 hours on task 15
Task 7 savings: 2 hours on task 2: 3 hours on task 15
Task 8 savings: 4 hours on task 5: 1 hours on task 11
Task 9 savings: 1 hours on task 2: 2 hours on task 3: 1 hours on task 11: 1 hours on task 13
Task 10 savings: 4 hours on task 11: 1 hours on task 15
Task 11 savings: 1 hours on task 1: 1 hours on task 3: 1 hours on task 8: 1 hours on task 10: 1 hours on task 12
Task 12 savings: 3 hours on task 1: 1 hours on task 4: 1 hours on task 11
Task 13 savings: 2 hours on task 3: 3 hours on task 12
Task 14 savings: 1 hours on task 3: 1 hours on task 6: 1 hours on task 7: 1 hours on task 8: 1 hours on task 12
Task 15 savings: 2 hours on task 6: 2 hours on task 12: 1 hours on task 13
*/


var task{1..15, 1..15}, binary;
s.t. task1{a in 1..15}: sum{b in 1..15} task[a, b] = 1;
s.t. task2{b in 1..15}: sum{a in 1..15} task[a, b] = 1;

var position{1..15}, >= 0;
s.t. position1{a in 1..15}: sum{b in 1..15} b * task[b,a] = position[a];

var before{1..15, 1..15}, binary;
s.t. before1{a in 1..15, b in 1..15, c in 1..15, d in 1..15: b > a and c != d}: before[c,d] + 1.5 >= task[a,c] + task[b,d];
s.t. before2{a in 1..15, b in 1..15, c in 1..15, d in 1..15: a > b and c != d}: before[c,d] + task[a,c] + task[b,d] <= 2.5;

var saving{1..15}, >= 0;
s.t. s1: saving[1] = 2 * before[1,2] + 2 * before[1,4] + before[1,9];
maximize savings: saving[1];

solve;

for {a in 1..15} {
  for {b in 1..15: task[a,b] = 1} {
    printf "%s. Task %s\n", a, b;
  }
}
for {a in 1..15, b in 1..15: before[a,b] >= 0.5 and a != b}{
  printf "task %s is done before task %s\n", a, b;
}
for {a in 1..15} {
  printf "Position of task %s: %s\n", a, position[a];
}
printf "\nTotal Savings: %s hours.", saving[1];
end;

>> I solved your enclosed model in 350sec. using SCIP (Answer was "5" ) with no special settings.

Using glpk2gams and GAMS/Gurobi this was solved in 7.5 seconds:

MODEL STATISTICS

BLOCKS OF EQUATIONS      44,147     SINGLE EQUATIONS       44,147
BLOCKS OF VARIABLES         452     SINGLE VARIABLES          452
NON ZERO ELEMENTS       132,996     DISCRETE VARIABLES        435



               S O L V E      S U M M A R Y

     MODEL   m                   OBJECTIVE  gamsobjvar
     TYPE    MIP                 DIRECTION  MAXIMIZE
     SOLVER  GUROBI              FROM LINE  132906

**** SOLVER STATUS     1 Normal Completion        
**** MODEL STATUS      1 Optimal                  
**** OBJECTIVE VALUE                5.0000

RESOURCE USAGE, LIMIT          7.548      1000.000
ITERATION COUNT, LIMIT      9497    2000000000

There are better formulations: this test was done on the original model (unchanged, except for the conversion to GAMS).