[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 |
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] Need help on interval planning constraint,
Oliver Milz <=