“INTEGER PROGRAMMING, A TECHNOLOGY”
Anureet Saxena
Friday, May 4, 2007
1:30 pm
153 Posner Hall
Mixed Integer Programming addresses the problem of minimizing (or maximizing) a linear function over a set of linear constraints such that some or all of the decision variables are constrained to be integers. Over the last five decades, mixed integer programming has emerged as a formidable optimization technology and has thereby opened research avenues which did not exist before. This thesis examines some of these new research opportunities in the form of four essays.
Optimizing over the Split Closure
The polyhedron defined by all the split cuts obtainable directly from the LP-relaxation P of a mixed integer program (MIP) is termed the (elementary) split closure of P. This essay deals with the problem of optimizing over the elementary split closure. We formulate the corresponding separation problem as a nonlinear mixed integer program that can be treated as a parametric mixed integer linear program (PMILP) with a single parameter in the objective function and the right hand side. We develop an algorithmic framework to deal with the resulting PMILP by creating and maintaining a dynamically updated grid of parameter values, and use the corresponding mixed integer programs to generate rank 1 split cuts. We report our computational results on well-known benchmark instances from MIPLIB 3.0 and several classes of structured integer and mixed integer problems, which include capacitated versions of warehouse location, single-source facility location, p-median, fixed charge network flow, multi-commodity network design with splittable and unsplittable flows, and lot sizing problems. Our computational results show that split closure closes around 80% of the duality gap on these instances, on average.
Finally, we illustrate an application of our work in solving a real-world mixed integer program named ‘arki001′ which arose in themetallurgical industry; this problem was first posed in 1995 and was subsequently included in the MIPLIB repository; despite several attempts it remained unsolved until our work.
Probabilistic Set Covering Problem
In this essay we address the following probabilistic version (PSC) of the set covering problem: min { cx | P (Ax >= xi) >= p, x_j in {0,1}^N} where A is a 0-1 matrix, xi is a random 0-1 vector and p in (0,1] is the threshold probability level. We formulate (PSC) as a mixed integer non-linear program (MINLP) and linearize it to obtain a MIP reformulation We introduce the concepts of p-inefficiency and polarity cuts. While the former is aimed at reducing the number of constraints in our model, the latter is used as a strengthening device to obtain stronger formulations. A hierarchy of relaxations for (PSC) is introduced, and fundamental relationships between the relaxations are established culminating with a MIP reformulation of (PSC) with no additional integer constrained variables. We corroborate our theoretical findings by an extensive computational experiment on a test-bed consisting of almost 10,000 probabilistic instances. Our computational results show that our procedure is orders of magnitude faster than any of the existing approaches to solve (PSC), and in many cases can reduce hours of computing time to fraction of seconds.
Finally, we discuss a large scale implementation of our algorithm and apply it to the probabilistic variant of the network design problem; we discuss preliminary computational results on test-instances based on network topologies from real-world backbone and metropolitan networks.
Polyhedral Analysis of the Set Covering Polytope
The third essay of this thesis concerns polyhedral analysis of the set covering polytope P(A)=conv {x in {0,1}^{n} | Ax>= 1} with focus on valid inequalities with coefficients in {0,… ,k} (k in Z, k>1). We introduce the notion of “cover hypergraph” – combinatorial object which captures the polyhedral properties of a valid inequality, and demonstrate its application in generalizing some of the well-known results from the literature, and in development of new ideas. We study two polynomial time (lifting and strengthening) procedures for generating minimally valid inequalities and give a complete characterization of the class of inequalities produced by each of them. We propose an alternative lifting procedure, referred to as the “Relaxation Lifting Procedure” (RLP), which is more efficient than the conventional one. As a byproduct of this investigation, we give a complete and compact (polynomial sized) characterization of the class of inequalities which can be obtained by sequential and simultaneous relaxation lifting, and a sequence independent lifting procedure for lifting inequalities with coefficients in {0,1,2}. Finally, a polynomial sized mixed integer programming model for separating inequalities with coefficients in {0,… ,k} is briefly discussed.
Contributions to Disjunctive Programming
The last essay of this thesis dwells on disjunctive programming – the theory of optimization over unions of polyhedra. Given a polyhedral set P, a disjunction D and a point x in P, the first part of the essay addresses the following membership problem: show that x in the disjunctive closure, say Q, of P defined by D or find a valid inequality for Q which is violated by x. We introduce the notion of separation functions and illustrate their application in the analysis of the above problem; our main result concerns facial disjunctions and simplifications of the membership problem arising from such disjunctions. We show that, unlike the case of split disjunctions, the separation problem associated with several well-known families of facial disjunctions (such as GUB disjunctions, set-covering disjunctions, facial split disjunction etc) can be modelled as mixed integer programs. Finally, we investigate the class of cutting planes which can be obtained from the conic relaxation (basis cone) of a mixed integer program using arbitrary disjunctions.
The first essay and part of the fourth essay is a joint work with Dr. E. Balas. The first part of the second essay was developed jointly with V. Goyal and Dr. M. Lejeune, while the second part of the second essay is an ongoing work with Dr. P. Belotti. Part of the fourth essay is an ongoing work with Dr. G. Pataki. The second and fourth essays are still under development.
