|
From: | Tawny Owl |
Subject: | RE: [Help-glpk] Modelling Advice Request - Project Tasks |
Date: | Thu, 21 Jan 2010 12:13:12 +0000 |
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 |
[Prev in Thread] | Current Thread | [Next in Thread] |