liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
Solving the Generalized Assignment Problem by column enumeration based on Lagrangian reduced costs
Linköping University, Department of Mathematics.
2006 (English)Independent thesis Basic level (professional degree), 20 points / 30 hpStudent thesis
Abstract [en]

In this thesis a method for solving the Generalized Assignment Problem (GAP) is described. It is based on a reformulation of the original problem into a Set Partitioning Problem (SPP), in which the columns represent partial solutions to the original problem. For solving this problem, column generation, with systematic overgeneration of columns, is used. Conditions that guarantee that an optimal solution to a restricted SPP is optimal also in the original problem are given. In order to satisfy these conditions, not only columns with the most negative Lagrangian reduced costs need to be generated, but also others; this observation leads to the use of overgeneration of columns.

The Generalized Assignment Problem has shown to be NP-hard and therefore efficient algorithms are needed, especially for large problems. The application of the proposed method decomposes GAP into several knapsack problems via Lagrangian relaxation, and enumerates solutions to each of these problems. The solutions obtained from the knapsack problems form a Set Partitioning Problem, which consists of combining one solution from each knapsack problem to obtain a solution to the original problem. The algorithm has been tested on problems with 10 agents and 60 jobs. This leads to 10 knapsack problems, each with 60 variables.

Place, publisher, year, edition, pages
Matematiska institutionen , 2006. , 29 p.
Keyword [en]
Generalized Assignment Problem, Knapsack Problems, Lagrangian Relaxation, Overgeneration, Enumeration, Set Partitioning Problem.
National Category
URN: urn:nbn:se:liu:diva-5583ISRN: LiTH-MAT-EX--05/12--SEOAI: diva2:21391
Available from: 2006-03-02 Created: 2006-03-02

Open Access in DiVA

fulltext(265 kB)3571 downloads
File information
File name FULLTEXT01.pdfFile size 265 kBChecksum MD5
Type fulltextMimetype application/pdf

By organisation
Department of Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 3571 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 987 hits
ReferencesLink to record
Permanent link

Direct link