generalized assignment problem greedy

Stack Exchange Network

Stack Exchange network consists of 183 Q&A communities including Stack Overflow , the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Q&A for work

Connect and share knowledge within a single location that is structured and easy to search.

Is there a greedy algorithm to solve the assignment problem?

The assignment problem is defined as:

There are n people who need to be assigned to n jobs, one person per job. The cost that would accrue if the ith person is assigned to the jth job is a known quantity C[i,j] for each pair i, j = 1, 2, ..., n. The problem is to find an assignment with the minimum total cost.

There is a question asking to design a greedy algorithm to solve the problem. It also asks if the greedy algorithm always yields an optimal solution and for the performance class of the algorithm. Here is my attempt at designing an algorithm:

Am I correct in saying that my algorithm is of O(n^2)? Am I also correct in saying that a greedy algorithm does not always yield an optimal solution? I used my algorithm on the following cost matrix and it is clearly not the optimal solution. Did I Do something wrong?

• greedy-algorithms
• assignment-problem

• $\begingroup$ Algorithms for maximum weight bipartite maximum matching are unfortunately more complicated than that. They don't really follow the greedy paradigm. $\endgroup$ –  Yuval Filmus Commented Apr 7, 2017 at 6:05

The answer of your post question (already given in Yuval comment) is that there is no greedy techniques providing you the optimal answer to an assignment problem.

The commonly used solution is the Hungarian algorithm, see

Harold W. Kuhn, "The Hungarian Method for the assignment problem", Naval Research Logistics Quarterly, 2: 83–97, 1955

for the original paper.

Otherwise your solution seems correct to me, and as usually with greedy algorithms, it will provide you a feasible solution which you may hope to not be "too far" from the global optimal solution.

Your Answer

Sign up or log in, post as a guest.

Required, but never shown

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy .

Not the answer you're looking for? Browse other questions tagged algorithms greedy-algorithms assignment-problem or ask your own question .

• Featured on Meta
• Bringing clarity to status tag usage on meta sites
• Announcing a change to the data-dump process

Hot Network Questions

• How do I learn more about rocketry?
• Etymology of 制度
• Where is this railroad track as seen in Rocky II during the training montage?
• Is it a good idea to perform I2C Communication in the ISR?
• Is "She played good" a grammatically correct sentence?
• What is the importance of bilinear functions?
• In which town of Europe (Germany ?) were this 2 photos taken during WWII?
• Why do Quantum Kernel Methods work when a large Hilbert space tends to make all samples orthogonal to each other?
• Does the average income in the US drop by $9,500 if you exclude the ten richest Americans?
• Perfectly normal but not collectionwise normal space in ZFC
• Are others allowed to use my copyrighted figures in theses, without asking?
• How can I measure the speed of sound with an oscilloscope and ultrasonic sensor? (Currently getting low value.)
• Sharing team members performance with peers
• Nausea during high altitude cycling climbs
• How do you tip cash when you don't have proper denomination or no cash at all?
• Sylvester primes
• Determine the rank of a matrix expression
• Solve cannot find solutions if integer parameters are assumed
• What would be a good weapon to use with size changing spell
• When has the SR-71 been used for civilian purposes?
• Inductive and projective limit of circles
• I'm a little embarrassed by the research of one of my recommenders
• How to Interpret Statistically Non-Significant Estimates and Rule Out Large Effects?
• Did the Turkish defense industry ever receive any significant foreign investment from any other OECD country?

Stack Exchange Network

Stack Exchange network consists of 183 Q&A communities including Stack Overflow , the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Q&A for work

Connect and share knowledge within a single location that is structured and easy to search.

How to solve large scale generalized assignment problem

I am looking for a way to solve a large scale Generalized assignment problem (To be precise, it is a relaxation of the Generalized assignment problem, because the second constraint has $\le$ instead of $=$ ). Here, $m$ is the number of agents and $n$ is the number of tasks. $$ \begin{aligned} &\text{maximize} && \sum_{i}^{m} \sum_{j}^{n} p_{ij}x_{ij} \\\ &\text{subject to} && \sum_{j}^{n} w_{ij}x_{ij} \le t_{i} &&& \forall i \\\ & && \sum_{i}^{m} x_{ij} \le 1 &&& \forall j \\\ & && x_{ij} \in \{0, 1\} \end{aligned} $$

• $m \le 1,000$
• $n \le 10,000,000$
• $p_{ij} \le 1,000$
• $w_{ij} \le 1,000$
• $t_i \le 200,000$
• valid agent-task pair(i.e. number of non zero $p_{ij}$ ) $\le 200,000,000$
• time limit : 6 hours

Generalized assignment problem is NP-hard, so I'm not trying to find an exact solution. Are there any approximation algorithm or heuristic to solve this problem?

Also, are there any other approaches to solving large scale NP-hard problems? For example, I was wondering if it is possible to reduce the number of variables by clustering agents or tasks, but I did not find such a method.

• assignment-problem

• $\begingroup$ All else failing, there is the greedy heuristic: sort the $p_{ij}$ in descending order, then make assignments in that order, tracking the remaining capacity of each agent and skipping assignments that would exceed that capacity. I did not put this in as an answer because it is such a low hanging fruit. $\endgroup$ –  prubin ♦ Commented Jul 29, 2021 at 18:13
• $\begingroup$ The problem that you wrote is not exactly the Generalized Assignment Problem, because the second set of constraints has $\le$ instead of $=$. This makes the problem much easier since finding a feasible solution is not an issue anymore in this case. Is it what you meant to write? $\endgroup$ –  fontanf Commented Jul 29, 2021 at 20:22
• $\begingroup$ @prubin Thank you. If there is no other way, I will use greedy algorithm. $\endgroup$ –  user5966 Commented Jul 30, 2021 at 6:02
• $\begingroup$ @fontanf Yes, I'm trying to solve the relaxation of the Generalized assignment problem. I've added this to the post $\endgroup$ –  user5966 Commented Jul 30, 2021 at 6:11

2 Answers 2

The instances you plan to solve are orders of magnitude larger than the ones from the datasets used in the scientific literature on the Generalized Assignment Problem. The largest instances of the literature have $m = 80$ and $n = 1600$ . Most algorithms designed for these instances won't be suitable for you.

What seems the most relevant in your case are the polynomial algorithms described in "Knapsack problems: algorithms and computer implementations" (Martello et Toth, 1990):

• Greedy: sort all agent-task pairs according to a given criterion, and then assign greedily from best to worst the unassigned tasks. Complexity: $O(n m \log (n m))$
• Regret greedy: for all tasks, sort its assignments according to a given criterion. At each step, assign the task with the greatest difference between its best assignment and its second-best assignment, and update the structures. Complexity: $O(n m \log m + n^2)$

Various sorting criteria have been proposed: pij , pij/wij , -wij , -wij/ti ... -wij and -wij/ti are more suited for the case where all items have to be assigned. In your case pij and pij/wij might yield good results

Then, they propose to try to shift each task once to improve the solution. With at most one shift per task, the algorithms remain polynomial, but you can try more shifts if you have more time.

Note that these algorithms might be optimized if not all pairs are possible, as you indicate in your case.

I have some implementations here for the standard GAP (and a min objective). You can try to play with them to get an overview of what might work or not in your case

You could try using the greedy heuristic to get an initial solution and then try out one of the many neighborhood-search type metaheuristics. I mentioned sorting on $p_{ij}$ in a comment, but it might (or might not) be better to sort on $p_{ij}/w_{ij}$ (or, time permitting, try both and pick the better solution). For improving on the starting solution, GRASP and simulated annealing would be possibilities. Tabu search is popular with some people, but the memory requirements of maintaining a table of tabu solutions might be prohibitive. I'm fond of genetic algorithms, but I think we can rule out a GA (or other "evolutionary" metaheuristic) based on memory considerations. Personally, I'd be tempted to check out GRASP first.

Your Answer

Sign up or log in, post as a guest.

Required, but never shown

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy .

Not the answer you're looking for? Browse other questions tagged heuristics assignment-problem or ask your own question .

• Featured on Meta
• Bringing clarity to status tag usage on meta sites
• Announcing a change to the data-dump process

Hot Network Questions

• How can I determine, for an arbitrary polyglossia language, whether it is RTL or LTR?
• How is carousing different from drunkenness in Luke 21:34-36? How should they be interpreted literally and spiritually?
• Can Christian Saudi Nationals visit Mecca?
• Why is LiCl a hypovalent covalent molecule?
• Is "She played good" a grammatically correct sentence?
• How to Interpret Statistically Non-Significant Estimates and Rule Out Large Effects?
• Did Babylon 4 actually do anything in the first shadow war?
• Best approach to make lasagna fill pan
• Gravitational potential energy of a water column
• In which town of Europe (Germany ?) were this 2 photos taken during WWII?
• Did the Turkish defense industry ever receive any significant foreign investment from any other OECD country?
• Is it possible to recover from a graveyard spiral?
• Why do Quantum Kernel Methods work when a large Hilbert space tends to make all samples orthogonal to each other?
• When can the cat and mouse meet?
• How to change time on ubuntu 22.04?
• Is the 2024 Ukrainian invasion of the Kursk region the first time since WW2 Russia was invaded?
• Can a quadrilateral polygon have 3 obtuse angles?
• What does "Two rolls" quote really mean?
• Solve cannot find solutions if integer parameters are assumed
• What does 'ex' mean in this context
• What will be impact areas if we don't set targethostname in Sitecore SXA cms in Sitedefinition?
• A seven letter *
• Star Trek: The Next Generation episode that talks about life and death
• What`s this? (Found among circulating tumor cells)

Solving Generalized Assignment Problem using Branch-And-Price

Oct 27, 2021

Table of Contents

Generalized assignment problem, dantzig-wolfe decomposition, column generation, standalone model, initial solution, branching rule, branch-and-price.

One of the best known and widely researched problems in combinatorial optimization is Knapsack Problem:

• given a set of items, each with its weight and value,
• select a set of items maximizing total value
• that can fit into a knapsack while respecting its weight limit.

The most common variant of a problem, called 0-1 Knapsack Problem can be formulated as follows:

• \(m\) - number of items;
• \(x_i\) - binary variable indicating whether item is selected;
• \(v_i\) - value of each items;
• \(w_i\) - weight of each items;
• \(W\) - maximum weight capacity.

As often happens in mathematics, or science in general, an obvious question to ask is how the problem can be generalized. One of generalization is Generalized Assignment Problem. It answers question - how to find a maximum profit assignment of \(m\) tasks to \(n\) machines such that each task (\(i=0, \ldots, m\)) is assigned to exactly one machine (\(j=1, \ldots, n\)), and one machine can have multiple tasks assigned to subject to its capacity limitation. Its standard formulation is presented below:

• \(n\) - number of machines;
• \(m\) - number of tasks;
• \(x_{ij}\) - binary variable indicating whether task \(i\) is assigned to machine \(j\);
• \(v_{ij}\) - value/profit of assigning task \(i\) to machine \(j\);
• \(w_{ij}\) - weight of assigning task \(i\) to machine \(j\);
• \(c_j\) - capacity of machine \(j\).

Branch-and-price

Branch-and-price is generalization of branch-and-bound method to solve integer programs (IPs),mixed integer programs (MIPs) or binary problems. Both branch-and-price, branch-and-bound, and also branch-and-cut, solve LP relaxation of a given IP. The goal of branch-and-price is to tighten LP relaxation by generating a subset of profitable columns associated with variables to join the current basis.

Branch-and-price builds at the top of branch-and-bound framework. It applies column generation priori to branching. Assuming maximization problem, branching occurs when:

• Column Generation is finished (i.e. no profitable columns can be found).
• Objective value of the current solution is greater than best lower bound.
• The current solution does not satisfy integrality constraints.

However, if only first two conditions are met but not the third one, meaning the current solution satisfies integrality constraints, then the best solution and lower bound are updated (lower bound is tightened) with respectively the current solution and its objective value.

The crucial element needed to apply branch-and-price successfully is to find branching scheme. It is tailored to specific problem to make sure that it does not destroy problem structure and can be used in pricing subproblem to effectively generate columns that enter Restricted Master Problem (RMP) while respecting branching rules .

Below is flow diagram describing branch-and-price method:

The successful application B&P depends on tight/strong model formulation. Model formulation is considered tight if solution of its LP relaxation satisfies (frequently) integrality constraints. One of structured approaches to come up with such a formulation is to use Dantzig-Wolfe Decomposition technique. We will see example of it applied to Generalized Assignment Problem (GAP).

A standard formulation was described above. Now, let’s try to reformulate problem. Let

be a set containing all feasible solutions to Knapsack problem for \(j\)-th machine. Clearly, \(S_j\) contains finite number of points, so \(S_j = \{ \mathbf{z}_j^1, \ldots, \mathbf{z}_j^{K_j} \}\), where \(\mathbf{z}_j^k \in \{0, 1\}^{m}\). You can think about \(\mathbf{z}_j^k \in \{0, 1\}^{m}\) as 0-1 encoding of tasks that form \(k\)-th feasible solution for machine \(j\). Now, let \(S = \{ \mathbf{z}_1^1, \ldots, \mathbf{z}_1^{K_1}, \ldots, \mathbf{z}_n^1, \ldots, \mathbf{z}_n^{K_n} \}\) be a set of all feasible solution to GAP. It, potentially, contains a very large number of elements. Then, every point \(x_{ij}\) can be expressed by the following convex combination:

where \(z_{ij}^k \in \{0, 1\}\), and \(z_{ij}^k = 1\) iff task \(i\) is assigned to machine \(j\) in \(k\)-th feasible solution for the machine.

Now, let’s use this representation to reformulate GAP:

Note that we do not need capacity restrictions as they are embedded into definition of feasible solution for machine \(j\).

Now that we have formulation that is suitable for column generation, let’s turn our attention to it.

Column generation is another crucial component of branch-and-price. There are many great resources devoted to column generation so I will mention only core points:

• Column generation is useful when a problem’s pool of feasible solutions contains many elements but only small subset will be present in the optimal solution.
• There exists subproblem (called often pricing problem) that can be used to effectively generate columns that should enter RMP.
• Column generation starts with initial feasible solution.
• Pricing subproblem objective function is updated with dual of the current solution.
• Columns with positive reduced cost, in case of maximization problem, enter problem.
• Procedure continues until such columns exist.

Below is flow diagram describing column generation method:

Implementation

Let’s see how one can approach implementation of B&P to solve Generalized Assignment Problem. Below is discussion about main concepts and few code excerpts, a repository containing all code can be found on github .

An example of problem instance taken from [1] is:

It is always good idea to have a reference simple(r) implementation that can be used to validate our results using more sophisticated methods. In our case it is based on standard problem formulation. Implementation can be found in repo by checking classes GAPStandaloneModelBuilder and GAPStandaloneModel . Formulation for a problem instance presented above looks as follows:

Now let’s try to examine building blocks of B&P to discus main part at the end, once all the puzzles are there.

To start column generation process, we need to have an initial solution. One possible way to derive it is to use two-phase Simplex method. In first step, you add slack variables to each constraint and set objective function as their sum. Then you minimize the problem. If your solution has objective value \(0\), then first of all you have initial solution and you know that your problem is feasible. In case you end up with positive value for any of slack variables, you can conclude that the problem is infeasible. You can stop here.

I took a different approach and came up with simple heuristic that generate initial solution. I have not analyzed it thoroughly so I am not sure if it is guaranteed to always return feasible solution if one exists. Its idea is quite simple:

• Construct bipartite graph defined as \(G=(V, A)\), where \(V = T \cup M\) – \(T\) is set of tasks and obviously \(M\) is set of machines. There exists arc \(a = (t, m)\) if \(w_{tm} \le rc_{m}\), where \(rc_{m}\) is remaining capacity for machine \(m\). Initially remaining capacity is equal to capacity of machine and with each iteration, and assignment of task to machine it is being update. If \(\vert A \vert = 0\), then stop.
• Solve a minimum weight matching problem.
• Update assignments – say that according to solution task \(t_0\) should be assigned to machine \(m_0\), then \(\overline{rc}_{m_0} = rc_{m_0} - w_{t_0 m_0}\).
• Find a machine where task is contributing with the lowest weight – say machine \(m_0 = \arg\min \{ m: w_{t_0 m} \}\).
• Free up remaining capacity so there is enough space for \(t_0\) on machine \(m_0\). Any tasks that were de-assigned in a process are added to pool of unassigned tasks.
• Repeat until there are no unassigned tasks.

See details on github .

As we said before the most important piece needed to implement B&P is branching rules which does not destroy structure of subproblem. Let’s consider non-integral solution to RMP. Given convexity constraint it means that there exists machine \(j_0\) and at least two, and for sake of example say exactly two, \(0 < \lambda_{j_0} ^{k_1} < 1\) and \(0 < \lambda_{j_0} ^{k_2} < 1\) such that \(\lambda_{j_0} ^{k_1} + \lambda_{j_0} ^{k_2} = 1\). Since with each of \(\lambda\)s is connected different assignment (set of tasks), then it leads us to a conclusion that there exists task \(i_0\) such that \(x_{i_0 j_0} < 1\) expressed in variables from the original formulation. Now, let’s use this information to formulate branching rule:

• left child node: a task \(i_0\) must be assigned to a machine \(j_0\).
• right child node: a task \(i_0\) cannot be assigned to a machine \(j_0\).

We can say that branching is based on \(x_{ij}\) from standard formulation. And it can be represented by:

Note that we can use the branching rule to easily to filter out initial columns for each node that do not satisfy those conditions:

• \(j = j_0\) and task \(i_0 \in T_{j_0}\), or
• \(j \neq j_0\) and task \(i_0 \notin T_{j}\).
• \(j = j_0\) and task \(i_0 \in T_{j_0}\).

See on github .

Based on the same principle, subproblem’s pool of feasible solution are created - i.e. on left child node:

• knapsack subproblem for machine \(j_0\) – variable representing task \(i_0\) is forced to be \(1\).
• knapsack subproblem for machine \(j \neq j_0\) – variable representing task \(i_0\) is forced to be \(0\).

Similarly for right childe node. See on github .

Below is an outline of main loop of column generation. It is an implementation of flow diagram from above so I will not spend too much time describing it. The only part maybe worth commenting is stop_due_to_no_progress - it evaluates whether column generation did not make any progress in last \(k\)-iterations and it should be stop.

Now, let’s see how constructing subproblems, solving them and then adding back column(s) to RMP looks like. We have as many subproblems as machines. Once a solution is available, we check whether it has positive reduced cost. A solution to knapsack problem corresponds to column in RMP. So if the column with positive reduced cost was identified and added, then new iteration of column generation will be executed. Gurobi allows to query information about all other identified solutions, so we can utilize this feature and add all columns that have the same objective value as optimal solution, potentially adding more than one column and hoping it will positively impact solution time.

Note that each subproblem is independent so in principle they could be solved in parallel. However due to Python Global Interpreter Lock (GIL) that prevent CPU-bounded threads to run in parallel, they are solved sequentially. Additionally depending on your Gurobi license, you might not be allowed to solve all those models in parallel even if Python would allow it.

Below you can find example of one of the RMPs:

and subproblem with dual information passed:

Now that we have all building blocks prepared, then let’s turn our attention back to B&P.

In the blog post, Branch-and-Price technique for solving MIP was explained. An example of applying B&P for Generalized Assignment Problem was presented. The solution approach used Python as programming language and Gurobi as solver.

[1] Der-San Chen, Robert G. Batson, Yu Dang (2010), Applied Integer Programming - Modeling and Solution, Willey. [2] Lasdon, Leon S. (2002), Optimization Theory for Large Systems, Mineola, New York: Dover Publications. [3] Cynthia Barnhart, Ellis L. Johnson, George L. Nemhauser, Martin W. P. Savelsbergh, Pamela H. Vance, (1998) Branch-and-Price: Column Generation for Solving Huge Integer Programs. Operations Research 46(3):316-329.

A Class of Greedy Algorithms for the Generalized Assignment Problem

• University of Florida
• Erasmus University Rotterdam

Research output : Contribution to journal › Journal article › Research › peer-review

Access to Document

• 10.1016/S0166-218X(99)00224-3 Licence: Unspecified
• Persistent link

T1 - A Class of Greedy Algorithms for the Generalized Assignment Problem

AU - Romeijn, H. Edwin

AU - Romero Morales, Dolores

N2 - The Generalized Assignment Problem (GAP) is the problem of finding the minimal cost assignment of jobs to machines such that each job is assigned to exactly one machine, subject to capacity restrictions on the machines. We propose a class of greedy algorithms for the GAP. A family of weight functions is defined to measure a pseudo-cost of assigning a job to a machine. This weight function in turn is used to measure the desirability of assigning each job to each of the machines. The greedy algorithm then schedules jobs according to a decreasing order of desirability. A relationship with the partial solution given by the LP-relaxation of the GAP is found, and we derive conditions under which the algorithm is asymptotically optimal in a probabilistic sense.

AB - The Generalized Assignment Problem (GAP) is the problem of finding the minimal cost assignment of jobs to machines such that each job is assigned to exactly one machine, subject to capacity restrictions on the machines. We propose a class of greedy algorithms for the GAP. A family of weight functions is defined to measure a pseudo-cost of assigning a job to a machine. This weight function in turn is used to measure the desirability of assigning each job to each of the machines. The greedy algorithm then schedules jobs according to a decreasing order of desirability. A relationship with the partial solution given by the LP-relaxation of the GAP is found, and we derive conditions under which the algorithm is asymptotically optimal in a probabilistic sense.

KW - Generalized Assignment Problem

KW - Greedy heuristic

KW - Asymptotic feasibility

KW - Asymptotic optimality

U2 - 10.1016/S0166-218X(99)00224-3

DO - 10.1016/S0166-218X(99)00224-3

M3 - Journal article

SN - 0166-218X

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

Navigation Menu

Search code, repositories, users, issues, pull requests..., provide feedback.

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly.

To see all available qualifiers, see our documentation .

• Notifications You must be signed in to change notification settings

A solver for the generalized assignment problem

fontanf/generalizedassignmentsolver

Folders and files.

Repository files navigation

Generalizedassignmentsolver.

A solver for the generalized assignment problem.

This problem is interesting because many different optimization methods can and have been applied to solve it (Branch-and-cut, Branch-and-price, Branch-and-relax, Local search, Constraint programming, Column generation heuristics...). Thus, the main goal of this repository is for me to have reference implementations for classical algorithms and optimization solvers.

The variant handled here is the variant:

• with a minimization objective (items have costs)
• where all items have to be assigned

It is possible to solve the variant with a maximization objective (items have profits) by setting the cost of assigning item an j to agent an i to maximum profit of item j - profit of assigning item j to agent i .

It is possible to solve the variant where not all items have to be assigned by adding an additional dummy agent i such that the weight of assigning an item j to this agent i is equal to 0 and the cost of assigning an item j to this agent i is equal to maximum profit of item j

Implemented algorithms

Lower bounds.

Linear relaxation

• solved with CLP -a linrelax-clp
• solved with Gurobi -a "milp-gurobi --only-linear-relaxation"
• solved with Cplex -a "milp-cplex --only-linear-relaxation"

Lagrangian relaxation of knapsack constraints. The value of this relaxation is the same as the value of the linear relaxation. However, it might be cheaper to compute, especially on large instances.

• solved with volume method -a lagrelax-knapsack-volume
• solved with L-BFGS method -a lagrelax-knapsack-lbfgs

Lagrangian relaxation of assignment constraints

• solved with volume method -a lagrelax-assignment-volume
• solved with L-BFGS method -a lagrelax-assignment-lbfgs

Column generation -a "column-generation --linear-programming-solver clp" -a "column-generation --linear-programming-solver cplex"

Upper bounds

Polynomial algorithms from "Generalized Assignment Problems" (Martello et al., 1992), options --desirability cij --desirability wij --desirability cij*wij --desirability -pij/wij --desirability wij/ti :

• Basic greedy -a "greedy --desirability wij"
• Greedy with regret measure -a "greedy-regret --desirability wij"
• MTHG, basic greedy (+ n shifts) -a "mthg --desirability wij"
• MTHG, greedy with regret measure (+ n shifts) -a "mthg-regret --desirability wij"

Local search algorithm implemented with fontanf/localsearchsolver -a "local-search --threads 3"

Tree search algorithms based on the Dantzig-Wolfe reformulation branching scheme (i.e. column generation heuristics) implemented with fontanf/columngenerationsolver :

• Greedy -a "column-generation-heuristic-greedy --linear-programming-solver cplex"
• Limited discrepency search -a "column-generation-heuristic-limited-discrepancy-search --linear-programming-solver cplex"

Others heuristics:

• Random feasible solution found with a Local search -a random
• Local search with LocalSolver -a localsolver

Exact algorithms

Mixed-Integer Linear Programs

• with CBC -a milp-cbc
• with CPLEX -a milp-cplex
• with Gurobi -a milp-gurobi
• with Knitro -a milp-knitro

Constraint programming

• with Gecode -a constraint-programming-gecode
• with CPLEX -a constraint-programming-cplex

Usage (command line)

• Python 1.8%
• Starlark 1.5%

Breadcrumbs Section. Click here to navigate to respective pages.

Generalized Assignment Problem

DOI link for Generalized Assignment Problem

Click here to navigate to parent product.

This chapter reviews heuristic and metaheuristic algorithms for generalized assignment problem and explores the problem formally and introduces some related problems and their complexities. It explains basic strategies of greedy method and local search and describes Lagrangian relaxation problems. The chapter provides some basic ideas of Lagrangian heuristics and also describes the basics of branch-and-bound. It analyses some computational results of various metaheuristic algorithms and branch-and-bound methods. The chapter focuses on polynomial-time approximation algorithms with performance guarantees. There are several useful tools used to design approximation algorithms. Metaheuristic algorithms are widely recognized as one of the most practical approaches for hard combinatorial optimization problems. Algorithm path relinking with ejection chains applies ejection chains probes to solutions generated by path relinking, which is a methodology to generate solutions from two or more solutions.

• Privacy Policy
• Terms & Conditions
• Cookie Policy
• Taylor & Francis Online
• Taylor & Francis Group
• Students/Researchers
• Librarians/Institutions

Connect with us

Registered in England & Wales No. 3099067 5 Howick Place | London | SW1P 1WG © 2024 Informa UK Limited

Stack Exchange Network

Stack Exchange network consists of 183 Q&A communities including Stack Overflow , the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Q&A for work

Connect and share knowledge within a single location that is structured and easy to search.

Can we find a generic tight example for the greedy algorithm of the unweighted generalized assignment problem?

In the unweighted generalized assignment problem (UGAP) we have $n$ items and $k$ knapsacks. For each item $i$ and knapsack $j$, there is a weight $w_{ij}$. Also, every knapsack has a capacity $W$. The question of UGAP is to pack the items into the knapsacks such that the weights of the items in any knapsack do not exceed $W$ and the number of all items packed is maximum.

UGAP is NP-hard . The greedy algorithm ALG that maximizes the number of items packed in each knapsack is $1-(1-1/k)^k$-approximation. I am trying to find a tight example for ALG that achieves this bound of $1-(1-1/k)^k$. I can find an example with fixed $n$ and $k$, e.g., $n=4$ and $k=2$ but I would like a generic example of arbitrary $n$ and $k$ such that ALG attains the bound of $1-(1-1/k)^k$.

This paper gives a tight example for the maximum coverage problem, which I think (if I am not mistaken) can be used to construct a tight example for the weighted generalized assignment problem. What about the UGAP?

• approximation-algorithms

• $\begingroup$ Would you mind clarifying the difference between the weighted and unweighted problem? $\endgroup$ –  Yonatan N Commented Apr 8, 2018 at 20:26
• $\begingroup$ In the unweighted problem, we maximize the number of items packed into the knapsacks subject to the capacity of each knapsack, whereas in the weighted problem, we maximize the weights of items packed into the knapsacks subject to the capacity of each knapsack. $\endgroup$ –  Jika Commented Apr 8, 2018 at 21:02

Know someone who can answer? Share a link to this question via email , Twitter , or Facebook .

Your answer, sign up or log in, post as a guest.

Required, but never shown

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy .

Browse other questions tagged approximation-algorithms packing or ask your own question .

• Featured on Meta
• Bringing clarity to status tag usage on meta sites
• Announcing a change to the data-dump process

Hot Network Questions

• How to Interpret Statistically Non-Significant Estimates and Rule Out Large Effects?
• Pull up resistor question
• What's "the archetypal book" called?
• Is a stable quantifier-free language really possible?
• What does 'ex' mean in this context
• Are all citizens of Saudi Arabia "considered Muslims by the state"?
• Fusion September 2024: Where are we with respect to "engineering break even"?
• Sharing team members performance with peers
• How to change time on ubuntu 22.04?
• Can Christian Saudi Nationals visit Mecca?
• In what chapter does Fleur suspect Hagrid?
• Why would autopilot be prohibited below 1000 AGL?
• how did the Apollo 11 know its precise gyroscopic position?
• What`s this? (Found among circulating tumor cells)
• Did the Turkish defense industry ever receive any significant foreign investment from any other OECD country?
• A seven letter *
• Why do Quantum Kernel Methods work when a large Hilbert space tends to make all samples orthogonal to each other?
• Text wrapping in longtable not working
• What will be impact areas if we don't set targethostname in Sitecore SXA cms in Sitedefinition?
• Why is LiCl a hypovalent covalent molecule?
• Why are poverty definitions not based off a person's access to necessities rather than a fixed number?
• Transform a list of rules into a list of function definitions
• When can the cat and mouse meet?
• Sylvester primes

The Generalized Assignment Problem and Extensions

Cite this chapter.

• Dolores Romero Morales 3 &
• H. Edwin Romeijn 4  

1937 Accesses

7 Citations

10 Concluding Remarks

In this chapter we have described the state of the art in solving the Generalized Assignment Problem, as well as many extensions thereof. The approach we have taken is to generalize the GAP to a much larger class of Convex Assignment Problems, show that many of the extensions of the GAP proposed in the literature are members of this class, and describe many of the proposed solution approaches to the GAP in terms of the larger class of problems. Throughout the chapter we have paid particular attention to the Generalized Assignment Problem, the Multi-Resource Generalized Assignment Problem, and the Multi-Period Single-Sourcing Problem.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save.

• Get 10 units per month
• Download Article/Chapter or eBook
• 1 Unit = 1 Article or 1 Chapter
• Cancel anytime
• Available as PDF
• Read on any device
• Instant download
• Own it forever
• Compact, lightweight edition
• Dispatched in 3 to 5 business days
• Free shipping worldwide - see info
• Durable hardcover edition

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Unable to display preview.  Download preview PDF.

Similar content being viewed by others

Some results on an assignment problem variant

The assignment problem revisited

Integer Programming

M.M. Amini and M. Racer. A rigorous computational comparison of alternative solution methods for the generalized assignment problem. Management Science , 40(7):868–890, 1994.

