🚀 go-pugleaf

In article <24JUL199212572842@vx.cis.umn.edu> mjfrisch@vx.cis.umn.edu (Michael J. Frisch, CIS 612/625-5830) writes:

   I am helping one of our users who wants to get the maximum volume of boxes
   to fit in a shipping container.  There are twelve different sized boxes.
   I'm interested in any software for solving this problem.  Otherwise, is
   there a way to set this up as a linear or nonlinear programming problem?
   If so, how?  Are there other methods one could use?  Are there any
   published articles or books on the subject?  Thanks for your help.

This problem is various referred to as a bin-packing or the knapsack problem.
General unconstrained solutions are very difficult to obtain.  Fortunately you
can do pretty well by imposing conditions and getting a good, albeit
non-optimal solution. Refer to the following letter that I had obtained about a
year ago.

BTW, I was trying to apply genetic algorithms to this problem but lacked a
good mutation and cross-over technique to prevent boxs (or squares in the 2D
case) from falling outside the boundaries.  Without this you end up wasting
most of the time on impossible combinations (unless you don't mind boxes
slopping over the side of the truck :-)


----------------------------------------------------------------------
Return-Path: <peter@bacchus.esa.oz.au>
Date: Fri, 19 Apr 91 12:04:10 EST
From: peter@bacchus.esa.oz.au
Apparently-To: schultz@halley.serc.3m.com

John,

In sci.math.num-analysis you write:

>Does anyone have suggestions on optimal packing techniques?

>Specifically I am interested in how to maximize the number of
>arbitrary sized rectangles which can be positioned anywhere on a
>larger, arbitrary sized rectangle.

>Thanks for any help.
>--
>John C. Schultz                    EMAIL: schultz@halley.serc.3m.com


>From what I've seen ,it appears that optimal 2d packing is very expensive and 
most of the algorithms use simplifications such as a guillotine-cutting 
methodology. (I'm working on an automated publication layout system)

References I have found useful are

1) Christofides, N. and Whitlock, C.: An algorithm for the two-dimensionsal
	cutting problem, Ops. Research 25 (1977) 30-44

2) Gilmore P.C. and Gomory R.E. : Multistage cutting stock problems of two and 
	more dimensions, Ops Research ?? 94-120 (See reference in 1)

The above two wrote a number of papers on the Knapsack problem which is related
but imposes no constraints on the number of each size of object. (See 
references in 1)

Hope you find them of some use,

	Peter Davison,
	Expert Solutions Australia.

--
   John C. Schultz   +1 (612) 733-4047   schultz@halley.serc.3m.com
   How to include the taste of Glendronach in a multi-media system?