Reduced Costs for Vehicle Routing and General Mixed-Integer Programs
Reduced Costs for Vehicle Routing and General Mixed-Integer Programs
View/Type of Scholarly Publication
DissertationDate of Exam
25.04.2025Date of Publication
09.05.2025Advisor
Mutzel, PetraCo-Referee
Stiller, SebastianMetadata
Show full item record
Citable Links 
Abstract
Mixed-integer linear programming is a powerful tool for modeling combinatorial optimization problems in a standardized way. Sophisticated solvers that calculate optimal solutions for these programs consist of dozens of individual interacting parts. Throughout the last 70 years, a lot of scientific and commercial resources have been invested in developing new components and refining old ones. Due to the diversity of applications, many general-purpose techniques exist. Additionally, when employed in practice, these algorithms often have to solve multiple problems with a similar structure. Consequently, problem-specific extensions are of high interest. In this thesis, we investigate both types of modules, general-purpose mixed-integer linear programming techniques and algorithmic refinements for a specific combinatorial optimization problem, namely, the vehicle routing problem (VRP).
In VRPs, the task is to deliver goods to customers using a fleet of vehicles at minimal travel cost. We introduce two new variants: the VRP with heterogeneous time windows and its dynamic and robust extension. These variants are motivated by a logistics problem from practice. In contrast to their homogeneous pendants, heterogeneous VRPs imply an additional level of decision-making: Which customer gets assigned to which vehicle type? We elaborate that this question is fundamental in our (mixed-)integer linear programming approach. We present efficient adaptations of state-of-the-art techniques to enforce the allocations of these vehicle-assignment variables throughout the solution process. In our extensive computational experiments, we evaluate different techniques, such as branching and reduced cost fixing for these variables in our branch-cut-and-price algorithm. Our results underline their importance for the VRP with heterogeneous time windows. In the dynamic extension, we use robust optimization techniques to introduce a novel delay-resistance objective term. To guarantee optimality, we adapt the dominance check of the labeling algorithm. In a computational study, we evaluate the practical impact of this objective term in our model on a set of real-world instances.
Motivated by the significant impact of enforcing routes in VRP solutions, we developed a general-purpose variable fixing technique. It is based on reduced cost fixing, a famous integer linear programming technique that combines important concepts of linear programming with the integrality condition of the variables and a primal bound U on the optimal objective function value. Our novel reduced cost fix and cut method extends this idea by efficiently increasing the amount of accessed local information via rotation of the objective vector. Its iterative version is an exact method for checking whether some variable values can not be attained in a solution with an objective value better than U. Furthermore, we introduce a new class of cuts, the gap-based optimality cuts. They are designed to cut off not only a given fractional optimum of the linear relaxation but also solutions that do not improve upon U. We show that these cuts imply the classic Dantzig cuts and their strengthened version by Charnes and Cooper. We evaluate the performance of our novel techniques on the MIPLIB 2017 Benchmark set to analyze their effectiveness and efficiency on a heterogeneous class of instances. Our implementation in the open-source solver SCIP shows that the new cuts significantly strengthen the dual bound at the root node relaxation. Additionally, both novel techniques can accelerate the solution process of a sophisticated MILP framework.
In VRPs, the task is to deliver goods to customers using a fleet of vehicles at minimal travel cost. We introduce two new variants: the VRP with heterogeneous time windows and its dynamic and robust extension. These variants are motivated by a logistics problem from practice. In contrast to their homogeneous pendants, heterogeneous VRPs imply an additional level of decision-making: Which customer gets assigned to which vehicle type? We elaborate that this question is fundamental in our (mixed-)integer linear programming approach. We present efficient adaptations of state-of-the-art techniques to enforce the allocations of these vehicle-assignment variables throughout the solution process. In our extensive computational experiments, we evaluate different techniques, such as branching and reduced cost fixing for these variables in our branch-cut-and-price algorithm. Our results underline their importance for the VRP with heterogeneous time windows. In the dynamic extension, we use robust optimization techniques to introduce a novel delay-resistance objective term. To guarantee optimality, we adapt the dominance check of the labeling algorithm. In a computational study, we evaluate the practical impact of this objective term in our model on a set of real-world instances.
Motivated by the significant impact of enforcing routes in VRP solutions, we developed a general-purpose variable fixing technique. It is based on reduced cost fixing, a famous integer linear programming technique that combines important concepts of linear programming with the integrality condition of the variables and a primal bound U on the optimal objective function value. Our novel reduced cost fix and cut method extends this idea by efficiently increasing the amount of accessed local information via rotation of the objective vector. Its iterative version is an exact method for checking whether some variable values can not be attained in a solution with an objective value better than U. Furthermore, we introduce a new class of cuts, the gap-based optimality cuts. They are designed to cut off not only a given fractional optimum of the linear relaxation but also solutions that do not improve upon U. We show that these cuts imply the classic Dantzig cuts and their strengthened version by Charnes and Cooper. We evaluate the performance of our novel techniques on the MIPLIB 2017 Benchmark set to analyze their effectiveness and efficiency on a heterogeneous class of instances. Our implementation in the open-source solver SCIP shows that the new cuts significantly strengthen the dual bound at the root node relaxation. Additionally, both novel techniques can accelerate the solution process of a sophisticated MILP framework.
Subjects
Mixed-Integer Programming, Reduced Costs, Vehicle Routing Problem, Algorithm Engineering
Classification (DDC)
004 InformatikSchürmann, Lukas: Reduced Costs for Vehicle Routing and General Mixed-Integer Programs. - Bonn, 2025. - Dissertation, Rheinische Friedrich-Wilhelms-Universität Bonn.
Online-Ausgabe in bonndoc: https://nbn-resolving.org/urn:nbn:de:hbz:5-82587
Online-Ausgabe in bonndoc: https://nbn-resolving.org/urn:nbn:de:hbz:5-82587
@phdthesis{handle:20.500.11811/13066,
urn: https://nbn-resolving.org/urn:nbn:de:hbz:5-82587,
author = {{Lukas Schürmann}},
title = {Reduced Costs for Vehicle Routing and General Mixed-Integer Programs},
school = {Rheinische Friedrich-Wilhelms-Universität Bonn},
year = 2025,
month = may,
note = {Mixed-integer linear programming is a powerful tool for modeling combinatorial optimization problems in a standardized way. Sophisticated solvers that calculate optimal solutions for these programs consist of dozens of individual interacting parts. Throughout the last 70 years, a lot of scientific and commercial resources have been invested in developing new components and refining old ones. Due to the diversity of applications, many general-purpose techniques exist. Additionally, when employed in practice, these algorithms often have to solve multiple problems with a similar structure. Consequently, problem-specific extensions are of high interest. In this thesis, we investigate both types of modules, general-purpose mixed-integer linear programming techniques and algorithmic refinements for a specific combinatorial optimization problem, namely, the vehicle routing problem (VRP).
In VRPs, the task is to deliver goods to customers using a fleet of vehicles at minimal travel cost. We introduce two new variants: the VRP with heterogeneous time windows and its dynamic and robust extension. These variants are motivated by a logistics problem from practice. In contrast to their homogeneous pendants, heterogeneous VRPs imply an additional level of decision-making: Which customer gets assigned to which vehicle type? We elaborate that this question is fundamental in our (mixed-)integer linear programming approach. We present efficient adaptations of state-of-the-art techniques to enforce the allocations of these vehicle-assignment variables throughout the solution process. In our extensive computational experiments, we evaluate different techniques, such as branching and reduced cost fixing for these variables in our branch-cut-and-price algorithm. Our results underline their importance for the VRP with heterogeneous time windows. In the dynamic extension, we use robust optimization techniques to introduce a novel delay-resistance objective term. To guarantee optimality, we adapt the dominance check of the labeling algorithm. In a computational study, we evaluate the practical impact of this objective term in our model on a set of real-world instances.
Motivated by the significant impact of enforcing routes in VRP solutions, we developed a general-purpose variable fixing technique. It is based on reduced cost fixing, a famous integer linear programming technique that combines important concepts of linear programming with the integrality condition of the variables and a primal bound U on the optimal objective function value. Our novel reduced cost fix and cut method extends this idea by efficiently increasing the amount of accessed local information via rotation of the objective vector. Its iterative version is an exact method for checking whether some variable values can not be attained in a solution with an objective value better than U. Furthermore, we introduce a new class of cuts, the gap-based optimality cuts. They are designed to cut off not only a given fractional optimum of the linear relaxation but also solutions that do not improve upon U. We show that these cuts imply the classic Dantzig cuts and their strengthened version by Charnes and Cooper. We evaluate the performance of our novel techniques on the MIPLIB 2017 Benchmark set to analyze their effectiveness and efficiency on a heterogeneous class of instances. Our implementation in the open-source solver SCIP shows that the new cuts significantly strengthen the dual bound at the root node relaxation. Additionally, both novel techniques can accelerate the solution process of a sophisticated MILP framework.},
url = {https://hdl.handle.net/20.500.11811/13066}
}
urn: https://nbn-resolving.org/urn:nbn:de:hbz:5-82587,
author = {{Lukas Schürmann}},
title = {Reduced Costs for Vehicle Routing and General Mixed-Integer Programs},
school = {Rheinische Friedrich-Wilhelms-Universität Bonn},
year = 2025,
month = may,
note = {Mixed-integer linear programming is a powerful tool for modeling combinatorial optimization problems in a standardized way. Sophisticated solvers that calculate optimal solutions for these programs consist of dozens of individual interacting parts. Throughout the last 70 years, a lot of scientific and commercial resources have been invested in developing new components and refining old ones. Due to the diversity of applications, many general-purpose techniques exist. Additionally, when employed in practice, these algorithms often have to solve multiple problems with a similar structure. Consequently, problem-specific extensions are of high interest. In this thesis, we investigate both types of modules, general-purpose mixed-integer linear programming techniques and algorithmic refinements for a specific combinatorial optimization problem, namely, the vehicle routing problem (VRP).
In VRPs, the task is to deliver goods to customers using a fleet of vehicles at minimal travel cost. We introduce two new variants: the VRP with heterogeneous time windows and its dynamic and robust extension. These variants are motivated by a logistics problem from practice. In contrast to their homogeneous pendants, heterogeneous VRPs imply an additional level of decision-making: Which customer gets assigned to which vehicle type? We elaborate that this question is fundamental in our (mixed-)integer linear programming approach. We present efficient adaptations of state-of-the-art techniques to enforce the allocations of these vehicle-assignment variables throughout the solution process. In our extensive computational experiments, we evaluate different techniques, such as branching and reduced cost fixing for these variables in our branch-cut-and-price algorithm. Our results underline their importance for the VRP with heterogeneous time windows. In the dynamic extension, we use robust optimization techniques to introduce a novel delay-resistance objective term. To guarantee optimality, we adapt the dominance check of the labeling algorithm. In a computational study, we evaluate the practical impact of this objective term in our model on a set of real-world instances.
Motivated by the significant impact of enforcing routes in VRP solutions, we developed a general-purpose variable fixing technique. It is based on reduced cost fixing, a famous integer linear programming technique that combines important concepts of linear programming with the integrality condition of the variables and a primal bound U on the optimal objective function value. Our novel reduced cost fix and cut method extends this idea by efficiently increasing the amount of accessed local information via rotation of the objective vector. Its iterative version is an exact method for checking whether some variable values can not be attained in a solution with an objective value better than U. Furthermore, we introduce a new class of cuts, the gap-based optimality cuts. They are designed to cut off not only a given fractional optimum of the linear relaxation but also solutions that do not improve upon U. We show that these cuts imply the classic Dantzig cuts and their strengthened version by Charnes and Cooper. We evaluate the performance of our novel techniques on the MIPLIB 2017 Benchmark set to analyze their effectiveness and efficiency on a heterogeneous class of instances. Our implementation in the open-source solver SCIP shows that the new cuts significantly strengthen the dual bound at the root node relaxation. Additionally, both novel techniques can accelerate the solution process of a sophisticated MILP framework.},
url = {https://hdl.handle.net/20.500.11811/13066}
}
The following license files are associated with this item:
