[Help-glpk] [Fwd: Strip packing problem]

[Andrew Makhorin]

-------- Forwarded Message --------
From: Thiago Borges <address@hidden>
To: address@hidden
Subject: Strip packing problem
Date: Sun, 24 Jun 2012 02:51:15 -0300

Hello guys,


I'm getting in trouble trying to model the following problem on GLPK.


It's a Strip packing problem. I have a set of rectangles to cut in a big
paper of dimensions W and H.


H is big enough for fit all rectangles, but I need to use the minimal
possible amount of paper.


minimize H
subject to
(xi + wi ≤ xj) or (xj + wj ≤ xi) or (yi + hi ≤ yj) or (yj + hj ≤
yi), ∀i, j ∈ I ,  i = j
xi + wi ≤ W, ∀i ∈ I
yi + hi ≤ H, ∀i ∈ I
xi, yi ≥ 0,∀i ∈ I


The first constraint (with "or's") is about overlap of the rectangles.
Each rectangle is at (xi, yi) and has width wi and height hi.


Someone can point me how to model the "or" conditions? 


I'm trying to create binary variables which determine if each rectangle
is above, below, left or right from each other, but it has taking days
to find solutions for instances of only 10 rectangles.


Sample:
var above{i in I, j in I}, binary;
s.t. overlap{i in I, j in I: i != j}: above[i,j] + below[i,j] <= 1;
s.t. overlap{i in I, j in I: i != j}: 1 <= below[i,j] + right[i,j] +
left[i,j] + above[i,j] <= 2;


s.t. acima1{i in I, j in I: i != j}: above[i,j]*B >= y[i]-y[j]-h[j];
s.t. acima2{i in I, j in I: i != j}: above[i,j]*B <= B+y[i]-y[j]-h[j];


*B = BIG M


Thanks,


-- 
Thiago Borges