The Art Gallery Guardian

Filling up a bin using balls with divisible weights


This post shows how to solve the special case for this problem. The special case has exactly one bin, and each ball have weight a power of 22. It is one of the most popular unanswered problem on cs.stackexchange as of writing.

Problem1

We are interested in solving the following integer program, Minimize:i=1nxiaisubject to:i=1nwixi=c0xibi for all 1in.\begin{aligned} \text{Minimize:} & \sum_{i=1}^n |x_i-a_i| \\ \text{subject to:} & \sum_{i=1}^n w_i x_i = c\\ & 0\leq x_i \leq b_i \text{ for all } 1\leq i \leq n. \end{aligned} where each wiw_i is a power of 22 for all 1in1\leq i\leq n. Assume wiwi+1w_i\leq w_{i+1}.

In fact, we do not require the wiw_is are powers of 22. We can establish polynomial time as long as wi+1/wiw_{i+1}/w_i is bounded by a polynomial in terms of the input size for all ii. However, for simplicity of exposition, assume wiw_is are powers of 22. We do not know the case when wi+1/wiw_{i+1}/w_i is unbounded.

Consider a more natural problem without the absolute values.

Problem200-11 exact knapsack problem with divisible weights

We are interested in solving the following integer program, Minimize:i=1ncixisubject to:i=1nwixi=txi{0,1} for all 1in\begin{aligned} \text{Minimize:} & \sum_{i=1}^n c_i x_i \\ \text{subject to:} & \sum_{i=1}^n w_i x_i = t\\ & x_i \in \{0,1\} \text{ for all } 1\leq i \leq n\\ \end{aligned}

where wiwi+1w_i|w_{i+1} for all 1in1\leq i\leq n. wiw_i can be negative.

We show Problem 1 reduces to Problem 2 with polynomial blow up, and Problem 2 can be solved in polynomial time.

1 Reduction

The reduction goes through a few steps. We start with the integer program in [Problem 1], and let yi=aixiy_i = a_i-x_i, and we get

Minimize:i=1nyisubject to:i=1nwiyi=i=1nwiaicaibiyiai for all 1in\begin{aligned} \text{Minimize:} & \sum_{i=1}^n |y_i| \\ \text{subject to:} & \sum_{i=1}^n w_i y_i = \sum_{i=1}^n w_i a_i - c\\ & a_i-b_i\leq y_i \leq a_i \text{ for all } 1\leq i \leq n\\ \end{aligned}

Let c=i=1nwiaicc' = \sum_{i=1}^n w_ia_i -c, and li=aibil_i = a_i-b_i and ui=aiu_i = a_i.

Minimize:i=1nyisubject to:i=1nwiyi=cliyiui for all 1in\begin{aligned} \text{Minimize:} & \sum_{i=1}^n |y_i| \\ \text{subject to:} & \sum_{i=1}^n w_i y_i = c'\\ & l_i \leq y_i \leq u_i \text{ for all } 1\leq i \leq n\\ \end{aligned}

Let yi=yi+yiy_i=y_i^+ - y_i^-, where yi,yi+0y_i^-,y_i^+\geq 0, we can remove the absolute value.

Minimize:i=1nyi++yisubject to:i=1nwiyi++i=1nwiyi=cliyi+yiui for all 1inyi,yi+0 for all 1in\begin{aligned} \text{Minimize:} & \sum_{i=1}^n y_i^+ + y_i^- \\ \text{subject to:} & \sum_{i=1}^n w_i y_i^+ + \sum_{i=1}^n -w_i y_i^- = c'\\ & l_i \leq y_i^+- y_i^- \leq u_i \text{ for all } 1\leq i \leq n\\ & y_i^-, y_i^+\geq 0 \text{ for all } 1\leq i \leq n\\ \end{aligned}

Observe that we can separate the inequalities involving yi+yiy_i^+ - y_i^-, because there is always an optimal where yiy_i^- or yi+y_i^+ is 00.

Remark

This observation fails when the number of bins is more than 11.

Minimize:i=1nyi++yisubject to:i=1nwiyi++i=1nwiyi=c0yi+ui for all 1in0yili for all 1in\begin{aligned} \text{Minimize:} & \sum_{i=1}^n y_i^+ + y_i^- \\ \text{subject to:} & \sum_{i=1}^n w_i y_i^+ + \sum_{i=1}^n -w_i y_i^- = c'\\ & 0 \leq y_i^+ \leq u_i \text{ for all } 1\leq i \leq n\\ & 0 \leq y_i^- \leq -l_i \text{ for all } 1\leq i \leq n\\ \end{aligned}

This is an integer program as a bounded exact knapsack problem.

Minimize:i=1nxisubject to:i=1nwixi=c0xibi for all 1in\begin{aligned} \text{Minimize:} & \sum_{i=1}^n x_i \\ \text{subject to:} & \sum_{i=1}^n w_i x_i = c\\ & 0 \leq x_i \leq b_i \text{ for all } 1\leq i \leq n\\ \end{aligned}

Finally, apply the standard technique that rewrites a bounded knapsack problem to 00-11-knapsack problem (see Section 7.1.1 of [1]). The blow up in problem size is at most a factor of O(logmaxibi)O(\log \max_i b_i). We can get the integer program in Problem 2, and also the weights are all powers of 22. The reduction runs in polynomial time with respect to input size.

2 Solving Problem 2

Yuzhou Gu noted that the integer program in Problem 2 has a dynamic programming solution.

Let D[m,k]D[m,k] to be the optimal value to the following problem

Minimize:j=1mcjxjsubject to:j=1mwjxj=kwm+tmodwmxj{0,1} for all 1jm\begin{aligned} \text{Minimize:} & \sum_{j=1}^m c_j x_j \\ \text{subject to:} & \sum_{j=1}^m w_j x_j = k |w_m| + t \bmod |w_m|\\ & x_j \in \{0,1\} \text{ for all } 1\leq j \leq m\\ \end{aligned}

The claim is that D[m,k]D[m,k] can be expressed by the following recurrence relation.

D[m,k]=minxm{0,1}D[m1,wmkwmxm+(tmodwmtmodwm1)wm1] D[m,k] = \min_{x_m\in \{0,1\}} D\left[m-1,\frac{|w_m|k- w_m x_m+(t\bmod |w_m| - t\bmod |w_{m-1}|)}{|w_{m-1}|}\right]

Note that k|k| is at most mm. Therefore the table has at most O(n2)O(n^2) entries. To obtain the solution to the original equation, we find the minimum overall D[n,k]D[n, k]. Clearly, this runs in polynomial time.

References

[1] H. Kellerer, U. Pferschy, D. Pisinger, Knapsack problems, Springer, 2004.

Posted by Chao Xu on .
Tags: optimization, integer.