Text

theses

In this work we focus on various cutting-plane methods for Mixed-integer Linear Programming (MILP) problems. It is well-known that MILP is a fundamental hard problem and many famous combinatorial optimization problems can be modeled using MILP formulations. It is also well-known that MILP formulations are very useful in many real life applications. Our first, rather theoretical, contribution is a new family of superadditive valid inequalities that are obtained from value functions of special surrogate optimization problems. Superadditive functions hold particular interest in MILP as they are fundamental in building integer programming duality, and all ``deepest valid inequalities'' are known to arise from superadditive functions. We propose a new family of superadditive functions that generate inequalities that are at least as strong as Chvatal-Gomory (CG-) inequalities. A special subfamily provides a new characterization of CG-cuts. Value functions of optimization problems are known to be super additive. We look at special surrogate optimization problems, and measure their complexity in terms of the number of integer variables in them. It turns out that the lowest possible nontrivial complexity class here includes all CG-cuts, and provides some stronger ones, as well. Our next contribution is a practically efficient, polynomial time method to produce ``deepest'' cuts form multiple simplex rows for the so called corner polyhedra. These inequalities have been receiving considerable attention lately. We provide a polynomial time column-generation algorithm to obtain such inequalities, based on an arbitrary (fixed) number of rows of the simplex tableau. We provide numerical evidence that these inequalities improve the CPLEX integrality gap at the root node on a well-known set of MILP instances, MIPLIB. In the last chapter, we consider a particular MILP instance, Optimal Resilient Distribution Grid Design Problem (ORDGDP). This is a problem of critical importance to infrastructure security and recently attracted a lot of attention from various government agencies (e.g. Presidential Policy Directive of Critical Infrastructure Security 2013). We formulate this problem as a MILP and propose various efficient solution methods blending together well-known decomposition ideas to overcome the numerical intractability encountered using commercial MILP software such as CPLEX.

ETD_6565

Ph.D.

Includes bibliographical references

by Emre Yamangil

doi:10.7282/T31V5H04

ETD doctoral

The author owns the copyright to this work.