Home
Resource
Valid inequalities for mixed-integer linear programming problems
PDF
PDF format is widely accepted and good for printing.
Plug-in required
PDF-1(2.17 MB)
Citation & Export
View Usage Statistics
Staff View

Citation & Export
Hide

Simple citation

Yamangil, Emre. Valid inequalities for mixed-integer linear programming problems. Retrieved from https://doi.org/doi:10.7282/T31V5H04

Export

Click here for information about Citation Management Tools at Rutgers.

Statistics
Hide

Description

TitleValid inequalities for mixed-integer linear programming problems
NameYamangil, Emre (author); BEN-ISRAEL, ADI (chair); Boros, Endre (internal member); Gurvich, Vladimir (internal member); Zhao, Yao (internal member); Bent, Russell (outside member); Rutgers University; Graduate School - New Brunswick
Date Created2015
Other Date2015-10 (degree)
SubjectOperations Research, Linear programming
Extent1 online resource (xii, 88 p. : ill.)
DescriptionIn 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.
NotePh.D.
NoteIncludes bibliographical references
Noteby Emre Yamangil
Genretheses, ETD doctoral
Persistent URLhttps://doi.org/doi:10.7282/T31V5H04
Languageeng
CollectionGraduate School - New Brunswick Electronic Theses and Dissertations
Organization NameRutgers, The State University of New Jersey
RightsThe author owns the copyright to this work.
Version 8.5.5
Rutgers University Libraries - Copyright ©2024