Column Generation in the Primal-Dual Linear Programming Algorithm
2025 (English)Independent thesis Advanced level (degree of Master (Two Years)), 28 HE credits
Student 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
2025-08-152025-08-082025-08-15Bibliographically approved