Generalized assignment problem

Last updated June 17, 2023

In applied mathematics, the maximum generalized 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.

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 tasks 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 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 assignment problem. When the costs and profits of all tasks do not vary between different agents, this problem reduces to the multiple knapsack problem. If there is a single agent, then, this problem reduces to the knapsack problem.

Explanation of definition

In the following, we have n kinds of items, $a_{1}$ through $a_{n}$ and m kinds of bins $b_{1}$ through $b_{m}$ . Each bin $b_{i}$ is associated with a budget $t_{i}$ . For a bin $b_{i}$ , each item $a_{j}$ has a profit $p_{ij}$ and a weight $w_{ij}$ . A solution is an assignment from items to bins. A feasible solution is a solution in which for each bin $b_{i}$ the total weight of assigned items is at most $t_{i}$ . 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 program:

{\begin{aligned}{\text{maximize }}&\sum _{i=1}^{m}\sum _{j=1}^{n}p_{ij}x_{ij}.\\{\text{subject to }}&\sum _{j=1}^{n}w_{ij}x_{ij}\leq t_{i}&&i=1,\ldots ,m;\\&\sum _{i=1}^{m}x_{ij}\leq 1&&j=1,\ldots ,n;\\&x_{ij}\in \{0,1\}&&i=1,\ldots ,m,\quad j=1,\ldots ,n;\end{aligned}}

Complexity

The generalized assignment problem is NP-hard,^[1] However, there are linear-programming relaxations which give a $(1-1/e)$ -approximation.^[2]

Greedy approximation algorithm

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.^[3]

Using any $\alpha$ -approximation algorithm ALG for the knapsack problem, it is possible to construct a ( $\alpha +1$ )-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 $j$ a tentative selection of items to bin $b_{j}$ is selected. The selection for bin $b_{j}$ might change as items might be reselected in a later iteration for other bins. The residual profit of an item $x_{i}$ for bin $b_{j}$ is $p_{ij}$ if $x_{i}$ is not selected for any other bin or $p_{ij}$ – $p_{ik}$ if $x_{i}$ is selected for bin $b_{k}$ .

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

Formally:

Set

T[i]=-1{\text{ for }}i=1\ldots n

For

j=1,\ldots ,m

do:

Call ALG to find a solution to bin

b_{j}

using the residual profit function

P_{j}

. Denote the selected items by

S_{j}

.

Update

T

using

S_{j}

, i.e.,

T[i]=j

for all

i\in S_{j}

.

Related Research Articles

The knapsack problem is the following problem in combinatorial optimization:

The travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?" It is an NP-hard problem in combinatorial optimization, important in theoretical computer science and operations research.

The subset sum problem (SSP) is a decision problem in computer science. In its most general formulation, there is a multiset $of integers and a target-sum, and the question is to decide whether any subset of the integers sum to precisely . The problem is known to be NP-hard. Moreover, some restricted variants of it are NP-complete too, for example:$

The method of least squares is a standard approach in regression analysis to approximate the solution of overdetermined systems by minimizing the sum of the squares of the residuals made in the results of each individual equation.

The assignment problem is a fundamental combinatorial optimization problem. In its most general form, the problem is as follows:

The bin packing problem is an optimization problem, in which items of different sizes must be packed into a finite number of bins or containers, each of a fixed given capacity, in a way that minimizes the number of bins used. The problem has many applications, such as filling up containers, loading trucks with weight capacity constraints, creating file backups in media, and technology mapping in FPGA semiconductor chip design.

The Gauss–Newton algorithm is used to solve non-linear least squares problems, which is equivalent to minimizing a sum of squared function values. It is an extension of Newton's method for finding a minimum of a non-linear function. Since a sum of squares must be nonnegative, the algorithm can be viewed as using Newton's method to iteratively approximate zeroes of the components of the sum, and thus minimizing the sum. In this sense, the algorithm is also an effective method for solving overdetermined systems of equations. It has the advantage that second derivatives, which can be challenging to compute, are not required.

A fully polynomial-time approximation scheme (FPTAS) is an algorithm for finding approximate solutions to function problems, especially optimization problems. An FPTAS takes as input an instance of the problem and a parameter ε > 0. It returns as output a value is at least $times the correct value, and at most times the correct value.$

In mathematics, the Grothendieck inequality states that there is a universal constant $with the following property. If M ij is an n \times n matrix with$

