Optimal 2d AABB allocation

aabb_alloc.mod

# See http://lethalman.blogspot.it/2014/01/intersection-test-and-optimal.html
# Run as glpsol --tmlim 5 -m alloc.mod

param cols integer >= 0;
param rows integer >= 0;
param n integer >= 1;
param w{1..n} integer >= 1 <= cols;
param M := cols+rows;
param C := 1/(2*n*rows);

var x{i in 1..n} integer >= 0 <= cols-1;
var y{i in 1..n} integer >= 0 <= rows-1;
var h{i in 1..n} integer >= 1 <= rows;
var b1{i in 1..n-1, j in i+1..n} binary;
var b2{i in 1..n-1, j in i+1..n} binary;
var b3{i in 1..n-1, j in i+1..n} binary;
var minh integer >= 0;

maximize alloc: minh + C*(sum{i in 1..n} h[i]);

minheight{i in 1..n}: minh <= h[i];
int1{i in 1..n-1, j in i+1..n}: M*b1[i,j] + M*b3[i,j] + x[i] >= x[j] + w[j];
int2{i in 1..n-1, j in i+1..n}: M*(1-b1[i,j]) + M*b3[i,j] + x[j] >= x[i] + w[i];
int3{i in 1..n-1, j in i+1..n}: M*b2[i,j] + M*(1-b3[i,j]) + y[i] >= y[j] + h[j];
int4{i in 1..n-1, j in i+1..n}: M*(1-b2[i,j]) + M*(1-b3[i,j]) + y[j] >= y[i] + h[i];
bound1{i in 1..n}: x[i]+w[i] <= cols;
bound2{i in 1..n}: y[i]+h[i] <= rows;

solve;

printf: "area %d cols x %d rows\n", cols, rows;
printf{i in 1..n}: "box %d: x=%d, y=%d, w=%d, h=%d\n", i, x[i], y[i], w[i], h[i];
printf: "alloc=%g\n", alloc;

data;

param cols := 10;
param rows := 100;
param n := 10;
param w := 1 3, 2 4, 3 10, 4 7, 5 4, 6 8, 7 2, 8 9, 9 8, 10 5;

end;