Re: RP and packing problem A

From: Ilkka Tapio Ikonen (
Date: Tue Jan 14 1997 - 23:16:22 EET

There is not much I can add to what Gill said about complexity of the problem
in hand (included below). No, I'm not expecting myself to proof something that
matematicians sped their life times with :-).

Even though this is a very hard problem, it is also very common one in its
various different forms (bin packing, scheduling, stock cutting, area layout,
sheet metal cutting etc). There are several different methods to solve
these classical OR problems, some optimally, some close to optimum. I am
looking for a good solution, which satisfies requirements for each batch of
parts. Addition to being NP-hard in its basic formulation,
complexity of part geometries introduces new difficulties.I am using STL
files directly, i.e. part geometry is represented as accurately as in a RP
machine (no bounding boxes needed).


>It will be *very* surprising if Ilkka gives a *polynomial*-time algorithm
>for solving the 3D packing problem and proves it always finds an optimal
>solution. The 1D analog of the problem (the "bin-packing" problem) already
>belongs to the so-called NP-Complete class of problems: find a
>polynomial-time algorithm (that is, an algorithm whose running time is
>proportional to a polynomial in the size of the input), and you found such
>an algorithm for thousands of problems for which only exponential-time
>algorithms are known but no polynomial-time algorithms. Assumptions like
>"all the objects are boxes, and even axis-parallel boxes (no rotations
>allowed)" don't make the problem easier. The question whether there exists
>any polynomial-time algorithm for this class of problems is a long standing
>problem in computational complexity since the late 70's. There is a deep
>theory on *approximation* algorithms for these problems, where you get
>solutions which are, say, (1+epsilon) times the size of the optimal
>solution (assuming minimum is sought).



This archive was generated by hypermail 2.1.2 : Tue Jun 05 2001 - 22:39:13 EEST