
From:  Jeffrey Kantor 
Subject:  Re: [Helpglpk] Need help on interval planning constraint 
Date:  Thu, 17 Dec 2009 10:32:41 0500 
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 (maximumOfAllMaximumEndsminimumOfAllMinimumEnds) 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/Needhelponintervalplanningconstrainttp26828755p26828755.html
Sent from the Gnu  GLPK  Help mailing list archive at Nabble.com.
_______________________________________________
Helpglpk mailing list
address@hidden
http://lists.gnu.org/mailman/listinfo/helpglpk
[Prev in Thread]  Current Thread  [Next in Thread] 