On the matrix cuts of Lovasz and Schrijver and their use in integer programming

An important approach to solving many discrete optimization problems is to associate the discrete set (over which we wish to optimize) with the 0-1 vectors in a given polyhedron and to derive linear inequalities valid for these 0-1 vectors from a linear inequality system defining the polyhedron. Lovasz and Schrijver (1991) described a family of operators, called the matrix-cut operators, which generate strong valid inequalities, called matrix cuts, for the 0-1 vectors in a polyhedron. This family includes the commutative, semidefinite and division operators; each operator can be applied iteratively to obtain, in n iterations for polyhedra in n-space, the convex hull of 0-1 vectors. We study the complexity of matrix-cut based methods for solving 0-1 integer linear programs. We first prove bounds on the (rank) number of iterations required to obtain the integer hull. We show that the upper bound of n, mentioned above, can be attained in the case of the semidefinite operator, answering a question of Goemans. We also determine the semidefinite rank of the standard linear relaxation of the traveling salesman polytope up to a constant factor. We study the use of the semidefinite operator in solving numerical instances and present results on some combinatorial examples and also on a few instances from the MIPLIB test set. Finally, we examine the lengths of cutting-plane proofs based on matrix cuts. We answer a question of Pudlak on such proofs, and prove an exponential lower bound on the length of cutting-plane proofs based on one class of matrix cuts.

Name thesis:degree_name

Doctor of Philosophy

Level thesis:degree_level

Doctoral

Discipline thesis:degree_discipline

Engineering

Grantor

Rice University

Year dc:date.issued

2001

Author dc:creator

• Dash, Sanjeeb

Advisor dc:contributor.advisor

• Cook, William J.

• Mathematics
• Operations research

Statement dc:rights

• Copyright is held by the author, unless otherwise indicated. Permission to reuse, publish, or reproduce the work beyond the bounds of fair use or other exemptions to copyright law must be obtained from the copyright holder.

Language dc:language.iso

eng

Handle dc:identifier.uri

https://hdl.handle.net/1911/17952

OAI identifier oai:identifier

oai:repository.rice.edu:1911/17952