MATH   Google Scholar  

M.M. Amini and M. Racer. A hybrid heuristic for the generalized assignment problem. European Journal of Operational Research , 87:343–348, 1995.

Article   MATH   Google Scholar  

V. Balachandran. An integer generalized transportation model for optimal job assignment in computer networks. Operations Research , 24(4):742–759, 1976.

MATH   MathSciNet   Google Scholar  

E. Balas and E. Zemel. Facets of the knapsack polytope from minimal covers. SIAM Journal of Applied Mathematics , 34:119–148, 1978.

Article   MATH   MathSciNet   Google Scholar  

P. Barcia. The bound improving sequence algorithm. Operations Research Letters , 4(1):27–30, 1985.

P. Barcia and K. Jörnsten. Improved Lagrangean decomposition: An application to the generalized assignment problem. European Journal of Operational Research , 46:84–92, 1990.

C. Barnhart, E.L. Johnson, G.L. Nemhauser, M.W.P. Savelsbergh, and P.H. Vance. Branch-and-price: column generation for solving huge integer programs. Operations Research , 46(3):316–329, 1998.

J. Beardwood, J.H. Halton, and J.M. Hammersley. The shortest path through many points. Proceedings of the Cambridge Philosophical Society , 55:299–327, 1959.

J.F. Benders and J.A.E.E. van Nunen. A property of assignment type mixed integer linear programming problems. Operations Research Letters , 2(2): 47–52, 1983.

