cutting-stock/multidimensional bin-packing probleme

Pff, war mir immer ein Rätsel und wird's wohl auch noch lange bleiben.

Wenn du was nettes hast, kannst du's ja dann mal hier posten.

hier zb ein 'programm' in GNU mathprog modelling language - ein grober hack eines simplen mitgelieferten 0/1 binpacking beispiels auf weitere dimensionen, demands>1 usw.. für die eingabedaten hab ich einen konverter geschrieben

m gegenstände, mit den gewichten w und den werten v. pro packeinheit dürfen maxc und maxv nicht überschritten werden. anzahl der packeinheiten soll minimiert werden; so ein problem ist NP-hart; das kleine beispiel braucht < 1min, das große läuft seit 24h auf einem p4/2ghz ohne noch eine lösung gefunden zu haben.

die 'number of bin'-estimation ist derweil auskommentiert, weil wir wissen, daß das beispiel in knapp unter 900 einheiten zu schaffen ist.

Code:

param m, integer, > 0;
/* number of items */

set I := 1..m;
/* set of items */

param v{i in 1..m}, > 0;
/* v[i] is value of item i */

param d{i in 1..m}, > 0;
/* d[i] is demand of item i */

param w{i in 1..m}, > 0;
/* w[i] is weight of item i */

param maxv, > 0;
/* max value */

param maxc, > 0;
/* bin capacity */

/* We need to estimate an upper bound of the number of bins sufficient
   to contain all items. The number of items m can be used, however, it
   is not a good idea. To obtain a more suitable estimation an easy
   heuristic is used: we put items into a bin until it is possible, and
   if the bin is full, we use another bin. Thus, the number of bin used
   in this way gives us a more appropriate estimation. */
/*
param z{i in I, j in 1..m} :=
/* z[i,j] = 1 if item i is in bin j, otherwise z[i,j] = 0 */

 /*  if i = 1 and j = 1 then 1
   /* put item 1 into bin 1 */
/*
   else if sum{jj in 1..j-1} z[i,jj]*v[i] > maxv then 0
   /* if item i is already in some bin, do not put it into bin j */
/*
   else if sum{ii in 1..i-1} w[ii] * z[ii,j] + w[i] > maxc then 0
   /* if item i does not fit into bin j, do not put it into bin j */
/*
   else if sum{ii in 1..i-1} z[ii,j] * v[ii] >
/*
   else 1;
   /* otherwise put item i into bin j */
/*
check{i in I}: sum{j in 1..m} z[i,j] >= d[i];
/* each item must be used */
/*
check{j in 1..m}: sum{i in I} w[i] * z[i,j] <= maxc;
/* no bin must be overflowed */
/*
check{j in 1..m}: sum{i in I} v[i] * z[i,j] <= maxv;
/* no bin must be overvalued */
/*
param n := sum{j in 1..m} if exists{i in I} z[i,j] then 1;
/* determine the number of bins used by the heuristic; obviously it is
   an upper bound of the optimal solution */

param n := 2000;

display n;

set J := 1..n;
/* set of bins */

var x{i in I, j in J}, integer >= 0;
/* x[i,j] = 1 means item i is in bin j */

var used{j in J}, binary;
/* used[j] = 1 means bin j contains at least one item */

/* s.t. use {j in J, i in I }: x[i,j] >=0; */

s.t. use{j in J}: sum{i in I} x[i,j] >= used[j] ;
s.t. test{j in J, i in I}: x[i,j] <= min(maxc/w[i],maxv/v[i]);

s.t. one{i in I}: sum{j in J} x[i,j] >= d[i];
/* each item must be at least the demands */

s.t. limc{j in J}: sum{i in I} w[i] * x[i,j] <= maxc * used[j];
/* if bin j is used, it must not be overflowed */

s.t. limv{j in J}: sum{i in I} v[i] * x[i,j] <= maxv * used[j];
/* if bin j is used, it must not be overvalued */

minimize obj: sum{j in J} used[j];
/* objective is to minimize the number of bins used */

/* ** a small program for start */

data;

param m := 3;
param w := 1 30, 2 20, 3 50;
param v := 1 90, 2 70, 3 20;
param d := 1 12, 2 7, 3 15;
param maxc := 100;
param maxv := 200;
end;

/* ** a bigger problem - uncomment */
/*
data;
 param maxc := 100;
  param maxv := 200;
  param v := 1 25, 2 9, 3 11, 4 71, 5 82, 6 86, 7 45, 8 80, 9 66, 
             10 79, 11 34, 12 94, 13 42, 14 83, 15 64, 16 37, 17 92,
             18 47, 19 76, 20 18, 21 85;
  param m := 21 ;
  param w := 1 14, 2 51, 3 78, 4 83, 5 89, 6 63, 7 80, 8 62, 9 23,
             10 11, 11 45, 12 68, 13 42, 14 91, 15 92, 16 82, 17 65,
             18 39, 19 6, 20 1, 21 64;
  param d := 1 29, 2 76, 3 73, 4 41, 5 70, 6 71, 7 94, 8 80, 9 78,
             10 55, 11 20, 12 62, 13 27, 14 85, 15 34, 16 67, 17 79,
             18 51, 19 64, 20 49, 21 24;
  end;
*/
end;