Content deleted Content added
Badgerific (talk | contribs) |
|||
Line 11:
In the following, we have ''n'' kinds of items, <math>x_1</math> through <math>x_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_i</math>. For a bin <math>b_i</math>, each item <math>x_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'' 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_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_i \qquad i=1, \ldots, m</math>;
| |||