Robust network flow and knapsack polyhedra

In this dissertation, we study robust optimization problems and develop new algorithms to solve them. We discuss three problems in the dissertation: two-stage robust network flow and design, the precedence-constraint fixed-charge (PCFC) polytope, and 0-1 robust knapsack polytope.;In the first part, we describe a two-stage robust optimization approach for solving network flow and design problems with uncertain demand. For network flow and design under demand uncertainty we give a characterization of the first-stage robust decisions with an exponential number of constraints and prove that the corresponding separation problem is NP -hard even for a network flow problem on a bipartite graph. We show, however, that if the second-stage network topology is totally ordered or an arborescence, then the separation problem is tractable.;We generalize the approach to multi-commodity network flow and design, and give applications to lot-sizing and location-transportation problems. By projecting out second-stage flow variables we define an upper bounding problem for the two-stage min-max-min optimization problem. Finally, we present computational results comparing the proposed two-stage robust optimization approach with single-stage robust optimization as well as scenario-based two-stage stochastic optimization.;In the second part, we study the polyhedral structure of the PCFC problem, which is a generalization of the separation problem of the robust network flow problem. It also has many applications in investment problems and scheduling problems. We derive valid lifting inequalities for the polyhedron and study their strength. For an induced minimal cover, we give an explicit expression of the lifting coefficients. For a given fractional point, a polynomial separation algorithm to find an optimal lifting order is given. We also present the computational experiments that show a big reduction in the integrality gap and computational time.;In the third part, we study the robust 0--1 knapsack problem with uncertain cost and constraint coefficients. The problem is formulated as a mixed-integer program. We propose strong lifting inequalities. The lifting coefficients can be computed in polynomial time in the robust selection problem. We propose a heuristic algorithm to compute the lifting inequalities for the robust 0--1 knapsack problem.