2
$\begingroup$

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}$?

|cite|improve this question
$\endgroup$
  • $\begingroup$ They look equivalent. Definitely $y_i$s look redundant. But the objective (sum of $y_i$s) will be harder to express. $\endgroup$ – randomsurfer_123 Mar 15 '16 at 22:24
  • 1
    $\begingroup$ Try to write an equivalent formulation with $x_{ij}$ and see if it works. You don't need us for that. $\endgroup$ – Yuval Filmus Mar 15 '16 at 22:27
  • $\begingroup$ 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. $\endgroup$ – drzbir Mar 15 '16 at 22:56
3
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
2
$\begingroup$

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).

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

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.