RE: [Help-glpk] Modelling Advice Request - Project Tasks

[Tawny Owl]

Hi Yingjie

> Big-M: M = 15 - 1 given 15 tasks.
>
> position[b] - position[a] <= M * before[a,b]
> position[a] - position[b] <= M * before[b,a]
> before[a,b]+before[b,a] == 1

Thanks very much - this is exactly what I was looking for!

> can reduce the before[,] variables somehow,
> create variable pair: before[a,b] and before[b,a]
> only if task a, b are related in savings.
>
> Cheers,
>
> Yingjie

On that subject, a member of this list has privately sent me a model which does this.

Thanks to EVERYBODY who took the time to respond.

Here's the new model, which uses a parameter for data input, minimises the number of variables needed, and works very successfully:

set TASKS := 1..15;
set PAIRS := setof{a in TASKS, b in TASKS} (a,b);
param saving{(a,b) in PAIRS} default 0;

var position{TASKS} >= 0;
s.t. p0{a in TASKS}: position[a] <= 15;

param BigM := 100;

var before{PAIRS} binary;
s.t. c0{(a,b) in PAIRS: a < b}: before[a,b] + before[b,a] = 1;
s.t. c1{(a,b) in PAIRS: a < b}:
position[a] + 1 <= position[b] + BigM*(1-before[a,b]);
s.t. c2{(a,b) in PAIRS: a < b}:
position[b] + 1 <= position[a] + BigM*before[a,b];

maximize SAVINGS: sum{(a,b) in PAIRS} saving[a,b]*before[a,b];

solve;

printf "\n\n";
for {a in TASKS}{
printf " %2d : %2d\n", a, position[a];
}
printf "\n\nSavings: %s\n\n", sum{(a,b) in PAIRS} saving[a,b]*before[a,b];

data;

param saving:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 :=
1 . 2 . 2 . . . . 1 . . . . . .
2 2 . . . . . . . . . . . . . 3
3 4 . . . 1 . . . . . . . . . .
4 1 . 1 . 2 . . . . 1 . . . . .
5 . 1 . . . . . . . 1 . . 1 1 1
6 . . . 1 . . . 1 . . 2 . . . 1
7 . 2 . . . . . . . . . . . . 3
8 . . . . 4 . . . . . 1 . . . .
9 . 1 2 . . . . . . . 1 . 1 . .
10 . . . . . . . . . . 4 . . . 1
11 1 . 1 . . . . 1 . 1 . 1 . . .
12 3 . . 1 . . . . . . 1 . . . .
13 . . 2 . . . . . . . . 3 . . .
14 . . 1 . . 1 1 1 . . . 1 . . .
15 . . . . . 2 . . . . . 2 1 . . ;

end;

---

Do you want a Hotmail account? Sign-up now - Free