<p>Your problem is at least as hard as bin-packing.  In particular, optimizing objective (a) basically <em>is</em> <a href="https://en.wikipedia.org/wiki/Bin_packing_problem" rel="nofollow noreferrer">the bin-packing problem</a> (in particular, bin packing is the special case where all drums have equal length, so your problem is at least as hard as bin packing), which is known to be NP-complete.  Consequently, your problem is NP-hard, too.  All the usual hardness results about bin packing apply to your problem as well: there is no polynomial-time approximation scheme (unless P=NP); and bin packing is known to be <a href="https://en.wikipedia.org/wiki/Strong_NP-completeness" rel="nofollow noreferrer">strongly NP-complete</a>, so there is no hope for a pseudo-polynomial time solution, either.</p>

<p>If you want a pragmatic approach to solve this in practice, or at least get as good a solution as possible, I would recommend formulating it as an instance of integer linear programming (ILP) and applying an off-the-shelf ILP solver.  In particular, you can formulate the problem of minimizing objective (a) as an ILP instance, in <a href="https://en.wikipedia.org/wiki/Bin_packing_problem" rel="nofollow noreferrer">the same way as for bin-packing</a>.  Then, off-the-shelf ILP solvers might be effective: even if they don't find the optimal solution, they typically have a way to output the best solution found after a certain amount of computation time, and that might be pretty close to optimal.  Of course, it is not a silver bullet; in the worst case it might take exponential time.  There's no way to know in advance whether it will work well enough.  The only way to tell is to try it and see.</p>

<p>Objective (b) amounts to maximizing a sum-of-squares objective function (per <a href="https://cstheory.stackexchange.com/questions/38003/interesting-real-life-problem-similar-to-subsetsum-bin-packing-problem?noredirect=1#comment85407_38003">your comment</a>).  This can't be expressed using integer linear programming, but it can be expressed as an instance of quadratic integer linear programming.  You could try formulating it as an instance of mixed-integer quadratic programming (MIQP) and then applying an <a href="https://en.wikipedia.org/wiki/Quadratic_programming#Solvers_and_scripting_.28programming.29_languages" rel="nofollow noreferrer">off-the-shelf MIQP solver</a>.  However, MIQP is substantially harder than ILP, so I don't know whether it will work well on problem instances of the size you have.</p>

CC BY-SA 3.0
2017-04-17T17:59:08.147Z
2017-04-17T17:59:08.147Z
D.W.
<p>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 :</p>

<p>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.</p>

<p>I have to cut a large number of cables of different lengths (that randomly varies from 10 meter to 1000 meter). </p>

<p>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.</p>

<p>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. </p>

<p>However, this is not the most optimum solution for the following reasons :</p>

<p>(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.</p>

<p>(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.</p>

<p>(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)</p>

<p>Can anybody please guide me with some ways to improve the situation. </p>

CC BY-SA 3.0
2017-04-17T06:57:16.573Z
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.
CC BY-SA 3.0
2017-04-17T09:44:26.503Z
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.
kaushik Ray
CC BY-SA 3.0
2017-04-17T17:00:26.973Z
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.
kaushik Ray
CC BY-SA 3.0
2017-04-17T17:19:01.230Z
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.
<combinatorics><subset-sum>
Interesting real life problem similar to subsetsum /bin packing problem
kaushik Ray
# Interesting real life problem similar to subsetsum /bin packing problem

(Asked by: username_0 on 2017-04-16)

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.

**Tags:** combinatorics, subset-sum
> **Comments:**
> **username_1**: 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).  
> **username_0**: 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.  
> **username_0**: 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.  
> **username_1**: 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.  

---

## 1 answers

### Answer by username_1 on 2017-04-17. Score: 4

Your problem is at least as hard as bin-packing. In particular, optimizing objective (a) basically *is* [the bin-packing problem](https://en.wikipedia.org/wiki/Bin_packing_problem) (in particular, bin packing is the special case where all drums have equal length, so your problem is at least as hard as bin packing), which is known to be NP-complete. Consequently, your problem is NP-hard, too. All the usual hardness results about bin packing apply to your problem as well: there is no polynomial-time approximation scheme (unless P=NP); and bin packing is known to be [strongly NP-complete](https://en.wikipedia.org/wiki/Strong_NP-completeness), so there is no hope for a pseudo-polynomial time solution, either.

If you want a pragmatic approach to solve this in practice, or at least get as good a solution as possible, I would recommend formulating it as an instance of integer linear programming (ILP) and applying an off-the-shelf ILP solver. In particular, you can formulate the problem of minimizing objective (a) as an ILP instance, in [the same way as for bin-packing](https://en.wikipedia.org/wiki/Bin_packing_problem). Then, off-the-shelf ILP solvers might be effective: even if they don't find the optimal solution, they typically have a way to output the best solution found after a certain amount of computation time, and that might be pretty close to optimal. Of course, it is not a silver bullet; in the worst case it might take exponential time. There's no way to know in advance whether it will work well enough. The only way to tell is to try it and see.

Objective (b) amounts to maximizing a sum-of-squares objective function (per [your comment](https://cstheory.stackexchange.com/questions/38003/interesting-real-life-problem-similar-to-subsetsum-bin-packing-problem?noredirect=1#comment85407_38003)). This can't be expressed using integer linear programming, but it can be expressed as an instance of quadratic integer linear programming. You could try formulating it as an instance of mixed-integer quadratic programming (MIQP) and then applying an [off-the-shelf MIQP solver](https://en.wikipedia.org/wiki/Quadratic_programming#Solvers_and_scripting_.28programming.29_languages). However, MIQP is substantially harder than ILP, so I don't know whether it will work well on problem instances of the size you have.


---

