On cutting-plane proofs in combinatorial optimization
From MaRDI portal
Publication:1123134
DOI10.1016/0024-3795(89)90476-XzbMath0676.90059MaRDI QIDQ1123134
Publication date: 1989
Published in: Linear Algebra and its Applications (Search for Journal in Brave)
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
90C35: Programming involving graphs or networks
90C10: Integer programming
90C05: Linear programming
90C27: Combinatorial optimization
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
90C09: Boolean programming
52Bxx: Polytopes and polyhedra
Related Items
Lower bounds for resolution and cutting plane proofs and monotone computations, The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds, The volume of relaxed Boolean-quadric and cut polytopes, On the Chvátal rank of polytopes in the 0/1 cube