Back to search

Clemson University

Branching Rules for Minimum Congestion Multi-Commodity Flow Problems

Abstract

dc:description.abstract

In 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 × 4

Identifiers

dc:identifier.*
Repository record dc:identifier
https://open.clemson.edu/all_theses/1488

Chain of custody

source
Harvested from
Clemson University
Base URL
open.clemson.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Megaw, Cameron. Branching Rules for Minimum Congestion Multi-Commodity Flow Problems. Thesis thesis, https://open.clemson.edu/all_theses/1488