\(\{ 0,\frac12\}\)-Chvátal-Gomory cuts

DOI10.1007/BF02592196zbMath0855.90088MaRDI QIDQ1814791

Publication date: 24 November 1996

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

polynomial time acyclic subgraph linear ordering polytopes integer polyhedron clique partitioning valid inequality separation problem plant location asymmetric traveling salesman binary clutter

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Trees (05C05) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Integer programming (90C10) Combinatorial optimization (90C27)

Related Items

On the p-median polytope of fork-free graphs, Globally solving nonconvex quadratic programming problems with box constraints via integer programming methods, Single-commodity robust network design with finite and hose demand sets, Algorithms to separate \(\{0,\frac{1}{2}\}\)-Chvátal-Gomory cuts, Vašek Chvátal: a very short introduction (on the occasion of his 60th birthday), Applying mod-\(k\)-cuts for solving linear ordering problems, Theoretical challenges towards cutting-plane selection, An improved integer linear programming formulation for the closest 0-1 string problem, Local cuts for mixed-integer programming, Simple odd \(\beta \)-cycle inequalities for binary polynomial optimization, On the partial order polytope of a digraph, Chvátal-Gomory cuts for the Steiner tree problem, On the tree augmentation problem, On the complexity of recognizing integrality and total dual integrality of the \(\{0,1/2\}\)-closure, Generalised 2-circulant inequalities for the max-cut problem, When the Gomory-chvátal closure coincides with the integer hull, On the complete set packing and set partitioning polytopes: properties and rank 1 facets, A note on the 2-circulant inequalities for the MAX-cut problem, Lattice closures of polyhedra, The opportunistic replacement problem: theoretical analyses and numerical tests, On the membership problem for the \({0, 1/2}\)-closure, Lifting for the integer knapsack cover polyhedron, Integer programming models for round Robin tournaments, Extended formulations for perfect domination problems and their algorithmic implications, Valid Inequalities and Separation Algorithms for the Set Partitioning Problem, A polyhedral study of lifted multicuts, Thinning out Steiner trees: a node-based model for uniform edge costs, Rational and integral \(k\)-regular matrices., Facets from gadgets, Optimization with binet matrices, A two-level graph partitioning problem arising in mobile wireless communications, Transitive packing, Metric inequalities and the network loading problem, An integer programming approach to optimal basic block instruction scheduling for single-issue processors, On the \(p\)-median polytope and the directed odd cycle inequalities: triangle-free oriented graphs, Projection results for the \(k\)-partition problem, Three enhancements for optimization-based bound tightening, A dynamic reformulation heuristic for generalized interdiction problems, Multicommodity flow in trees: packing via covering and iterated relaxation, Cutting planes in integer and mixed integer programming, Discrete relaxations of combinatorial programs, Chvatal--Gomory--tier cuts for general integer programs, Max-Weight Integral Multicommodity Flow in Spiders and High-Capacity Trees, A short proof for the polyhedrality of the Chvátal-Gomory closure of a compact convex set, On a connection between facility location and perfect graphs, On the rational polytopes with Chvátal rank 1, The confined primal integral: a measure to benchmark heuristic MINLP solvers against global MINLP solvers, Set covering and packing formulations of graph coloring: Algorithms and first polyhedral results, A separation algorithm for the simple plant location problem, Face dimensions of general-purpose cutting planes for mixed-integer linear programs, A branch\&cut approach to recharging and refueling infrastructure planning, The Chvátal closure of generalized stable sets in bidirected graphs, On matroid parity and matching polytopes, Stable sets, corner polyhedra and the Chvàtal closure, Virtual private network design over the first Chvátal closure, Tight compact extended relaxations for nonconvex quadratic programming problems with box constraints, Separating lifted odd-hole inequalities to solve the index selection problem, A new separation algorithm for the Boolean quadric and cut polytopes, On cycles and the stable multi-set polytope, On small-depth tree augmentations, A fast algorithm for minimum weight odd circuits and cuts in planar graphs, Totally tight Chvatal-Gomory cuts

Cites Work