# Is it possible to reduce the number of variables in bin packing?

The bin packing problem can be formulated as: \begin{align} & \underset{x,y}{\min} & & B = \sum_{i=1}^n y_i\\ & \text{subject to} & & B \geq 1,\\ & & & \sum_{j=1}^n a_j x_{ij} \leq V y_i,\forall i \in \{1,\ldots,n\}\\ & & & \sum_{i=1}^n x_{ij} = 1,\forall j \in \{1,\ldots,n\}\\ & & & y_i \in \{0,1\},\forall i \in \{1,\ldots,n\},\\ & & & x_{ij} \in \{0,1\}, \forall i \in \{1,\ldots,n\}, \, \forall j \in \{1,\ldots,n\},\\ \end{align}

where $y_i = 1$ if bin $i$ is used and $x_{ij} = 1$ if item $j$ is put into bin $i$.

Why do we use $x_{ij}$ and $y_{i}$? We can just use $x_{ij}$.

• if $x_{ij}=1$ than bin $i$ is used and item $j$ is put into bin $i$; and
• if $x_{ij}=0$ than bin $i$ is not used.

Is that correct? If so, why can't I find any formulation with only $x_{ij}$?

• They look equivalent. Definitely $y_i$s look redundant. But the objective (sum of $y_i$s) will be harder to express. – randomsurfer_123 Mar 15 '16 at 22:24
• Try to write an equivalent formulation with $x_{ij}$ and see if it works. You don't need us for that. – Yuval Filmus Mar 15 '16 at 22:27
• I think that if I remove $y_i$ from all the constraints in the optimization problem and replace the objective function by $\sum\limits_{i=1}^n\max\limits_{j}x_{ij}$. That will work. – drzbir Mar 15 '16 at 22:56

An integer program, or more properly an integer linear program, consists of a linear program together with integrality constraints stating that some of the variables are integers. As such, its objective function is always a linear combination of variables.

When the objective is minimization, it is admissible to have $\max$ operators (appearing positively) in the objective function. This means that there is an equivalent proper integer program. This program is obtained by introducing auxiliary variables, just as the variables $y_i$ are introduced in your example to implement $\max_j x_{ij}$.

To answer your question, it all depends on what you consider as an integer program. The standard definition only allows linear objective functions, and in this case the $y_i$ are necessary. If you also allow $\max$ operators in the objective function, then the $y_i$ are not necessary.

Decided to post an answer here:

You can get by with only $x_{ij}$s in this case. However, the objective function now becomes harder to define.

A cleaner way to work with bin packing is to turn it into a decision problem (you can convert it back to optimisation problem by doing a binary search, hence it doesn't add an exponential factor).

• I think the objective function $\sum\limits_{i=1}^n\max\limits_{j}x_{ij}$ will work, right? – drzbir Mar 15 '16 at 22:58
• Oh, Yuval answered that question. You can't use max in classical integer programming. – randomsurfer_123 Mar 17 '16 at 16:30