Solving set partitioning problems using lagrangian relaxation

M.G.C. van Krieken

Research output: ThesisDoctoral Thesis

485 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

Set Partitioning
Lagrangian Relaxation
Vehicle Routing
Roots
Crew Scheduling
Subset
Costs
Branch-and-bound
Preprocessing
Scheduling Problem
Linear programming
Partition
Optimization

Cite this

van Krieken, M. G. C. (2006). Solving set partitioning problems using lagrangian relaxation. Tilburg: CentER, Center for Economic Research.
van Krieken, M.G.C.. / Solving set partitioning problems using lagrangian relaxation. Tilburg : CentER, Center for Economic Research, 2006. 185 p.
@phdthesis{1447ef00401948a68b7b906a33201b24,
title = "Solving set partitioning problems using lagrangian relaxation",
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.",
author = "{van Krieken}, M.G.C.",
year = "2006",
language = "English",
isbn = "9056681613",
series = "CentER Dissertation Series",
publisher = "CentER, Center for Economic Research",
school = "Tilburg University",

}

van Krieken, MGC 2006, 'Solving set partitioning problems using lagrangian relaxation', Doctor of Philosophy, Tilburg University, Tilburg.

Solving set partitioning problems using lagrangian relaxation. / van Krieken, M.G.C.

Tilburg : CentER, Center for Economic Research, 2006. 185 p.

Research output: ThesisDoctoral Thesis

TY - THES

T1 - Solving set partitioning problems using lagrangian relaxation

AU - van Krieken, M.G.C.

PY - 2006

Y1 - 2006

N2 - 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.

AB - 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.

M3 - Doctoral Thesis

SN - 9056681613

T3 - CentER Dissertation Series

PB - CentER, Center for Economic Research

CY - Tilburg

ER -

van Krieken MGC. Solving set partitioning problems using lagrangian relaxation. Tilburg: CentER, Center for Economic Research, 2006. 185 p. (CentER Dissertation Series).