Clemson University
Branching Rules for Minimum Congestion Multi-Commodity Flow Problems
Abstract
dc:description.abstractIn this paper, we examine various branch and bound algorithms for a minimum congestion origin-destination integer multi-commodity flow problem. The problem consists of finding a routing such that the congestion of the most congested arc is minimum. For our implementation, we assume that all demands are known a priori. We provide a mixed integer linear programming formulation of our problem and propose various new branching rules to solve the model. For each rule, we provide theoretical and experimental proof of their effectiveness. In order to solve large instances, that more accurately portray real-world applications, we outline a path formulation model of our problem. We provide two methods for implementing our branching rules using branch and price.
Degree
thesis:*- Name thesis:degree_name
- Master of Science (MS)
- Level thesis:degree_level
- Thesis
- Discipline thesis:degree_discipline
- Mathematics
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Megaw, Cameron
- Contributors dc:contributor
-
- Belotti, Pietro
- Shier , Douglas
- Saltzman , Matthew
Subjects
dc:subject × 4Identifiers
dc:identifier.*- Repository record dc:identifier
- https://open.clemson.edu/all_theses/1488