R.J.M. Blocq. Het multi-resource generalised assignment problem toegepast op de toeleveringsstrategie van een oliemaatschappij. Master’s thesis, Vrije Universiteit Amsterdam, 1999.

Google Scholar  

R.J.M. Blocq, D. Romero Morales, H.E. Romeijn, and G.T. Timmer. The multi-resource generalized assignment problem with an application to the distribution of gasoline products. Working Paper, Department of Decision and Information Sciences, Rotterdam School of Management, The Netherlands, 2000.

J. Bramel and D. Simchi-Levi. The Logic of Logistics — theory, algorithms, and applications for logistics management . Springer-Verlag, New York, 1997.

J.F. Campbell and A. Langevin. The snow disposal assignment problem. Journal of the Operational Research Society , 46:919–929, 1995.

D. Cattrysse, Z. Degraeve, and J. Tistaert. Solving the generalised assignment problem using polyhedral results. European Journal of Operational Research , 108:618–628, 1998.

D.G. Cattrysse. Set Partitioning Approaches to Combinatorial Optimization Problems . PhD thesis, Katholieke Universiteit Leuven, 1990.

D.G. Cattrysse, M. Salomon, and L.N. Van Wassenhove. A set partitioning heuristic for the generalized assignment problem. European Journal of Operational Research , 72:167–174, 1994.

D.G. Cattrysse and L.N. Van Wassenhove. A survey of algorithms for the generalized assignment problem. European Journal of Operational Research , 60:260–272, 1992.

L. Chalmet and L. Gelders. Lagrangean relaxation for a generalized assignment-type problem. In M. Roubens, editor, Advances in OR , pages 103–109. EURO, North-Holland, Amsterdam, 1976.

P.C. Chu and J.E. Beasley. A genetic algorithm for the generalised assignment problem. Computers and Operations Research , 24(1):17–23, 1997.

A. De Maio and C. Roveda. An all zero-one algorithm for a certain class of transportation problems. Operations Research , 19(6):1406–1418, 1971.

M. Dyer and A. Frieze. Probabilistic analysis of the generalised assignment problem. Mathematical Programming , 55:169–181, 1992.

T.A. Feo and M.G.C. Resende. Greedy randomized adaptive search procedures. Journal of Global Optimization , 6:109–133, 1995.

J.A. Ferland, A. Hertz, and A. Lavoie. An object-oriented methodology for solving assignment-type problems with neighborhood search techniques. Operations Research , 44(2):347–359, 1996.

M.L. Fisher. The lagrangian relaxation method for solving integer programming problems. Management Science , 27:1–18, 1981.

M.L. Fisher and R. Jaikumar. A generalized assignment heuristic for vehicle routing. Networks , 11:109–124, 1981.

MathSciNet   Google Scholar  

M.L. Fisher, R. Jaikumar, and L.N. Van Wassenhove. A multiplier adjustment method for the generalized assignment problem. Management Science , 32(9):1095–1103, 1986.

R. Freling, H.E. Romeijn, D. Romero Morales, and A.P.M. Wagelmans. A branch and price algorithm for the multi-period single-sourcing problem. Operations Research , 51(6):922–939, 2003.

Article   MathSciNet   Google Scholar  

R.S. Garfinkel and G.L. Nemhauser. Set partitioning problem: set covering with equality constraints. Operations Research , 17:848–856, 1969.

