Solving set partitioning problems using lagrangian relaxation

M.G.C. van Krieken

Research output: ThesisDoctoral Thesis

1833 Downloads (Pure)

Abstract

This thesis focuses on the set partitioning problem. Given a collection of subsets of a certain root set and costs associated to these subsets, the set partitioning problem is the problem of finding a minimum cost partition of the root set. Many real-life problems, such as vehicle routing and crew scheduling problems, can be formulated as set partitioning problems. The LaRSS solver is developed for solving set partitioning problems fast without using external linear programming solvers. The methods used include Lagrangian relaxation, preprocessing techniques and branch and bound. This thesis describes many research results coming from the development of LaRSS. Moreover, the performance of LaRSS is discussed and compared with the well-known optimization package CPLEX. Finally, two cases in the field of vehicle routing are described to illustrate the use of LaRSS in real-life situations.
Original languageEnglish
QualificationDoctor of Philosophy
Awarding Institution
  • Tilburg University
Supervisors/Advisors
  • Peeters, Rene, Co-promotor
  • Fleuren, Hein, Promotor
Award date15 Mar 2006
Place of PublicationTilburg
Publisher
Print ISBNs9056681613
Publication statusPublished - 2006

Fingerprint

Dive into the research topics of 'Solving set partitioning problems using lagrangian relaxation'. Together they form a unique fingerprint.

Cite this