Is it possible to reduce the number of variables in bin packing? The bin packing problem can be formulated as:
\begin{align}
 &amp; \underset{x,y}{\min}
 &amp; &amp; B = \sum_{i=1}^n y_i\\
 &amp; \text{subject to} 
 &amp; &amp; B \geq 1,\\
 &amp; &amp; &amp; \sum_{j=1}^n a_j x_{ij} \leq V y_i,\forall i \in \{1,\ldots,n\}\\
    &amp; &amp; &amp; \sum_{i=1}^n x_{ij} = 1,\forall j \in \{1,\ldots,n\}\\
    &amp; &amp; &amp; y_i \in \{0,1\},\forall i \in \{1,\ldots,n\},\\
    &amp; &amp; &amp; 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}$?
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.