Thesis Title: Theory and computation of sparse cutting planes

Advisor: Prof. Santanu Dey

Committee Members: Prof. George Nemhauser, Prof. Shabbir Ahmed, Prof. Andy Sun and

Prof. Marco Molinaro (Pontifical Catholic University of Rio de Janeiro)

Date and Time: Thursday, August 4, 2016, 11:00 AM.

Location: ISyE Groseclose 226A

Summary:

A cutting plane is a linear inequality that is valid for all the feasible solutions of an integer program but may separate some points of the linear programming relaxation. Most state-of-the-art integer programming solvers tend to bias their cutting plane selection towards sparse cuts. In this thesis, we conduct a comprehensive study of sparse cutting planes. We also develop a new approximation algorithm for sparse integer programs. 

In the first chapter, we discuss the quality of approximating integer hull by adding sparse cutting planes. Given a polytope $P$ (e.g. the integer hull of a MIP), let $P^k$ be its best approximation using cuts with at most k non-zero coefficients. We consider $d(P, P^k ) = max_{x∈P^k} (min_{y∈P} ||x − y||)$ as a measure of the quality of sparse cuts. In our first result, we present general upper bounds on $d(P, P^k)$ which depend on the number of vertices in the polytope and exhibits three phases as k increases. Our bounds imply that if $P$ has polynomially many vertices, using half sparsity already approximates it very well. Second, we present a lower bound on $d(P, P^k)$ for random polytopes that show that the upper bounds are quite tight. Third, we show that for a class of hard packing IPs, sparse cutting-planes do not approximate the integer hull well.Finally, we show that using sparse cutting-planes in extended formulations is at least as good as using them in the original polyhedron, and give an example where the former is actually much better. 

In the second chapter, we present an analysis of the strength of sparse cutting planes for mixed integer linear programs (MILP) with sparse formulations. We examine three kinds of problems: packing problems, covering problems, and more general MILPs with the only assumption that the objective function is non-negative. Given x a MILP instance of one of these three types, assume that we decide on the support of cutting-planes to be used and the strongest inequalities on these supports are added to the linear programming relaxation. Call the optimal objective function value of the linear programming relaxation together with these cuts as $z^cut$. We present bounds on the ratio of $z^cut$ and the optimal objective function value of the MILP that depends only on the sparsity structure of the constraint matrix and the support of sparse cuts selected, that is, these bounds are completely data independent. These results also shed light on the strength of scenario-specific cuts for two stage stochastic MILPs. 

In the last chapter, we present a new approximation algorithm for solving packing integer programs whose constraint matrix exhibit global sparsity pattern that is known in advance. The algorithm runs in two phases. In the first phase, the sparse packing problem is partitioned into smaller parts and then these small integer programs are solved. In the second phase, the optimal solutions of the smaller problems are patched together into a feasible solution for the original problem by exploiting the sparsity structure of the constraint matrix. We present a theoretical guarantee on the quality of the solution produced by this algorithm, which we show depends only on the sizes of the smaller IPs and the sparsity structure, being otherwise completely data independent. Finally, we experiment on randomly generated large-scale sparse set packing instances and also deterministic equivalent of multi-stage stochastic set-packing integer programs and compare the results of our algorithm to those by CPLEX and also specialized heuristic for packing integer programs based on the state-of-the-art Greedy Randomized Adaptive Search Procedure (GRASP). Our results indicate that on very sparse instances our algorithm shows significant promise over other methods.