{"id":{"repo_id":"rice","oai_identifier":"oai:repository.rice.edu:1911/17952"},"canonical_url":"https://search.dev.ndltd.org/etd/rice/oai:repository.rice.edu:1911/17952","repository":{"repo_id":"rice","name":"Rice University","base_url":"https://repository.rice.edu/server/oai/request"},"display":{"title":"On the matrix cuts of Lovasz and Schrijver and their use in integer programming","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Dash, Sanjeeb"],"institution":"Rice University","degree_name":"Doctor of Philosophy","degree_level":"Doctoral","degree_discipline":"Engineering","degree_department":null,"school":null,"contributors":[],"advisors":["Cook, William J."],"committee_chairs":[],"committee_members":[],"year":2001,"date_issued":"2001","date_published":"2001","updated_at":"2026-07-24T04:10:39Z","subjects":["Mathematics","Operations research"],"languages":["eng"],"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."],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/1911/17952","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Cook, William J."]},{"key":"dc:creator","label":"Author","values":["Dash, Sanjeeb"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2009-06-04T08:37:48Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2009-06-04T08:37:48Z"]},{"key":"dc:date.issued","label":"Date","values":["2001"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Doctoral"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Doctor of Philosophy"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Rice University"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Mathematics","Operations research"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["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."]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/1911/17952"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["On the matrix cuts of Lovasz and Schrijver and their use in integer programming"]}]}],"canonical_facts":{"dc:contributor.advisor":["Cook, William J."],"dc:creator":["Dash, Sanjeeb"],"dc:date.accessioned":["2009-06-04T08:37:48Z"],"dc:date.available":["2009-06-04T08:37:48Z"],"dc:date.issued":["2001"],"dc:description.abstract":["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."],"dc:format.mimetype":["application/pdf"],"dc:identifier.uri":["https://hdl.handle.net/1911/17952"],"dc:language.iso":["eng"],"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."],"dc:subject":["Mathematics","Operations research"],"dc:title":["On the matrix cuts of Lovasz and Schrijver and their use in integer programming"],"dc:type":["Thesis"],"thesis:degree_discipline":["Engineering"],"thesis:degree_level":["Doctoral"],"thesis:degree_name":["Doctor of Philosophy"],"thesis:institution_name":["Rice University"]},"updated_at":"2026-07-24T04:10:39Z"}