**Next message:**K. Kaisha Halcli: "AAROFLEX RESPONDS TO ALLEGED LITIGATION"**Previous message:**Derek Harrell: "rp memail"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

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).

Ilkka

--------------------------------------------------------------

*>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).
*

Gill.

------------------------------------------------------------------------

**Next message:**K. Kaisha Halcli: "AAROFLEX RESPONDS TO ALLEGED LITIGATION"**Previous message:**Derek Harrell: "rp memail"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

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