Re: [Help-glpk] Need help on interval planning constraint

[Jeffrey Kantor]

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 <address@hidden> 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
address@hidden
http://lists.gnu.org/mailman/listinfo/help-glpk