To: celliers@ibm2.sun.ac.za Subject: Re: Best Fit algorithm for stock-cutting and bin packing problems Newsgroups: sci.math From: rusin@math.niu.edu In article you write: >I am currently working on a program to optimize the layout of >rectangular objects on a surface. If you know where I can find any >information about algorithms and formulas etc. would you please be so >kind to help me. Thank you very much. Here are some recent newsgroup posts which appear to be helpful ============================================================================== From: israel@math.ubc.ca (Robert Israel) Newsgroups: sci.math Subject: Re: reference urgently needed for CUTTING STOCK PROBLEM Date: 20 Feb 1998 23:23:17 GMT In article <6ci4pc$ot5$1@nnrp1.dejanews.com>, su_jionglong@hotmail.com writes: |> Can somebody please help me by directing to reference concerning the cutting |> stock problem. This is one special form of integer programming. |> |> I would also need to know a greedy algorithm called FIRST FIT DECREASING |> METHOD to find an initial basic feasible solution for the linear relaxation. |> The greedy algorithm is crucial in solving the above problem. Try V. Chvatal, Linear Programming, W.H. Freeman 1983, ISBN 0-7167-1195-8. ============================================================================== From: spellucci@mathematik.th-darmstadt.de (Peter Spellucci) Newsgroups: sci.math,sci.op-research,sci.math,sci.op-research Subject: Re: Please help on FFD ( First Fit Decreasing) Method for Cutting Stock problem Date: 13 Mar 1998 12:50:07 GMT In article <6e8n59$b1a$1@nnrp1.dejanews.com>, su_jionglong@hotmail.com writes: |> Having been trying to solve the cutting stock problem but the ideal text |> Chvatal : Linear Programming is not available in my country. you may try online tutorials concerning linear programming, e.g. http://www-math.cudenver.edu/~hgreenbe |> |> Need to know : How to find the matrix by the above method? The matrix ,if |> Iam not wrong, is the basic(but not optimal) solution. Is the matrix |> generated by the First fit decreasing method a UNIQUE matrix? if you speak about LP, you seem to confuse a lot : if you have a feasible nondegenerate vertex, then the columns of the constraint matrix which corrspond to the nonzero components of x build the basismatrix. "a first fit decreasing method" is unknown to me. do you mean Blands exchange rule to take as ingoing and outgoing variables those with the algebraically smallest index chosen from the possible ones? the basismatrix of a nondegenerate vertex is always unique. hope this helps peter ============================================================================== From: spellucci@mathematik.tu-darmstadt.de (Peter Spellucci) Newsgroups: sci.math.num-analysis Subject: Re: Optimization problem with squares Date: 21 Jul 1998 09:47:22 GMT In article <35b3a5f0.0@news.uibk.ac.at>, Hermann Helbok writes: |> |> |> |> I have a large square with fixed dimensions. |> Then i have 10-20 little squares, and I want place them in such a way that |> the rest which is unused is a minimum. |> once again, the 2d cutting stock problem. literature: The german book "Grundlagen zur Integration der Zuschneideplanung in Produktionsplanungs- -steuerungssystem" from Ute Finke, LIT Verlag, Münster, 1995, contains quite a lot of references to bin packing and cutting problem. Maybe it helps you. Another bibliograhy is writen by Harald Dyckhoff, Ute Finke: Cutting and packing in Production and Distribution, Physica Verlag, Heidelberg, 1991. check out http://prodlog.wiwi.uni-halle.de/sicup/index.html http://www.maths.mu.oz.au/~worms/digest/cuting_stock96.html and other links you find with a netsearch a commercial cutting stock software package at http://www.hyper.gr/escape/guillotine.html no free public domain software as far as I know hope this helps peter ============================================================================== From: spellucci@mathematik.th-darmstadt.de (Peter Spellucci) Newsgroups: sci.op-research,sci.math.research Subject: Re: Container Loading Algorithm Date: 6 Jan 1998 11:46:09 GMT In article <34b0324a.2548630@news.extremezone.com>, m@superb.com writes: |> |> Does anyone know where I can find a good 3D shipping container loading |> algorithm? I came up with one but I would like to compare it with |> others. snip the same problem as cutting a piece of material in 3d into given sizes with minimum loss, the cutting stock problem. for papers see http://prodlog.wiwi.uni-halle.de/sicup/index.html http://www.maths.mu.oz.au/~worms/digest/cuting_stock96.html http://www.math.tu-dresden.de/~riehme/CAPAD-DIR/CAPAD.html there is a commercial software product (2d I believe), see http://www.hyper.gr/escape/guillotine.html I dont know about good software for 3d available for free hope this helps peter ============================================================================== From: "R.G. Vickson" Subject: Re: Linear programming: algorithms on diet and cutting stock problems Date: Mon, 13 Sep 1999 12:58:05 -0400 Newsgroups: sci.math.symbolic To: Torsten Gehl Torsten Gehl wrote: > I found myself stuck while programming algorithms with Maple that are to > solve the diet problem as well as the cutting stock problem. The cutting stock problem is not nearly as easy as the diet problem. Several aspects are emportand: (1) is the problem 1 or 2-dimensional? (2) are cutting patterns to be generated automatically by the program itself, or are they generated externally? Realistic cutting stock problems may have millions of patterns, corresponding to millions of variables in the formulation. These are typically dealt with either by "column generation" (see Chvatal, Linear Programming, Freeman Press, 1980, Chapter 13 for a nice treatment ), or by some form of table lookup, in which an encyclopedia of "useful" patterns is developed and only these are accessed in the formulation (see, eg., Edwards, Wagner and Woods, "Blue Bell Trims its Inventory", reprinted in Assad et al. "Excellence in Management Science", Prentice-Hall---describing the use of such methods in blue jean manufacture). You also have the problem that integer solutions are needed, so the problem is NOT a linear program. > The goal is > that the user should just enter the individual objective function as well as > the constraints and be provided with the optimum solution. > Can anybody help me out on how to correctly formulate the algorithms that > are to solve these two problems? > > Thank you