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

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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
Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-5583ISRN: LiTH-MAT-EX--05/12--SEOAI: oai:DiVA.org:liu-5583DiVA: diva2:21391
Uppsok
fysik/kemi/matematik
Supervisors
Examiners
Available from: 2006-03-02 Created: 2006-03-02

Open Access in DiVA

fulltext(265 kB)4218 downloads
File information
File name FULLTEXT01.pdfFile size 265 kBChecksum SHA-1
44ca8f5a39bc1ea02c9da4ad3d66265ac8decb30515434ed9c9dedee85166335b8e0fe06
Type fulltextMimetype application/pdf

By organisation
Department of Mathematics
Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 4218 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

urn-nbn

Altmetric score

urn-nbn
Total: 1012 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf