Bin packing problem

**Marcin Dobrucki** · Oct 31 '06, 07:35 AM

Re: Bin packing problem

This has "homework" written all over it. I think you will need to
work it out for yourself.

fraz wrote:

Does anyone have code to solve a 3-d bin packing problem in php? I am
trying to solve the issue of packing various sized rectangular shaped
objects into boxes of three different sizes so as to use as few packing
peanuts as possible (to some reasonable approximation) to fill the
gaps.
>
I have found some c code and plenty of discussions on the subject, but
I was thinking that someone out there has to have done this in php
already.
>
FWIW, this would be off-line bin packing, and there are no "this side
up" or weight constraints.
>

**fraz** · Oct 31 '06, 01:25 PM

Re: Bin packing problem

Marcin Dobrucki wrote:

This has "homework" written all over it. I think you will need to
work it out for yourself.

Sounds like it, but this is for a real issue. I work at a brewery, we
ship all kinds of stuff (albeit, not the beer), and we want to keep the
shipping costs as low as possible for the purchaser by optimizing the
number of packages sent (as the first pound is always the costliest)
while concurrently reducing the amount of packaging materials needed
(peanuts, bubble wrap, etc.).

I have found an implementation in c for a version of this that isn't
quite what I need, and if I were to use it I would need to write a php
extension or pull out of safe-mode to run system/exec calls.

I guess it just seems like there have to have been some people who have
tackled this before considering how many on-line sales sites are out
there written in php, and any help would be appreciated by this
overworked sysadmin/programmer/dbadmin/graphic designer/cable
runner/taste tester who has, unfortunately, very little time to pore
over white papers titled "Guided local search for the three-dimensional
bin packing problem" trying to rekindle my memory on Big-O notation and
figure out how to convert this into applicable code.

**Jerry Stuckle** · Oct 31 '06, 02:35 PM

Re: Bin packing problem

fraz wrote:

Marcin Dobrucki wrote:
>

>>This has "homework" written all over it. I think you will need to
>>work it out for yourself.

>
>
Sounds like it, but this is for a real issue. I work at a brewery, we
ship all kinds of stuff (albeit, not the beer), and we want to keep the
shipping costs as low as possible for the purchaser by optimizing the
number of packages sent (as the first pound is always the costliest)
while concurrently reducing the amount of packaging materials needed
(peanuts, bubble wrap, etc.).
>
I have found an implementation in c for a version of this that isn't
quite what I need, and if I were to use it I would need to write a php
extension or pull out of safe-mode to run system/exec calls.
>
I guess it just seems like there have to have been some people who have
tackled this before considering how many on-line sales sites are out
there written in php, and any help would be appreciated by this
overworked sysadmin/programmer/dbadmin/graphic designer/cable
runner/taste tester who has, unfortunately, very little time to pore
over white papers titled "Guided local search for the three-dimensional
bin packing problem" trying to rekindle my memory on Big-O notation and
figure out how to convert this into applicable code.
>

Ah, that makes it simple. No PHP code needed. Just:

1. Place items in compactor
2. Activate compactor
3. Wrap results in brown paper.

No boxes and no peanuts required. And you can blame the damage on the
shipping company :-)

Seriously - I haven't seen anything like that in PHP. But I wouldn't
think it would be too hard to convert. Do you have some examples of the
C code?

--
=============== ===
Remove the "x" from my email address
Jerry Stuckle
JDS Computer Training Corp.
jstucklex@attgl obal.net
=============== ===

**fraz** · Oct 31 '06, 04:25 PM

Re: Bin packing problem

Seriously - I haven't seen anything like that in PHP. But I wouldn't

think it would be too hard to convert. Do you have some examples of the
C code?

<a
href="http://www.diku.dk/~pisinger/3dbpp.c">http://www.diku.dk/~pisinger/3dbpp.c</a>

I have been checking out this code for the last day when I have time.
It apparently restricts objects to not be rotatable, and the bins to
fill are all of the same size. So, in those two respects it is not
applicable, but I have hopes to modify it to my needs as a last resort.
It's just a bit dense, but I didn't necessarily expect anything less
out of the problem.

One constraint though that I could throw into the mix is that I don't
expect n (no. of items to pack) to exceed, say, 25 in all but the most
unusual scenarios. Hence, I could get by with a hacky brute force
heuristic that errs on the side of simpler code rather than an elegant
algorithm that approaches a "log n" efficiency. Ultimately, I just want
to be able to abstract the items that are to be packed so that the
addition of new types of items doesn't throw the whole procedure and
require a rewrite.

>
--
=============== ===
Remove the "x" from my email address
Jerry Stuckle
JDS Computer Training Corp.
jstucklex@attgl obal.net
=============== ===

**Jerry Stuckle** · Oct 31 '06, 05:15 PM

Re: Bin packing problem

fraz wrote:

>>Seriously - I haven't seen anything like that in PHP. But I wouldn't
>>think it would be too hard to convert. Do you have some examples of the
>>C code?

