Hi, I have a interval planning problem:
n intervals, begin and end of each interval needs to be determined duration of interval is given minimum begin and maximum end of each interval are given (bounds) Goal: Find begin and end of each interval (inside its bounds) intersection free (if possible). I solved this with glpk using a binary matrix which has n columns and (maximumOfAllMaximumEnds-minimumOfAllMinimumEnds) rows, where each 1 represents a day between begin and end of an interval each sum of a row needs to be <=1 (intersection free) each sum of a column need to be = duration of the interval each block of 1 needs to be continuous (no 0 inbetween) but it is big & slow and was a bad idea. I have another model (see below) where the constraint to say that each interval needs to be intersection free is missing. I am a beginner to glpk and tried to express that in many several ways, but I could not manage it. Can you help me with this ? Is it possible ? Maybe using another model ? I guess this here needs to expressed in any working way : s.t. intersectionFree1{p in 1..n, k in 1..n: p<>k}: not (begin[p] <=begin[k] <= end[p]); s.t. intersectionFree2{p in 1..n, k in 1..n: p<>k}: not (begin[p] <=end[k] <= end[p]); If it can?t be expressed - since this seems to be a common problem, do you know a way to efficently solve this ? Thanks, Oliver Model: # interval count param n, integer, > 0; # duration of each interval param duration{i in 1..n}; # lower bound of each interval param lowerb{i in 1..n}; # higher bound of each interval param higherb{i in 1..n}; # determined begin of each interval var begin {i in 1..n} integer,>=0; # determined end of each interval var end {i in 1..n} integer,>=0; s.t. beginInBounds{p in 1..n}: lowerb[p] <= begin[p] <= higherb[p]; s.t. endInBounds{p in 1..n}: lowerb[p] <= end[p] <= higherb[p]; s.t. durationIsEndMinusBegin{p in 1..n}: end[p]-begin[p] =duration[p]; # Missing intersectionfree constraint data; param n :=3; param duration := 1 3, 2 4, 3 2; param lowerb := 1 1, 2 3, 3 1; param higherb := 1 10, 2 8, 3 10; -- View this message in context: http://old.nabble.com/Need-help-on-interval-planning-constraint-tp26828755p26828755.html Sent from the Gnu - GLPK - Help mailing list archive at Nabble.com. _______________________________________________ Help-glpk mailing list Help-glpk@gnu.org http://lists.gnu.org/mailman/listinfo/help-glpk