Title:
  Algorithms for Network Design Problems

Author:
  Frederico Rodrigues Borges da Cruz

Abstract:
  In this thesis, a special class of network design problems representing an
important collection of mixed-integer programming problems is studied.
The problems are defined on a digraph, where an optimal subset of arcs and
nodes fulfilling a special set of constraints is sought. The uncapacitated
fixed-charge network flow (UFNF) problem is presented along with a 
comprehensive review of the research advances in the field. An original 
solution algorithm is developed and its practical efficiency is demonstrated
through a comprehensive set of computational experiments. The multi-level 
network design (MLND) problem is next developed and a review of the research 
efforts on similar problems is presented showing the increasing attention
such models have recently received. The methods developed for the UFNF 
problem are extended to the MLND problem, achieving encouraging 
computational results. Also, parallel implementations for the algorithms 
are developed, demonstrating that this is a promising area for future 
investigations. Some possible research directions for further study 
on the MLND problem are proposed and briefly outlined. Finally, it is 
noteworthy to point out that the main results in this thesis may be 
extended to many other network design problems.

Keywords:
  Network design; mixed-integer programming; location; network flows.