>
>
<a
href="http://www.diku.dk/~pisinger/3dbpp.c">http://www.diku.dk/~pisinger/3dbpp.c</a>
>
I have been checking out this code for the last day when I have time.
It apparently restricts objects to not be rotatable, and the bins to
fill are all of the same size. So, in those two respects it is not
applicable, but I have hopes to modify it to my needs as a last resort.
It's just a bit dense, but I didn't necessarily expect anything less
out of the problem.
>
One constraint though that I could throw into the mix is that I don't
expect n (no. of items to pack) to exceed, say, 25 in all but the most
unusual scenarios. Hence, I could get by with a hacky brute force
heuristic that errs on the side of simpler code rather than an elegant
algorithm that approaches a "log n" efficiency. Ultimately, I just want
to be able to abstract the items that are to be packed so that the
addition of new types of items doesn't throw the whole procedure and
require a rewrite.
>
>

Yuk! Some of the worst C code I've ever seen. Virtually no comments,
meaningless single character variable names and even the function names
are cryptic. I'm sure it works - but I'd hate to have to spend the time
understanding the code. And quite frankly I'd be embarrassed to even
post it.

But back to your problem. Brute force might be the easiest way.
Figuring you have 3 different orientations of the packages (assuming
they have symmetric shapes), a recursive routine might work. And as
long as you don't have to make too many calculations it should be
relatively fast.

--
=============== ===
Remove the "x" from my email address
Jerry Stuckle
JDS Computer Training Corp.
jstucklex@attgl obal.net
=============== ===

**fraz** · Oct 31 '06, 06:55 PM

Re: Bin packing problem

Jerry Stuckle wrote:

Yuk! Some of the worst C code I've ever seen. Virtually no comments,
meaningless single character variable names and even the function names
are cryptic. I'm sure it works - but I'd hate to have to spend the time
understanding the code. And quite frankly I'd be embarrassed to even
post it.
>
But back to your problem. Brute force might be the easiest way.
Figuring you have 3 different orientations of the packages (assuming
they have symmetric shapes), a recursive routine might work. And as
long as you don't have to make too many calculations it should be
relatively fast.
>

thanks for taking a look.

--
=============== ===
Remove the "x" from my email address
Jerry Stuckle
JDS Computer Training Corp.
jstucklex@attgl obal.net
=============== ===

**Jerry Stuckle** · Oct 31 '06, 08:55 PM

Re: Bin packing problem

fraz wrote:

>>Seriously - I haven't seen anything like that in PHP. But I wouldn't
>>think it would be too hard to convert. Do you have some examples of the
>>C code?

>
>
<a
href="http://www.diku.dk/~pisinger/3dbpp.c">http://www.diku.dk/~pisinger/3dbpp.c</a>
>
I have been checking out this code for the last day when I have time.
It apparently restricts objects to not be rotatable, and the bins to
fill are all of the same size. So, in those two respects it is not
applicable, but I have hopes to modify it to my needs as a last resort.
It's just a bit dense, but I didn't necessarily expect anything less
out of the problem.
>
One constraint though that I could throw into the mix is that I don't
expect n (no. of items to pack) to exceed, say, 25 in all but the most
unusual scenarios. Hence, I could get by with a hacky brute force
heuristic that errs on the side of simpler code rather than an elegant
algorithm that approaches a "log n" efficiency. Ultimately, I just want
to be able to abstract the items that are to be packed so that the
addition of new types of items doesn't throw the whole procedure and
require a rewrite.
>
>

>>--
>>============= =====
>>Remove the "x" from my email address
>>Jerry Stuckle
>>JDS Computer Training Corp.
>>jstucklex@att global.net
>>============= =====

>
>

I thought about it some more. And really, your problem isn't much
different than the historic traveling salesman (a salesman has to visit
X cities - what's the shortest distance he has to travel to visit all
cities). It's a great puzzle - and one which has never been solved
except by brute force, AFAIK.

And I think that's what you're going to have to do here, unfortunately.

--
=============== ===
Remove the "x" from my email address
Jerry Stuckle
JDS Computer Training Corp.
jstucklex@attgl obal.net
=============== ===

**Moot** · Nov 1 '06, 01:05 PM

Re: Bin packing problem

Jerry Stuckle wrote:

I thought about it some more. And really, your problem isn't much
different than the historic traveling salesman (a salesman has to visit
X cities - what's the shortest distance he has to travel to visit all
cities). It's a great puzzle - and one which has never been solved
except by brute force, AFAIK.
>
And I think that's what you're going to have to do here, unfortunately.
>

If you want to get the *best* possible packaging solution, then like
you say, there's just no way around it...you're going to have to expand
the entire search tree. But, if you could be satisfied with the best
solution chosen from a subset of all solutions, then a
heuristic-directed A* search could be a good candidate.

Without delving deeper into the problem, a good starting heurstic would
simply be the amount of empty space left in the package. Keep
expanding the tree and following the branch dictated by the heuristic
until you get to a point where you can fit no more packages, and
declare that a possible solution. Backtrack out of the solution (how
far to back out will depend upon how similar you want your solution
subset to be...further = a more diverse set). Repeat X times to get
however many possible solutions you want to have, then choose the best
one as your actual packaging setup.

As I said, if you don't need the actual best solution, but only a
*good* solution, then this approach would save you processing time and
memory because you don't have to examine all possible options, just the
most promising ones.

**fraz** · Nov 1 '06, 07:35 PM

Re: Bin packing problem

Thanks for the feedback fellas.

Bin packing problem

Bin packing problem

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment