1
$\begingroup$

Let us say the optimization version of the bin packing problem asks you to give a packing using the fewest bins possible and the decision version asks if it is possible to pack the bins into $k$ bins.

How can you reduce the optimization version to the decision version?

If you only have to answer what the fewest bins possible is then it is clear you can use binary search. But if you actually have to give the packing, I can't see how to do it.

$\endgroup$
2
$\begingroup$

If you could solve the decision problem (do these items fit in k bins) you can obviously solve the optimisation problem (what is the minimum number of bins) using binary search. But you actually want to know what to put into each box. That’s easily done doing the decision problem at most n^2 times.

Let’s say you know k boxes are required and sufficient. Sort the item by descending size. Replace the biggest and second biggest item with one item of their combined size and check if the new items fit into k bins. If not, try the largest and third largest item, and so on. After n attempts, you either know two items that are in the same bin in an optimal solution, or you know the largest item is on its own. And you repeat that, each time you find that you can put two items in the same bin by solving at most n decision problems.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This looks like a very nice trick. Thank you. $\endgroup$ – Anush May 29 '19 at 8:12
1
$\begingroup$

This answer will probably be quite annoying...

To be explicit, your bin packing problem is: find a way of assigning items of size $s_1, \dots, s_k$, to the minimum number of bins such that no bin contains items of total size more than $t$.

Consider the following problem, Non-Uniform Bin Packing: the input is a list of bin sizes and item sizes and we want to know if we can put all the items in the bins so no bin is overflowing. This problem is clearly in NP: an assignment of items to bins is of polynomial size with respect to the input, and we can check in polynomial time if none of the bins are overflowing. Since this problem is in NP, it can be reduced to Bin Packing, which is NP-complete. (This is the annoying part: I've not said how to perform this reduction, because I've not managed to figure it out.)

We can use Non-Uniform Bin Packing to solve your problem in the usual way. We build up the solution by asking, for each item in turn, whether that item can go in each bin. First, as you describe, use binary search to find out how many bins we need; call this $d$. Then, suppose we have a partial solution, in which we have placed items $1, \dots, i$ into bins, and the remaining capacities of the bins are $c_1, \dots, c_d$ (our initial partial solution is that $i=0$, i.e., we've placed no items, and the remaining capacities are $t, \dots, t$). Then, just try placing the $(i+1)$st item in each bin in turn until the Non-Uniform Bin Packing algorithm says that there is a solution for items $i+2, \dots, k$ in the remaining bin capacities. That is, we ask in turn if items $i+2, \dots, k$ can be placed in bins with capacities $c_1-s_{i+1}, c_2, \dots, c_d$, then $c_1, c_2-s_{i+1}, c_3, \dots, c_d$, then ... and finally $c_1, \dots, c_{d-1}, c_d-s_{i+1}$. Do this until you've placed each item and you have your assignment.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Doesn't this suggest that optimal solutions to non-uniform bin packing are nested, in the sense that the optimal allocation of $i$ items is the same in the $i$-item problem as it is in the $(i+1)$-item problem? $\endgroup$ – LarrySnyder610 May 29 '19 at 0:16
  • 1
    $\begingroup$ Thank you although, as you say, this does still leave a large gap. I hope someone can fill it. $\endgroup$ – Anush May 29 '19 at 6:36
  • $\begingroup$ @LarrySnyder610 I'm not sure what you mean. The algorithm I describe uses different bin sizes for the $i$-item and $(i+1)$-item problems. Essentially, it's saying "If I put this item in this bin, can I fit the remaining items in the remaining space? If it's possible to solve the $(i+1)$-item problem by putting item $1$ in bin $j$, it must be possible to put items $2, \dots, i+1$ in bins of size $c_1, \dots, c_{j-1}, (c_j-s_i), c_{j+1}, \dots, c_d$. $\endgroup$ – David Richerby May 29 '19 at 8:36
  • $\begingroup$ I agree that in that case it's possible to put items $2, \ldots, i+1$ in those bins, but my question is whether it is optimal to do so. I believe your algorithm is greedy -- once we put item $i$ in bin $j$, we will never consider taking it out and putting it into a different bin. But a greedy algorithm should not be optimal for NUBP. So if you don't solve the $i$-item problem optimally, you might run out of room for the remaining items, even though a solution with $d$ bins exists. $\endgroup$ – LarrySnyder610 May 29 '19 at 18:52
-2
$\begingroup$

There is some inconsistency about whether, in the context of complexity analysis, an optimization problem is defined as asking for the optimal solution or the optimal objective function value. For example, Wikipedia's entry on decision problems says:

There are standard techniques for transforming function and optimization problems into decision problems. For example, in the traveling salesman problem, the optimization problem is to produce a tour with minimal weight. The associated decision problem is: for each $N$, to decide whether the graph has any tour with weight less than $N$. By repeatedly answering the decision problem, it is possible to find the minimal weight of a tour.

The second sentence defines the optimization problem as producing the optimal tour, whereas the last sentence implicitly defines it as producing the weight of the optimal tour.

Similarly, the entry on optimization problems says:

For example, if there is a graph $G$ which contains vertices $u$ and $v$, an optimization problem might be "find a path from $u$ to $v$ that uses the fewest edges". This problem might have an answer of, say, 4.

But 4 is not an "answer" to the problem of "find[ing] a path". So, this quote, too, is inconsistent about whether the optimization problem means finding the optimal solution or finding the optimal objective function value.

I am not trying to wade into a debate here about the quality of Wikipedia entries; I'm just trying to make the point that in common usage, there is an inconsistency about the way "optimization problem" is used, and that inconsistency can lead to confusion about the relationship between decision and optimization problems.

Now, back to your original question. If what you are asking is:

How can you reduce the "find the optimal solution" version of the optimization problem to the decision problem?

then I don't know of a way to do this, though @David Richerby gives one in his answer.

If what you are asking is:

How can you reduce the "find the optimal objective function" version of the optimization problem to the decision problem?

then the answer is, using binary search, as you have pointed out.

And if what you are really asking is:

Why does everyone say you can reduce the optimization problem to the decision problem, when it seems impossible?

then my answer is, when people say you can reduce the optimization problem to the decision problem, they mean the "find the optimal objective function" version of the optimization problem, but they are not always sufficiently clear in articulating that.

Now, from a practical perspective, if you are actually going to solve the decision problem, you usually run some algorithm that determines whether the items can be packed into $k$ bins. That algorithm is most likely going to do the packing, so in the course of your binary search, you will find the actual packings.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The question explicitly asks about finding which items go in which bin, not just computing the minimum number of bins. $\endgroup$ – David Richerby May 28 '19 at 22:47
  • $\begingroup$ True, but I guess I am saying that’s an inconsistent pair of definitions (of the two problems), and that that’s part of where the confusion stems from. $\endgroup$ – LarrySnyder610 May 28 '19 at 22:51
  • $\begingroup$ It's not inconsistent or confused. The question gives two natural problems and asks how to reduce one to the other. I get that you'd rather reduce between two different problems, but that's not what the question is about, and the asker already mentions reducing the your version of the optimization problem to the decision problem. $\endgroup$ – David Richerby May 28 '19 at 22:53
  • $\begingroup$ Revised to better explain my argument, and why I think the question arises because of an inconsistency in the way the term "optimization problem" is used. $\endgroup$ – LarrySnyder610 May 28 '19 at 23:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.