On cutting-plane proofs in combinatorial optimization

From MaRDI portal

Publication:1123134

Jump to:navigation, search

DOI10.1016/0024-3795(89)90476-XzbMath0676.90059OpenAlexW2011805810MaRDI QIDQ1123134

S. H. Smith

Publication date: 1989

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0024-3795(89)90476-x

zbMATH Keywords

maximum cut lower bounds valid inequalities set covering travelling salesman knapsack set partitioning cutting plane proof bipartite subgraph acyclic subdigraph depth of an inequality rank of a polyhedron

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Linear programming (90C05) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Boolean programming (90C09) Polytopes and polyhedra (52Bxx)

Related Items

On the Chvátal-rank of Antiwebs, Rank of random half-integral polytopes — extended abstract —, Vašek Chvátal: a very short introduction (on the occasion of his 60th birthday), The volume of relaxed Boolean-quadric and cut polytopes, On Some Polytopes Contained in the 0,1 Hypercube that Have a Small Chvátal Rank, Theoretical challenges towards cutting-plane selection, Elementary polytopes with high lift-and-project ranks for strong positive semidefinite operators, Lattice closures of polyhedra, Integer-empty polytopes in the 0/1-cube with maximal Gomory-Chvàtal rank, On polytopes with linear rank with respect to generalizations of the split closure, Complexity of optimizing over the integers, Lower bounds on the size of general branch-and-bound trees, Complexity of branch-and-bound and cutting planes in mixed-integer optimization, Lower bounds for the Chvàtal-Gomory rank in the 0/1 cube, Random half-integral polytopes, Cutting planes cannot approximate some integer programs, Clique problem, cutting plane proofs and communication complexity, On the Chvátal rank of polytopes in the 0/1 cube, The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds, On the Chvátal rank of linear relaxations of the stable set polytope, A note on the Chvátal-rank of clique family inequalities, Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra, Lower bounds for resolution and cutting plane proofs and monotone computations, Design and Verify: A New Scheme for Generating Cutting-Planes, Cutting planes from extended LP formulations, The stable set polytope of quasi-line graphs, Transitive packing, On semantic cutting planes with very small coefficients, Design and verify: a new scheme for generating cutting-planes, Several notes on the power of Gomory-Chvátal cuts, Aggregation-based cutting-planes for packing and covering integer programs, A short proof for the polyhedrality of the Chvátal-Gomory closure of a compact convex set, Valid inequalities for mixed integer linear programs, On the rational polytopes with Chvátal rank 1, A simple effective heuristic for embedded mixed-integer quadratic programming, On some polytopes contained in the 0,1 hypercube that have a small Chvátal rank, Characterizing Polytopes in the 0/1-Cube with Bounded Chvátal-Gomory Rank, Complexity of branch-and-bound and cutting planes in mixed-integer optimization. II, A lower bound on the Chvátal-rank of Antiwebs, Optimizing over the subtour polytope of the travelling salesman problem

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:1123134&oldid=13171327"