[Top][All Lists]

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

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

From: Jeffrey Kantor
Subject: Re: [Help-glpk] Need help on interval planning constraint
Date: Thu, 17 Dec 2009 10:32:41 -0500

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

Hope that helps,

On Thu, Dec 17, 2009 at 9:55 AM, Oliver Milz <address@hidden> wrote:


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

Help-glpk mailing list

reply via email to

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