[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Help-glpk] Need help on interval planning constraint

From: Oliver Milz
Subject: [Help-glpk] Need help on interval planning constraint
Date: Thu, 17 Dec 2009 17:55:15 +0300


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)

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, 
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
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 ?



# 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


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:
Sent from the Gnu - GLPK - Help mailing list archive at

reply via email to

[Prev in Thread] Current Thread [Next in Thread]