473,225 Members | 1,375 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,225 software developers and data experts.

Bin packing problem

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.

Oct 30 '06 #1
9 5820

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.
Oct 31 '06 #2
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.

Oct 31 '06 #3
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.
js*******@attglobal.net
==================
Oct 31 '06 #4
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.
js*******@attglobal.net
==================
Oct 31 '06 #5
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.
js*******@attglobal.net
==================
Oct 31 '06 #6

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.
js*******@attglobal.net
==================
Oct 31 '06 #7
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.
js*******@attglobal.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.
js*******@attglobal.net
==================
Oct 31 '06 #8
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.

Nov 1 '06 #9

Thanks for the feedback fellas.

Nov 1 '06 #10

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

0
by: ZaGras | last post by:
after i pack my vb program using package and deployment wizard, i try to install the program on other computer instead of my computer and run the program. when i click to add a new record to the...
0
by: William Goedicke | last post by:
Dear Y'all - I'm need to "unpack" fields in a data file that was created with COBOL on an OpenVMS machine. I've tried Convert::IBM390 but it appears that the packing algorithm is different. ...
0
by: nobull | last post by:
Google won't let me post this as a follow-up but lynch@agere.com (lynto) wrote in message news:<503469eb.0407271148.7ee4b0ca@posting.google.com>... > Does anyone have an algorithm for packing...
2
by: gbb0330 | last post by:
Hi all I need some advice. the daily packing number will be used to match a box with its label. the guys in the warehouse will get a list of items to pack. they will find the item - put it...
1
by: gbb0330 | last post by:
hi guys -the code (all capital letters) generates daily packing number, it is in the on click event of a command button that moves to the next record. dpkn is unbound control - i use it to...
2
by: FMorales | last post by:
Hello all, quick hopefully easy question. Here goes. I've started on the Art Of Assembly tutorial(s) (http://webster.cs.ucr.edu/Page_asm/0_ArtOfAsm.html) and got to the sample projects and kinda...
18
by: Edward Diener | last post by:
Is the packing alignment of __nogc classes stored as part of the assembly ? I think it must as the compiler, when referencing the assembly, could not know how the original data is packed otherwise....
1
by: Gajendra | last post by:
How does the byte packing and the byte alignment work in VC++ compiler? What is the effect of #pragma pack(n) on the alignment and byte packing for example while using the structur struc double...
1
by: QbProg | last post by:
Hello, what I'm saying here is about VS 2005 WITHOUT service pack. I have two DLL projects, with EXACTLY the same project preferences and settings. Both have alignment set to "default", it...
0
by: veera ravala | last post by:
ServiceNow is a powerful cloud-based platform that offers a wide range of services to help organizations manage their workflows, operations, and IT services more efficiently. At its core, ServiceNow...
0
by: jianzs | last post by:
Introduction Cloud-native applications are conventionally identified as those designed and nurtured on cloud infrastructure. Such applications, rooted in cloud technologies, skillfully benefit from...
0
by: mar23 | last post by:
Here's the situation. I have a form called frmDiceInventory with subform called subfrmDice. The subform's control source is linked to a query called qryDiceInventory. I've been trying to pick up the...
0
by: abbasky | last post by:
### Vandf component communication method one: data sharing ​ Vandf components can achieve data exchange through data sharing, state sharing, events, and other methods. Vandf's data exchange method...
2
by: jimatqsi | last post by:
The boss wants the word "CONFIDENTIAL" overlaying certain reports. He wants it large, slanted across the page, on every page, very light gray, outlined letters, not block letters. I thought Word Art...
0
by: stefan129 | last post by:
Hey forum members, I'm exploring options for SSL certificates for multiple domains. Has anyone had experience with multi-domain SSL certificates? Any recommendations on reliable providers or specific...
0
Git
by: egorbl4 | last post by:
Скачал я git, хотел начать настройку, а там вылезло вот это Что это? Что мне с этим делать? ...
1
by: davi5007 | last post by:
Hi, Basically, I am trying to automate a field named TraceabilityNo into a web page from an access form. I've got the serial held in the variable strSearchString. How can I get this into the...
0
by: MeoLessi9 | last post by:
I have VirtualBox installed on Windows 11 and now I would like to install Kali on a virtual machine. However, on the official website, I see two options: "Installer images" and "Virtual machines"....

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.