Generalized assignment problem: Difference between revisions

Revision as of 21:48, 8 February 2018

Revision as of 01:13, 11 February 2018

Line 12:

Mathematically the generalized assignment problem can be formulated as an [[Integer programming|integer program]]:

:maximize <math>\sum_{i=1}^m\sum_{j=1}^n p_{ij} x_{ij}.</math>

: <math>

:subject to <math>\sum_{j=1}^n w_{ij} x_{ij} \le t_i \qquad i=1, \ldots, m</math>;

\begin{align}

::<math> \sum_{i=1}^m x_{ij} = 1 \qquad j=1, \ldots, n</math>;

:\text{maximize <math>} & \sum_{i=1}^m\sum_{j=1}^n p_{ij} x_{ij}.</math> \\

::<math> x_{ij} \in \{0,1\} \qquad i=1, \ldots, m, \quad j=1, \ldots, n</math>;

:\text{subject to <math>} & \sum_{j=1}^n w_{ij} x_{ij} \le t_i \qquad& & i=1, \ldots, m</math>; \\

::<math>& \sum_{i=1}^m x_{ij} = 1 \qquad& & j=1, \ldots, n</math>; \\

::<math>& x_{ij} \in \{0,1\} \qquad& & i=1, \ldots, m, \quad j=1, \ldots, n</math>;

\end{align}

</math>

== Complexity ==

Line 39 ⟶ 44:

Formally:

: Set <math>T[i]=-1</math> \text{ for all} <math>i = 1\ldots n</math>

: For <math>j=1...,\ldots,m</math> do:

:: Call ALG to find a solution to bin <math>b_j</math> using the residual profit function <math>P_j</math>. Denote the selected items by <math>S_j</math>.

:: Update <math>T</math> using <math>S_j</math>, i.e., <math>T[i]=j</math> for all <math>i \in S_j</math>.