A special case of bin packing problem

Question

1.00/5 (2 votes)

See more:

Dear Experts ,

I have a real life scenario, where I need to solve a construction related problem somewhat similar to bin packing problem.The situation is as follows :

I have large number of cable reels/drums (lets say in the order of 20,000 numbers) each having varying lengths (random lengths between 200 meter to 3,000 meter) of cable in it.

I have to cut a large number of cables of different lengths (that randomly varies from 1 meter to 1000 meter).

I want to allocate the cables to these drums with two objectives viz. (a) minimize wastage or minimize total cable used for the whole allocation (b) Maximize the length of waste cables (e.g. instead of wasting two 10 meter cable, when absolutely necessary, I would try to waste one 20 meter) to increase the chance of re-usability.

I have used a dynamic algorithm (similar to solving a subset sum problem) to find the best fit for a specific cable reel/drum and get a fairly good solution.

However, this is not the most optimum solution for the following reasons :

(1) I don't know at the beginning which drum to take first for the allocation. The sequence at which I start allocation vastly affects the overall wastage.

(2) When there are multiple perfect combinations possible for zero wastage for a particular drum, choosing right combination from that for a overall optimization is my challenge.

(3) I end up making zero wastage for a drum, where I should actually keep some deliberate wastage to use up some specific cable, that will lead me to a over all minimized wastage. That means, making zero wastage for a drum is not necessarily the best solution, (especially when the cable lengths are in the order between 300 to 800 meter)

Seek your help !

Regards

What I have tried:

Tried with dynamic algorithm for subset sum problem

Posted 15-Mar-17 6:36am

Member 13061207

Updated 15-Mar-17 10:40am

Add a Solution

Comments

Richard MacCutchan 15-Mar-17 12:44pm

Sorry we do not do your homework.

Member 13061207 15-Mar-17 12:47pm

Probably you have not gone through the problem . This is not a home work :). I understand this is still an open problem and lot o ppl still work on that. wanted a fresh idea.

Richard MacCutchan 16-Mar-17 4:19am

Well, it is still effectively homework. And as Patrice mentions below, there are books about the subject that you need to study. You cannot expect an answer to such a problem in a Quick Answers forum.

1 solution

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Patrice T · Answer 1 · 2017-03-15T10:40:00

This problem fit in a domain named "Linear Programming with Integer Numbers".
It takes books to explain how efficient algorithms are working. The problem is so difficult that companies are selling programs just to solve this problem.
Integer programming - Wikipedia[^]
Cutting stock problem - Wikipedia[^]

1 solution is to generate all possible combination of cable that fit in each drum length. Then pick ones to minimize waste.

Quote:
I have large number of cable reels/drums (lets say in the order of 20,000 numbers) each having varying lengths (random lengths between 200 meter to 3,000 meter) of cable in it.

The number of drums do nit matters, it is the number of drum length which matters.

Quote:
I have to cut a large number of cables of different lengths (that randomly varies from 1 meter to 1000 meter).

If minimum cable length is 1 meter, waste is drum with shorter cable remaining.