B. Gavish and H. Pirkul. Algorithms for the multi-resource generalized assignment problem. Management Science , 37(6):695–713, 1991.

A.M. Geoffrion. Lagrangean relaxation for integer programming. Mathematical Programming Studies , 2:82–114, 1974.

A.M. Geoffrion and G.W. Graves. Multicommodity distribution system design by Benders decomposition. Management Science , 20(5):822–844, 1974.

F. Glover. Surrogate constraints. Operations Research , 16(4):741–749, 1968.

F. Glover, J. Hultz, and D. Klingman. Improved computer-based planning techniques, part II. Interfaces , 9(4):12–20, 1979.

E.S. Gottlieb and M.R. Rao. (1 , k )- configuration facets for the generalized assignment problem. Mathematical Programming , 46:53–60, 1990.

E.S. Gottlieb and M.R. Rao. The generalized assignment problem: Valid inequalities and facets. Mathematical Programming , 46:31–52, 1990.

M. Guignard and S. Kim. Lagrangean decomposition: a model yielding stronger lagrangean bounds. Mathematical Programming , 39:215–228, 1987.

M. Guignard and M.B. Rosenwein. An improved dual based algorithm for the generalized assignment problem. Operations Research , 37(4):658–663, 1989.

N.G. Hall and M.E. Posner. Generating experimental data for scheduling problems. Operations Research , 49(6):854–865, 2001.

Å Hallefjord, K.O. Jörnsten, and P. Värbrand. Solving large scale generalized assignment problems-An aggregation/disaggregation approach. European Journal of Operational Research , 64:103–114, 1993.

M. Held, P. Wolfe, and H.P. Crowder. Validation of subgradient optimization. Mathematical Programming , 6:62–88, 1974.

K. Jörnsten and M. Näsberg. A new lagrangian relaxation approach to the generalized assignment problem. European Journal of Operational Research , 27:313–323, 1986.

K.O. Jörnsten and P. Värbrand. A hybrid algorithm for the generalized assignment problem. Optimization , 22(2):273–282, 1991.

N. Karabakal, J.C. Bean, and J.R. Lohmann. A steepest descent multiplier adjustment method for the generalized assignment problem. Technical Report 92-11, Department of Industrial and Operations Engineering, The University of Michigan, 1992.

T.D. Klastorin. On the maximal covering location problem and the generalized assignment problem. Management Science , 25(1):107–113, 1979.

K. Kogan, A. Shtub, and V.E. Levit. DGAP-the dynamic generalized assignment problem. Annals of Operations Research , 69:227–239, 1997.

H. Kuhn. A heuristic algorithm for the loading problem in flexible manufacturing systems. International Journal of Flexible Manufacturing Systems , 7:229–254, 1995.

Article   Google Scholar  

M. Laguna, J.P. Kelly, J.L. González-Velarde, and F. Glover. Tabu search for the multilevel generalized assignment problem. European Journal of Operational Research , 82:176–189, 1995.

L.A.N. Lorena and M.G. Narciso. Relaxation heuristics for a generalized assignment problem. European Journal of Operational Research , 91:600–610, 1996.

S. Martello and P. Toth. An algorithm for the generalized assignment problem. In J.P. Brans, editor, Operational Research’ 81 , pages 589–603. IFORS, North-Holland, Amsterdam, 1981.

S. Martello and P. Toth. Knapsack problems, algorithms and computer implementations . John Wiley & Sons, New York, 1990.

S. Martello and P. Toth. The bottleneck generalized assignment problem. European Journal of Operational Research , 83(3):621–638, 1995.

J.B. Mazzola. Generalized assignment with nonlinear capacity interaction. Management Science , 35(8):923–941, 1989.

J.B. Mazzola and A.W. Neebe. Bottleneck generalized assignment problems. Engineering Costs and Production Economics , 14:61–65, 1988.

M.G. Narciso and L.A.N. Lorena. Lagrangean/surrogate relaxation for generalized assignment problems. European Journal of Operational Research , 114:165–177, 1999.

A.W. Neebe and M.R. Rao. An algorithm for the fixed-charge assigning users to sources problem. Journal of the Operational Research Society , 34(11):1107–1113, 1983.

I.H. Osman. Heuristics for the generalised assignment problem: simulated annealing and tabu search approaches. OR Spektrum , 17:211–225, 1995.

J.S. Park, B.H. Lim, and Y. Lee. A lagrangian dual-based branch-and-bound algorithm for the generalized multi-assignment problem. Management Science , 44(12, part 2 of 2):S271–S282, 1998.

M. Racer and M.M. Amini. A robust heuristic for the generalized assignment problem. Annals of Operations Research , 50:487–503, 1994.

H. Ramalhinho Lourenço and D. Serra. Adaptive search heuristics for the generalized assignment problem. Mathware and Soft Computing , 9(2–3):209–234, 2002.

H.E. Romeijn and N. Piersma. A probabilistic feasibility and value analysis of the generalized assignment problem. Journal of Combinatorial Optimization , 4(3):325–355, 2000.

H.E. Romeijn and D. Romero Morales. A class of greedy algorithms for the generalized assignment problem. Discrete Applied Mathematics , 103:209–235, 2000.

H.E. Romeijn and D. Romero Morales. Generating experimental data for the generalized assignment problem. Operations Research , 49(6):866–878, 2001.

H.E. Romeijn and D. Romero Morales. A probabilistic analysis of the multi-period single-sourcing problem. Discrete Applied Mathematics , 112:301–328, 2001.

H.E. Romeijn and D. Romero Morales. An asymptotically optimal greedy heuristic for the multi-period single-sourcing problem: the cyclic case. Naval Research Logistics , 50(5):412–437, 2003.

H.E. Romeijn and D. Romero Morales. Asymptotic analysis of a greedy heuristic for the multi-period single-sourcing problem: the acyclic case. Journal of Heuristics , 10:5–35, 2004.

D. Romero Morales. Optimization Problems in Supply Chain Management . PhD thesis, TRAIL Thesis Series nr. 2000/4 & ERIM PhD series Research in Management nr. 3, The Netherlands, 2000.

