The Generalized Assignment Problem

  • First Online: 10 February 2021

Cite this chapter

generalized assignment problem (gap)

  • 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

  1. The unsolved special case of the generalized assignment problem

    generalized assignment problem (gap)

  2. GitHub

    generalized assignment problem (gap)

  3. PPT

    generalized assignment problem (gap)

  4. Solved Consider an instance of the Generalised Assignment

    generalized assignment problem (gap)

  5. Well-known problems: linear assignment problem (LAP), quadratic

    generalized assignment problem (gap)

  6. The story of distributed constraint optimization in LA: Relaxed

    generalized assignment problem (gap)

VIDEO

  1. Assignment 3 Generalized Anxiety

  2. Ignou Result June 2024 New Update Publish

  3. BAKING-PROBLEM GAP ANALYSIS

  4. communication 101 THE GENDER PAY GAP assignment

  5. ASSIGNMENT PROBLEM: meaning, formulation, Hungarian method

  6. MMPC-007 MBA Solved Assignment 2024-2025

COMMENTS

  1. Generalized assignment problem - Wikipedia

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

  2. The Generalized Assignment Problem and Its Generalizations

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

  3. Generalized Assignment Problem | SpringerLink

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

  4. 13.1 Generalized Assignment Problem (GAP) - University of Alberta

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

  5. Chapter 1 The Generalized Assignment Problem - Springer

    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

  6. An efficient approximation for the Generalized Assignment Problem

    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

  7. The Generalized Assignment Problem | SpringerLink

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

  8. GENERALIZED ASSIGNMENT PROBLEM - INSEAD

    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

  9. The Elastic Generalized Assignment Problem - JSTOR

    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

  10. 13.1 Generalized Assignment Problem(GAP) - University of Alberta

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