15,877,051 members
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)

Regards

What I have tried:

Tried with dynamic algorithm for subset sum problem
Posted
Updated 15-Mar-17 10:40am
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.

Solution 1

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.