The Generalized Assignment Problem
- First Online: 10 February 2021
Cite this chapter
- Vittorio Maniezzo 6 ,
- Marco Antonio Boschetti 6 &
- Thomas Stützle 7
Part of the book series: EURO Advanced Tutorials on Operational Research ((EUROATOR))
1409 Accesses
5 Citations
The generalized assignment problem (GAP) asks to assign n clients to m servers in such a way that the assignment cost is minimized, provided that all clients are assigned to a server and that the capacity of each server is not exceeded. It is a problem that appears, by itself or as a subproblem, in a very high number of practical applications and has therefore been intensively studied. We use this problem as a test case example of all algorithms presented in the text. This section reviews the state of the art of research on GAP and shows the application of several mathematical programming techniques on GAP instances.
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 EPUB and 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
Vectors and matrices are denoted by small bold letters throughout the text, and these definitions depart from the standard for compliance with much of the literature on the GAP. Furthermore, as stated in Sect. 1.1 , remind that all variables in this chapter are indexed from 1, but in the computational traces they will appear as indexed from 0.
In this, and in all algorithms in the text, the input of all GAP instance data is implicit.
Avella P, Boccia M, Vasilyev I (2010) A computational study of exact knapsack separation for the generalized assignment problem. Comput Optim Appl 45(3):543–555
Article Google Scholar
Beasley JE (1993) Lagrangian relaxation. In: Reeves CR (ed) Modern heuristic techniques for combinatorial problems. Wiley, New York, pp 243–303
Google Scholar
Benders JF (1962) Partitioning procedures for solving mixed-variables programming problems. Numer Math 4:280–322
Benders JF, van Nunen JA (1983) A property of assignment type mixed linear programming problems. Oper Res Lett 32:47–52
Boschetti M, Maniezzo V (2009) Benders decomposition, Lagrangean relaxation and metaheuristic design. J Heurist 15:283–312
Bressoud TC, Rastogi R, Smith MA (2003) Optimal configuration for BGP route selection. In: IEEE INFOCOM 2003, twenty-second annual joint conference of the IEEE computer and communications societies, San Francisco, CA, vol 2, pp 916–926
Campbell GM (1999) Cross-utilization of workers whose capabilities differ. Manage Sci 45(5):722–732
Cattrysse DG, Van Wassenhove LN (1992) A survey of algorithms for the generalized assignment problem. Eur J Oper Res 60(3):260–272
Cattrysse DG, Degraeve Z, Tistaert J (1998) Solving the generalised assignment problem using polyhedral results. Eur J Oper Res 108(3):618–628
Chalmet LG, Gelders LF (1976) Lagrangian relaxations for a generalized assignment-type problem. In: Proceedings of the second european congress operations research. North-Holland, Amsterdam, pp 103–109
Chu PC, Beasley JE (1997) A genetic algorithm for the generalised assignment problem. Comput Oper Res 24(1):17–23
Cordeau JF, Gaudioso M, Laporte G, Moccia L (2006) A memetic heuristic for the generalized quadratic assignment problem. INFORMS J Comput 18(4):433–443
Dantzig GB, Wolfe P (1960) Decomposition principle for linear programs. Oper Res 8:101–111
De Farias IR, Johnson EL Jr, Nemhauser GL (2000) A generalized assignment problem with special ordered sets: a polyhedral approach. Math Program Ser A 89:187–203
Dobson G, Nambimadom RS (2001) The batch loading and scheduling problem. Oper Res 49(1):52–65
Drexl A (1991) Scheduling of project networks by job assignment. Manage Sci 37(12):1590–1602
Fisher ML, Jaikumar R (1981) A generalized assignment heuristic for vehicle routing. Networks 11:109–124
Fisher ML, Jaikumar R, Van Wassenhove LN (1986) A multiplier adjustment method for the generalized assignment problem. Manage Sci 32(9):1095–1103
Foulds L, Wilson J (1997) A variation of the generalized assignment problem arising in the New Zealand dairy industry. Ann Oper Research 69:105–114
Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman & Co, New York, NY
Gavish B, Pirkul H (1985) Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality. Math Program 33(1):31–78
Geoffrion AM (1974) Lagrangean relaxation for integer programming. Math Program Stud 2:82–114
Glover F (1965) A multiphase-dual algorithm for the zero-one integer programming problem. Oper Res 13:879–919
Glover F (1968) Surrogate constraints. Oper Res 16:741–749
Glover F (1975) Surrogate constraint duality in mathematical programming. Oper Res 23:434–451
Glover F, Hultz H, Klingman D (1979) Improved computer based planning techniques, part 2. Interfaces 9(4):12–20
Gottlieb ES, Rao MR (1990) Generalized assignment problem. Valid inequalities and facets. Math Program Ser A 46(1):31–52
Greenberg HJ, Pierskalla WP (1970) Surrogate mathematical programming. Oper Res 18:924–939
Guignard M, Kim S (1987) Lagrangean decomposition: a model yielding stronger Lagrangean bounds. Math Program 39:215–228
Harvey NJA, Ladner RE, Lovász L, Tamir T (2006) Semi-matchings for bipartite graphs and load balancing. J Algorith 59(1):53–78
Higgins AJ (1999) Optimizing cane supply decisions within a sugar mill region. J Sched 2:229–244
Jeet V, Kutanoglu E (2007) Lagrangean relaxation guided problem space search heuristic for generalized assignment problems. Eur J Oper Res 182(3):1039–1056
Jörnsten K, Nasberg M (1986) A new Lagrangian relaxation approach to the generalized assignment problem. Eur J Oper Res 27:313–323
Lee CG, Ma Z (2004) The generalized quadratic assignment problem. Tech. Rep. 5, Department of Mechanical and Industrial Engineering, University of Toronto, Toronto
Maniezzo V (2019) Bridging the GAP. Some generalized assignment problem instances. http://astarte.csr.unibo.it/gapdata/gapinstances.html
Martello S, Toth P (1981) An algorithm for the generalized assignment problem. In: Brans J (ed) Operations research ’81. North-Holland, Amsterdam, pp 589–603
Martello S, Toth P (1990) Knapsack problems: algorithms and computer implementations. Wiley, New York, NY
Mazzola JB, Neebe AW (1993) An algorithm for the bottleneck generalized assignment problem. Comput Oper Res 20(4):355–362
Mazzola JB, Neebe AW, Dunn CVR (1989) Production planning of a flexible manufacturing system in a requirements planning environment. Int J Flex Manuf Syst 1:115–142
Mitrović-Minić S, Punnen AP (2008) Very large-scale variable neighborhood search for the generalized assignment problem. J Interdiscipl Math 11(5):653–670
Morales DR, Romeijn HE (2004) The generalized assignment problem and extensions. In: Du D, Pardalos PM (eds) Handbook of combinatorial optimization. Springer, Boston, pp 259–311
Narciso MG, Lorena L (2007) Lagrangean/surrogate relaxation for generalized assignment problems. Eur J Oper Res 182:1039–1056
Nauss RM (2003) Solving the generalized assignment problem: an optimizing and heuristic approach. INFORMS J Comput 15(3):249–266
Nauss RM (2004) The elastic generalized assignment problem. J Oper Res Soc 55:1333–1341
Öncan T (2007) A survey of the generalized assignment problem and its applications. Inf Syst Oper Res 45(3):123–141
Pigatti A, Poggi de Aragao M, Uchoa E (2005) Stabilized branch-and-cut-and-price for the generalized assignment problem. Electron Notes Discr Math 19:389–395
Pirkul H, Gavish B (1986) Computer and database location in distributed computer systems. IEEE Trans Comput 35:583–590
Posta M, Ferland JA, Michelon P (2012) An exact method with variable fixing for solving the generalized assignment problem. Comput Optim Appl 52(3):629–644
Ross GT, Soland RM (1975) A branch and bound algorithm for the generalized assignment problem. Math Program 8(1):91–103
Ruland KS (1999) A model for aeromedical routing and scheduling. Int Trans Oper Res 6:57–73
Sahni S, Gonzalez T (1976) P-complete approximation problems. J ACM 23(3):555–565
Savelsbergh MWP (1997) A branch-and-price algorithm for the generalized assignment problem. Oper Res 45:831–841
Wilson JM (1997) A genetic algorithm for the generalised assignment problem. J Oper Res Soc 48:804–809
Zhang CW, Ong HL (2007) An efficient solution to biobjective generalized assignment problem. Adv Eng Softw 38:50–58
Download references
Author information
Authors and affiliations.
University of Bologna, Cesena, Italy
Vittorio Maniezzo & Marco Antonio Boschetti
Université Libre de Bruxelles, Brussels, Belgium
Thomas Stützle
You can also search for this author in PubMed Google Scholar
Rights and permissions
Reprints and permissions
Copyright information
© 2021 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this chapter
Maniezzo, V., Boschetti, M.A., Stützle, T. (2021). The Generalized Assignment Problem. In: Matheuristics. EURO Advanced Tutorials on Operational Research. Springer, Cham. https://doi.org/10.1007/978-3-030-70277-9_1
Download citation
DOI : https://doi.org/10.1007/978-3-030-70277-9_1
Published : 10 February 2021
Publisher Name : Springer, Cham
Print ISBN : 978-3-030-70276-2
Online ISBN : 978-3-030-70277-9
eBook Packages : Business and Management Business and Management (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
IMAGES
VIDEO
COMMENTS
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 ...
An assignment is a mapping σ: J → I, where σ(j) = i means that job j is assigned to agent i. Then the generalized assignment problem (GAP) is formulated as follows: minimize cost(σ) = ∑ j∈J cσ(j),j subject to ∑ j∈J σ(j)=i aij ≤ bi, ∀i ∈ I. (1) The GAP is known to be NP-hard, since the partition problem of a given set of ...
The generalized assignment problem (GAP) seeks the minimum cost assignment of n tasks to m agents such that each task is assigned to precisely one agent subject to capacity restrictions on the agents. The formulation of the problem is: where \ ( c_ {ij} \) is the cost of assigning task j to agent i, \ ( a_ {ij} \) is the capacity used when task ...
cost of processing these jobs. The following is a natural LP relaxation for this problem known as Generalized Assignment Problem (GAP): min P i;j c Pijx ij P i x ij = 1 1 j n j p ijx ij T 1 i m x ij 0 Note that even to detect if there is a feasible schedule (respecting the deadline bound T) is NP-hard. Therefore, we cannot have an approximation ...
The Generalized Assignment Problem 1.1 Introduction The generalized assignment problem (GAP) asks to assign n clients to m servers in such a way that the assignment cost is minimized, provided that all clients are assigned to a server and that thecapacityof each server is not exceeded. A mathematical model can be obtainedby defining:1
the knapsack problem, then Algorithm 1 is a (1 + α)-approximation for GAP. Proof. For the following proof we use the notation p(S)to indicate the profit gained by assignment S.The proof is by induction on the number of bins available when the algorithm is invoked. When there is a single bin, the assignment returned by the algorithm, S¯ M,is
The generalized assignment problem (GAP) asks to assign n clients to m servers in such a way that the assignment cost is minimized, provided that all clients are assigned to a server and that the capacity of each server is not exceeded. It is a problem that appears, by itself or as a subproblem, in a very high number of practical applications ...
of relatively hard test problems the heuristic is able to find solutions that are on average within 0.13% from optimality. Keywords: generalized assignment problem, set partitioning, column generation, dual as-cent. 1 Introduction The generalized assignment problem (GAP) is the problem of determining an assignment of J
The generalized assignment problem (GAP) has been studied by numerous researchers over the past 30 years or so. Simply stated, one must find a minimum-cost assignment of tasks to agents such that each task is assigned to exactly one agent and such that each agent's resource capacity is honoured. The problem is known to be NP-hard. In this paper, we
Tand we minimize the cost of processing these jobs. The following is a natural LP relaxation for this problem known as Generalized Assignment Problem (GAP): min P i;j c Pij x ij P i x ij = 1 1 j n j p ij x ij T 1 i m x ij 0 Clearly the problem is NP-hard since even the feasibility (whether there is a solution satisfying all the constraints is ...