Algorithms to separate \(\{0,\frac{1}{2}\}\)-Chvátal-Gomory cuts

DOI10.1007/s00453-008-9218-7zbMath1189.90132OpenAlexW2109933087MaRDI QIDQ834596

Arie M. C. A. Koster, Adrian Zymolka, Manuel Kutschka

Publication date: 27 August 2009

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-008-9218-7

zbMATH Keywords

integer programmingseparation algorithms\(\{0,\frac {1}{2}\}\)-Chvátal-Gomory cuts

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Integer programming (90C10) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Complexity and performance of numerical algorithms (65Y20)

Related Items

Globally solving nonconvex quadratic programming problems with box constraints via integer programming methods, Chvátal-Gomory cuts for the Steiner tree problem, Lifting for the integer knapsack cover polyhedron, Valid Inequalities and Separation Algorithms for the Set Partitioning Problem, Safe and Verified Gomory Mixed-Integer Cuts in a Rational Mixed-Integer Program Framework, Generalized coefficient strengthening cuts for mixed integer programming, Face dimensions of general-purpose cutting planes for mixed-integer linear programs, Tight compact extended relaxations for nonconvex quadratic programming problems with box constraints, On the exact separation of cover inequalities of maximum-depth

Uses Software

• TSPLIB
• SCIP
• MIPLIB
• CPLEX
• MIPLIB2003

Cites Work

• Unnamed Item
• Unnamed Item
• Optimizing over the first Chvátal closure
• Stable multi-sets
• \(\{ 0,\frac12\}\)-Chvátal-Gomory cuts
• On the separation of maximally violated mod-\(k\) cuts
• Projected Chvátal-Gomory cuts for mixed integer linear programs
• Edmonds polytopes and a hierarchy of combinatorial problems
• On cycles and the stable multi-set polytope
• Embedding {0, ½}-Cuts in a Branch-and-Cut Framework: A Computational Study
• Outline of an algorithm for integer solutions to linear programs
• On Cutting Planes
• On the facial structure of set packing polyhedra
• 0, 1/2‐Cuts and the Linear Ordering Problem: Surfaces That Define Facets
• Mod‐2 Cuts Generation Yields the Convex Hull of Bounded Integer Feasible Sets