cutting-stock/multidimensional bin-packing probleme

Seite 1 von 1 - Forum: Coding Stuff auf overclockers.at

URL: https://www.overclockers.at/coding-stuff/cutting-stock_multidimensional_bin-packing_problem_117062/page_1 - zur Vollversion wechseln!

atrox schrieb am 14.06.2004 um 01:16

wer kennt/hat tools, libs bzw papers dazu ?

hab mir schon ein bishen was dazu angesehen, programme in Xpres-IVE/mosel, gnu linear programming Kit (glpk),... gemacht, bin aber noch auf der suche nach weiteren...

vorallem tools & papers zu Mixed-integer programming und multidimensionalen bin-packing oder cutting-stock algorithmen und heuristiken.

tia, atrox

Ringding schrieb am 14.06.2004 um 01:26

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.

mat schrieb am 14.06.2004 um 01:50

ich trage mal was bei

add: ich sags gleich, ich kenn mich mit dem thema 0 aus

atrox schrieb am 14.06.2004 um 02:01

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;