Hi Oliver, A couple of quick observations. First, your first formulation introduces a *lot* of binary variables, and unnecessarily discretizes time.
The second approach is workable, but why add the integer specification? Was that an unstated part of the application? One way to model the 'no intersection' requirement is add a binary variable for each unique pair of intervals. Call it y[i,j] corresponding to tasks i and j, i < j. y[i,j] = 1 implies task i finishes before j starts, and y[i,j] = 0 implies the opposite. This technique is demonstrated in a simple example "Machine Bottleneck" under GMPL/GLPK Examples on http://estm60203.blogspot.com/ Hope that helps, Jeff On Thu, Dec 17, 2009 at 9:55 AM, Oliver Milz <[email protected]> wrote: > > 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 > [email protected] > http://lists.gnu.org/mailman/listinfo/help-glpk >
_______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
