Generalized assignment problem: Difference between revisions

Revision as of 15:11, 6 April 2008

Latest revision as of 21:36, 3 October 2024

(62 intermediate revisions by 47 users not shown)

Line 1:

{{short description|Combinatorial optimization problem}}

{{context}}

In [[applied mathematics]], the maximum '''generalgeneralized assignment problem''' is a problem in [[combinatorial optimization]]. This problem is a [[generalization]] of the [[assignment problem]] in which both [[tasks]] and [[Agent-based model|agents]] have a size. Moreover, the size of each task might vary from one agent to the other.

This problem in its most general form is as follows: There are a number of agents and a number of tasks. Any agent can be assigned to perform any task, incurring some cost and profit that may vary depending on the agent-task assignment. Moreover, each agent has a budget and the sum of the costs of tasktasks assigned to it cannot exceed this budget. It is required to find an assignment in which all agents do not exceed their budget and total profit of the assignment is maximized.

In [[applied mathematics]], the maximum '''general assignment problem''' is a problem in [[combinatorial optimization]]. This problem is a [[generalization]] of the [[assignment problem]] in which both [[tasks]] and [[agents]] have a size. Moreover, the size of each task might vary from one agent to the other.

==SpecialIn special cases==

This problem in its most general form is as follows:

In the special case in which all the agents' budgets and all tasks' costs are equal to 1, this problem reduces to the maximum [[assignment problem]]. When the costs and profits of all agents-tasktasks assignmentdo arenot equalvary between different agents, this problem reduces to the multiple knapsack problem. If there is a single agent, then, this problem reduces to the [[Knapsackknapsack problem]].

==Explanation of definition==

There are a number of agents and a number of tasks. Any agent can be assigned to perform any task, incurring some cost and profit that may vary depending on the agent-task assignment. Moreover, each agent has a budget and the sum of the costs of task assigned to it cannot exceed this budget. It is required to find an assignment in which all agents do not exceed their budget and total profit of the assignment is maximized.

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 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 weightstotal sumweight 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]]:

==Special cases==

In the special case in which all the agents' budgets and all tasks' costs are equal to 1, this problem reduces to the maximum assignment problem. When the costs and profits of all agents-task assignment are equal, this problem reduces to the multiple knapsack problem. If there is a single agent, then, this problem reduces to the [[Knapsack problem]].

: <math>

==Definition==

\begin{align}

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 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 weights sum 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.

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

:\text{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} \leqle 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 ==

Mathematically the generalized assignment problem can be formulated as:

The generalized assignment problem is [[NP-hard]].<ref>{{citation

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

| last1 = Özbakir | first1 = Lale

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

| last2 = Baykasoğlu | first2 = Adil

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

| last3 = Tapkan | first3 = Pınar

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

| pages = 3782–3795

| publisher = Springer VerlagElsevier

| series = Applied Mathematics and Computation

| title = Bees algorithm for generalized assignment problem

| doi = 10.1016/j.amc.2009.11.018

| volume = 215

| issue = 11

| year = 2010}}.</ref> However, there are linear-programming relaxations which give a <math>(1 - 1/e)</math>-approximation.<ref>{{cite conference |last1=Fleischer |first1=Lisa |last2=Goemans |first2=Michel X. |last3=Mirrokni |first3=Vahab S. |last4=Sviridenko |first4=Maxim |date=2006 |title=Tight approximation algorithms for maximum general assignment problems |conference=Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 |pages=611–620}}</ref>

==Greedy approximation algorithm==

The generalized assignment problem is NP-hard, and it is even APX-hard to approximation. Recently it was shown that it is (<math>e/(e-1) - \epsilon</math>) hard to approximate for every <math>\epsilon</math>.

For the problem variant in which not every item must be assigned to a bin, there is a family of algorithms for solving the GAP by using a combinatorial translation of any algorithm for the knapsack problem into an approximation algorithm for the GAP.<ref>{{cite journal |doi=10.1016/j.ipl.2006.06.003|title=An efficient approximation for the Generalized Assignment Problem|journal=Information Processing Letters|volume=100|issue=4|pages=162–166|year=2006|last1=Cohen|first1=Reuven|last2=Katzir|first2=Liran|last3=Raz|first3=Danny|citeseerx=10.1.1.159.1947}}</ref>

Using any algorithm ALG <math> \alpha</math>-approximation algorithm ALG for the [[knapsack problem]], it is possible to construct a (<math> \alpha + 1</math>)-approximation for the generalized assignment problem in a greedy manner using a residual profit concept.

==Greedy approximation algorithm==

Using any algorithm ALG <math> \alpha</math>-approximation algorithm for the knapsack problem, it is possible to construct a (<math> \alpha+1</math>)-approximation for the generalized assignment problem in a greedy manner using a residual profit concept.

The algorithm constructs a schedule in iterations, where during iteration <math>j</math> a tentative selection of items to bin <math>b_j</math> is selected.

The selection for bin <math>b_j</math> might change as items might be reselected in a later iteration for other bins.

The residual profit of an item <math>x_i</math> for bin <math>b_j</math> is <math>p_{ij}</math> isif <math>x_i</math> is not selected for any other bin or <math> p_{ij}</math> – <math>p_{ik} </math> if <math>x_i</math> is selected for bin <math>b_k</math>.

Formally: We use a vector <math>T</math> to indicate the tentative schedule during the algorithm. Specifically, <math>T[i]=j</math> means the item <math>x_i</math> is scheduled on bin <math>b_j</math> and <math>T[i]=-1</math> means that item <math>x_i</math> is not scheduled. The residual profit in iteration <math>j</math> is denoted by <math>P_j</math>, where <math>P_j[i]=p_{ij}</math> if item <math>x_i</math> is not scheduled (i.e. <math>T[i]=-1</math>) and <math>P_j[i]=p_{ij}-p_{ik}</math> if item <math>x_i</math> is scheduled on bin <math>b_k</math> (i.e. <math>T[i]=k</math>).

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

==See References also==

* [[Assignment problem]]

* [http://www.cs.technion.ac.il/~lirank/pubs/2006-IPL-Generalized-Assignment-Problem.pdf'''An Efficient Approximation for the Generalized Assignment Problem'''], Cohen, Katzir, and Raz, 2006.

==References==

* [http://www-math.mit.edu/~goemans/ga-soda06.pdf '''Tight Approximation Algorithms for Maximum General Assignment Problems'''],

{{reflist}}

Fleischer, Goemans, Mirrokni, and Sviridenko, 2006.

==Further reading==

* {{cite book

* {{cite book |isbn=978-3-540-24777-7|title=Knapsack Problems|last1=Kellerer|first1=Hans|last2=Pferschy|first2=Ulrich|last3=Pisinger|first3=David|date=2013-03-19|publisher=Springer }}

| authorlink = Hans | Kellerer

| first = Hans | Kellerer

| coauthors = U. Pferschy D. Pisinger

| year = 2005

| title = Knapsack Problems

| publisher = Springer Verlag

| id = ISBN 3-540-40286-1

}}

==See also==

*[[Assignment problem]]

[[Category:NP-complete problems]]

[[Category:ProblemsCombinatorial optimization]]

[[Category:operations research]]