# Interesting real life problem similar to subsetsum /bin packing problem

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 (let's say in the order of 10,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 10 meter to 1000 meter).

I want to allocate the cables to these drums with two objectives viz. (a) minimize wastage or minimize total drums 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)

Can anybody please guide me with some ways to improve the situation.

• Normally, you can't simultaneously optimize one objective. To make the problem well-defined, you'll need to define a single objective function (e.g., pick one to minimize, or describe how to form a weighted combination of them, or something).
– D.W.
Apr 17, 2017 at 6:57
• Thanks for your comment. I'm able to optimise to the extreme (let's say, Zero wastage) once first drum is picked up. I need to delete those cables now from the set of cables for the next drum to allocate. However, I could have chosen another probable combination for the first drum that also produce Zero wastage and left with different set of cables for the next drum. Now as the number of possible combinations that makes zero wastage for the first drum would generally be very large, its impractical for me to check every possible combination for each drum. Apr 17, 2017 at 9:44
• Thank you somuch once again. Actually you are right, I meant, minimise drums (not the cables used; my mistake) required to allocate all cables. This is objective (a). Objective (b) is a bit tricky as you rightly pointed out. In this case, I would take the sum of square of the wastage and try to maximise it. This would give me more weightage for the bigger wastage (as sum of wastage is same, whatever way I allocate).Alternatively, product of all wastage can also be an indicator- as small as better. I've already achieved that by dynamic programming, I need help for points 1 to 3 mentioned above. Apr 17, 2017 at 17:00
• OK. Can you edit the question accordingly? There's an "edit" link under your post. We want questions to read well for someone who encounters them for the first time, and to be self-contained (people shouldn't need to read the comments to understand your question). Don't bother marking what has changed: the site has built-in revision history for that.
– D.W.
Apr 17, 2017 at 17:19