Cheap and Secure Web Hosting Provider : See Now

[Solved]: Is it possible to reduce the number of variables in bin packing?

, , No Comments
Problem Detail: 

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

Asked By : Azzo

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/54516

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback