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))
1422 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
The generalized assignment problem is a classical combinatorial optimization problem that models a variety of real world applications including flexible manufacturing systems [6], facility location [11] and vehicle routing problems [2].
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:
In this paper, we propose an ejection chain approach under the framework of tabu search (TS) for the generalized assignment problem (GAP), which is known to be NP-hard [32]. GAP seeks a minimum cost assignment of n jobs to m agents subject to. resource constraint for each agent.
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.
Key words: Approximation algorithms, generalized assignment problem, scheduling unrelated parallel machines. 1. Introduction The generalized assignment problem can be viewed as the following problem of scheduling parallel machines with costs. Each of n independent jobs is to be processed by exactly one
In this work, we consider the well-studied Generalized Assignment Problem and investigate the performance of several metaheuristic methods. To obtain insights on strengths and weaknesses of these solution approaches, we perform Instance Space Analysis on the existing instance types and propose a set of features describing the hardness of an ...
The Generalized Assignment Problem (GAP) consists in finding a maximum-profit assignment of tasks to agents with capacity constraints. In this paper, a path relinking heuristic is proposed for the GAP.
The generalized assignment problem (GAP) is the problem of determining an assignment of J jobs to M capacity constrained machines, such that each job is assigned to exactly one machine, while total costs are minimized.
The generalized assignment problem (GAP) and its special cases multiple knapsack1 and bin packing 2 capture several fundamental optimization problems and have many practical applications in computer science, operations research, and related disciplines.
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.