Date of Award

8-2012

Document Type

Thesis

Degree Name

Master of Science (MS)

Legacy Department

Mathematics

Advisor

Belotti, Pietro

Committee Member

Shier , Douglas

Committee Member

Saltzman , Matthew

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.

Share

COinS
 
 

To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.