In statistics, an additive model (AM) is a nonparametric regression method. It was suggested by Jerome H. Friedman and Werner Stuetzle (1981) and is an essential part of the ACE algorithm. The AM uses a one-dimensional smoother to build a restricted class of nonparametric regression models. Because of this, it is less affected by the curse of dimensionality than e.g. a p-dimensional smoother. Furthermore, the AM is more flexible than a standard linear model, while being more interpretable than a general regression surface at the cost of approximation errors. Problems with AM, like many other machine learning methods, include model selection, overfitting, and multicollinearity.

The maximum coverage problem is a classical question in computer science, computational complexity theory, and operations research. It is a problem that is widely taught in approximation algorithms.

David Bernard Shmoys is a Professor in the School of Operations Research and Information Engineering and the Department of Computer Science at Cornell University. He obtained his Ph.D. from the University of California, Berkeley in 1984. His major focus has been in the design and analysis of algorithms for discrete optimization problems.

The weapon target assignment problem (WTA) is a class of combinatorial optimization problems present in the fields of optimization and operations research. It consists of finding an optimal assignment of a set of weapons of various types to a set of targets in order to maximize the total expected damage done to the opponent.

In mathematics, a submodular set function is a set function whose value, informally, has the property that the difference in the incremental value of the function that a single element makes when added to an input set decreases as the size of the input set increases. Submodular functions have a natural diminishing returns property which makes them suitable for many applications, including approximation algorithms, game theory and electrical networks. Recently, submodular functions have also found immense utility in several real world problems in machine learning and artificial intelligence, including automatic summarization, multi-document summarization, feature selection, active learning, sensor placement, image collection summarization and many other domains.

The quadratic knapsack problem (QKP), first introduced in 19th century, is an extension of knapsack problem that allows for quadratic terms in the objective function: Given a set of items, each with a weight, a value, and an extra profit that can be earned if two items are selected, determine the number of items to include in a collection without exceeding capacity of the knapsack, so as to maximize the overall profit. Usually, quadratic knapsack problems come with a restriction on the number of copies of each kind of item: either 0, or 1. This special type of QKP forms the 0-1 quadratic knapsack problem, which was first discussed by Gallo et al. The 0-1 quadratic knapsack problem is a variation of knapsack problems, combining the features of unbounded knapsack problem, 0-1 knapsack problem and quadratic knapsack problem.

In the bin covering problem, items of different sizes must be packed into a finite number of bins or containers, each of which must contain at least a certain given total size, in a way that maximizes the number of bins used.

The multiple subset sum problem is an optimization problem in computer science and operations research. It is a generalization of the subset sum problem. The input to the problem is a multiset $of n integers and a positive integer m representing the number of subsets. The goal is to construct, from the input integers, some m subsets. The problem has several variants:$

The configuration linear program (configuration-LP) is a particular linear programming used for solving combinatorial optimization problems. It was introduced in the context of the cutting stock problem. Later, it has been applied to bin packing and job scheduling. In the configuration-LP, there is a variable for each possible configuration - each possible multiset of items that can fit in a single bin. Usually, the number of configurations is exponential in the problem size, but in some cases it is possible to attain approximate solutions using only a polynomial number of configurations.

The Karmarkar–Karp (KK) bin packing algorithms are several related approximation algorithm for the bin packing problem. The bin packing problem is a problem of packing items of different sizes into bins of identical capacity, such that the total number of bins is as small as possible. Finding the optimal solution is computationally hard. Karmarkar and Karp devised an algorithm that runs in polynomial time and finds a solution with at most $bins, where OPT is the number of bins in the optimal solution. They also devised several other algorithms with slightly different approximation guarantees and run-time bounds.$

References

↑ Özbakir, Lale; Baykasoğlu, Adil; Tapkan, Pınar (2010), Bees algorithm for generalized assignment problem, Applied Mathematics and Computation, vol. 215, Elsevier, pp. 3782–3795, doi:10.1016/j.amc.2009.11.018 .
↑ Fleischer, Lisa; Goemans, Michel X.; Mirrokni, Vahab S.; Sviridenko, Maxim (2006). "Tight approximation algorithms for maximum general assignment problems".{{cite journal}}: Cite journal requires |journal= (help)
↑ Cohen, Reuven; Katzir, Liran; Raz, Danny (2006). "An efficient approximation for the Generalized Assignment Problem". Information Processing Letters. 100 (4): 162–166. doi:10.1016/j.ipl.2006.06.003.