G.T. Ross and R.M. Soland. A branch and bound algorithm for the generalized assignment problem. Mathematical Programming , 8:91–103, 1975.

G.T. Ross and R.M. Soland. Modeling facility location problems as generalized assignment problems. Management Science , 24(3):345–357, 1977.

M.W.P. Savelsbergh. A branch-and-price algorithm for the generalized assignment problem. Operations Research , 45(6):831–841, 1997.

D.B. Shmoys and É. Tardos. An approximation algorithm for the generalized assignment problem. Mathematical Programming , 62:461–474, 1993.

A. Shtub and K. Kogan. Capacity planning by a dynamic multi-resource generalized assignment problem (DMRGAP). European Journal of Operational Research , 105:91–99, 1998.

V. Srinivasan and G.L. Thompson. An algorithm for assigning uses to sources in a special class of transportation problems. Operations Research , 21:284–295, 1972.

T. Stützle and H. Hoos. The max-min ant system and local search for combinatorial optimization problems: Towards adaptive tools for combinatorial global optimization. In S. Voss, S. Martello, I.H. Osman, and C. Roucairol, editors, Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization , pages 313–329. Kluwer Academic Publishers, 1998.

M.A. Trick. A linear relaxation heuristic for the generalized assignment problem. Naval Research Logistics , 39:137–151, 1992.

J.M. Wilson. A genetic algorithm for the generalised assignment problem. Journal of the Operational Research Society , 48:804–809, 1997.

J.M. Wilson. A simple dual algorithm for the generalised assignment problem. Journal of Heuristics , 2:303–311, 1997.

M. Yagiura, T. Ibaraki, and F. Glover. An ejection chain approach for the generalized assignment problem. Technical Report 99013, Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto Univeristy, 1999.

M. Yagiura, T. Yamaguchi, and T. Ibaraki. A variable depth search algorithm for the generalized assignment problem. In S. Voss, S. Martello, I.H. Osman, and C. Roucairol, editors, Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization , pages 459–471. Kluwer Academic Publishers, 1998.

V.A. Zimokha and M.I. Rubinshtein. R & D planning and the generalized assignment problem. Automation and Remote Control , 49:484–492, 1988.

Download references

Author information

Authors and affiliations.

Saïd Business School, University of Oxford, Oxford, 0X1 1HP, UK

Dolores Romero Morales

Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL, 32611

H. Edwin Romeijn

You can also search for this author in PubMed   Google Scholar

Editor information

Editors and affiliations.

University of Minnesota, Minneapolis, MN

Ding-Zhu Du

University of Florida, Gainesville, FL

Panos M. Pardalos

Rights and permissions

Reprints and permissions

Copyright information

© 2004 Kluwer Academic Publishers

About this chapter

Morales, D.R., Romeijn, H.E. (2004). The Generalized Assignment Problem and Extensions. In: Du, DZ., Pardalos, P.M. (eds) Handbook of Combinatorial Optimization. Springer, Boston, MA. https://doi.org/10.1007/0-387-23830-1_6

Download citation

DOI : https://doi.org/10.1007/0-387-23830-1_6

Publisher Name : Springer, Boston, MA

Print ISBN : 978-0-387-23829-6

Online ISBN : 978-0-387-23830-2

eBook Packages : Mathematics and Statistics Mathematics and Statistics (R0)

Share this chapter

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

• Publish with us

Policies and ethics

• Find a journal
• Track your research

Generalized assignment problem

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.

In special cases

Explanation of definition, greedy approximation algorithm, further reading.

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

Mathematically the generalized assignment problem can be formulated as an integer program :

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]

• Assignment problem

Related Research Articles

The knapsack problem is the following problem in combinatorial optimization:

The travelling salesman problem , also known as the travelling salesperson 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-complete. Moreover, some restricted variants of it are NP-complete too, for example:

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, splitting a network prefix into multiple subnets, and technology mapping in FPGA semiconductor chip design.

Multidimensional scaling ( MDS ) is a means of visualizing the level of similarity of individual cases of a data set. MDS is used to translate distances between each pair of objects in a set into a configuration of points mapped into an abstract Cartesian space.

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 which 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  ×  n matrix with

The study of facility location problems (FLP) , also known as location analysis , is a branch of operations research and computational geometry concerned with the optimal placement of facilities to minimize transportation costs while considering factors like avoiding placing hazardous materials near housing, and competitors' facilities. The techniques also apply to cluster analysis.

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 that, informally, describes the relationship between a set of inputs and an output, where adding more of one input has a decreasing additional benefit. The 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 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.

Quantum optimization algorithms are quantum algorithms that are used to solve optimization problems. Mathematical optimization deals with finding the best solution to a problem from a set of possible solutions. Mostly, the optimization problem is formulated as a minimization problem, where one tries to minimize an error which depends on the solution: the optimal solution has the minimal error. Different optimization techniques are applied in various fields such as mechanics, economics and engineering, and as the complexity and amount of data involved rise, more efficient ways of solving optimization problems are needed. Quantum computing may allow problems which are not practically feasible on classical computers to be solved, or suggest a considerable speed up with respect to the best known classical algorithm.

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 linear programming technique used for solving combinatorial optimization problems. It was introduced in the context of the cutting stock problem. Later, it has been applied to the bin packing and job scheduling problems. 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.

• ↑ Fleischer, Lisa; Goemans, Michel X.; Mirrokni, Vahab S.; Sviridenko, Maxim (2006). Tight approximation algorithms for maximum general assignment problems . Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06. pp.   611–620.
• ↑ Cohen, Reuven; Katzir, Liran; Raz, Danny (2006). "An efficient approximation for the Generalized Assignment Problem". Information Processing Letters . 100 (4): 162–166. CiteSeerX   10.1.1.159.1947 . doi : 10.1016/j.ipl.2006.06.003 .

Kellerer, Hans; Pferschy, Ulrich; Pisinger, David (2013-03-19). Knapsack Problems . Springer. ISBN   978-3-540-24777-7 .