[Help-glpk] Need help on interval planning constraint

[Oliver Milz]

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.