UC Berkeley

Capacitated fixed-charge network flow problems (CFCNF) are used to model a variety of problems in telecommunication, facility location, production planning and supply chain management. We model CFCNF as a linear mixed-integer program and study the polyhedral structure of various path networks.

We investigate capacitated path substructures and derive strong and easy-to-compute path cover and path pack inequalities. These inequalities are based on an explicit characterization of the submodular inequalities through a fast computation of parametric minimum cuts on a path, and they generalize the well-known flow cover and flow pack inequalities for the single-node relaxations of fixed-charge flow models. Computational results demonstrate the effectiveness of the inequalities when used as cuts in a branch-and-cut algorithm.

Moreover, we consider single item lot-sizing problems with backlogging and inventory bounds and fixed costs (LSBIB). Using the underlying fixed-charge network structure of LSBIB, we derive explicit path pack inequalities that are proposed in this thesis. These inequalities are generalizations of the valid inequalities proposed by Atamturk and Kucukyavuz (2005) for lot-sizing problems under the existence of backlogging. Furthermore, we propose extensions of these inequalities where the binary variables for inventory and backlogging are lifted. Finally, we present computational results suggest that show the effectiveness of both path pack and extended path pack inequalities when used in a branch-and-cut algorithm.