Generalized assignment problem: Difference between revisions

Revision as of 13:54, 24 April 2015

Revision as of 14:05, 17 June 2015

Line 9:

==Definition==

In the following, we have ''n'' kinds of items, <math>x_1a_1</math> through <math>x_na_n</math> and ''m'' kinds of bins <math>b_1</math> through <math>b_m</math>. Each bin <math>b_i</math> is associated with a budget <math>w_it_i</math>. For a bin <math>b_i</math>, each item <math>x_ja_j</math> has a profit <math>p_{ij}</math> and a weight <math>w_{ij}</math>. A solution is a subset of items ''U'' and an assignment from ''U''items to the bins. A feasible solution is a solution in which for each bin <math>b_i</math> the total weight of assigned items is at most <math>w_it_i</math>. The solution's profit is the sum of profits for each item-bin assignment. The goal is to find a maximum profit feasible solution.

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>

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

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

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