Digitala Vetenskapliga Arkivet

Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • 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
Column Generation in the Primal-Dual Linear Programming Algorithm
Linköping University, Department of Mathematics, Applied Mathematics. Linköping University, Faculty of Science & Engineering.
2025 (English)Independent thesis Advanced level (degree of Master (Two Years)), 28 HE creditsStudent thesis
Abstract [en]

We combine the primal-dual linear programming algorithm with Dinkelbach's Newton-type fractional programming method to solve large scale linear programming problems normally solved by column generation. We test this primal-dual column generation method on one-dimensional bin packing problems and on vehicle routing problems with time windows. The primal-dual column generation algorithm solved the vehicle routing problems faster than classical column generation. However, classical column generation outperformed the primal-dual algorithm on the bin packing problems.

Abstract [sv]

Vi kombinerar den primal-duala linjärprogrammeringsalgoritmen med Dinkelbachs Newton-metod för fraktionell programmering för att lösa storskaliga linjära program som normalt löses med kolumngenerering. Vi utvärderar denna primal-duala kolumngenereringsmetod på endimensionella packingssproblem samt på ruttplaneringsproblem med tidsfönster. Den primal-duala kolumngeneringsmetoden löste ruttplaneringsproblemen snabbare än klassisk kolumngenerering. Däremot presterade klassisk kolumngenerering bättre än primal-dual kolumngenerering på packingsproblemen.

Place, publisher, year, edition, pages
2025. , p. 54
Keywords [en]
linear programming, column generation, primal-dual algorithm, fractional programming
Keywords [sv]
linjärprogrammering, kolumngenering, primal-duala algoritmen, fractionell programmering
National Category
Computational Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-216247ISRN: LiTH-MAT-EX--2025/13--SEOAI: oai:DiVA.org:liu-216247DiVA, id: diva2:1987847
Subject / course
Optimization
Presentation
2025-06-09, Hopningspunkten, B-huset, Campus Valla, Linköpings Universitet, Linköping, 11:00 (English)
Supervisors
Examiners
Available from: 2025-08-15 Created: 2025-08-08 Last updated: 2025-08-15Bibliographically approved

Open Access in DiVA

fulltext(4164 kB)331 downloads
File information
File name FULLTEXT01.pdfFile size 4164 kBChecksum SHA-512
26e32fd07fb9c63afa8ec1754b1124900cc767ab9e26cbd430212086060c679689d2426a29dcb3781d683d99f5e7d2931b8e7a84ea590efafedbcb5f2bb6a5c9
Type fulltextMimetype application/pdf

By organisation
Applied MathematicsFaculty of Science & Engineering
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 332 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: 545 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • 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