Dynamic network design

Abstract

An optimization problem is called offline when the whole input is known in advance, and there are no causality restrictions on the solution structure. In contrast, dynamic optimization models are defined on the literature, in which knowledge about the input is limited and/or there are causality restrictions on partial solutions. Such models include online computation, stochastic optimization and incremental optimization. Network design is a common framework for a large class of optimization problems related to graph connectivity, and the Steiner tree problem is usually considered the central problem in this area. Although a lot of attention has been given to those problems in the offline setting, there are few results about network design problems on dynamic models, in particular, on the incremental model. The aim of this project is to study network design problems on dynamic optimization models. (AU)