An electronic compendium of extreme functions for the Gomory-Johnson infinite group problem

DOI10.1016/j.orl.2015.06.004zbMath1408.90002arXiv1411.5121OpenAlexW1547823805MaRDI QIDQ1785398

Matthias Köppe, Yuan Zhou

Publication date: 28 September 2018

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1411.5121

zbMATH Keywords

softwareinteger programmingcutting planesinfinite group relaxation

Mathematics Subject Classification ID

Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Software, source code, etc. for problems pertaining to operations research and mathematical programming (90-04)

Related Items

Theoretical challenges towards cutting-plane selection, The structure of the infinite models in integer programming, New computer-based search strategies for extreme functions of the Gomory-Johnson infinite group problem, Equivariant perturbation in Gomory and Johnson's infinite group problem (V). Software for the continuous and discontinuous 1-row case, Some cut-generating functions for second-order conic sets, Piecewise smooth extreme functions are piecewise linear, Lifting convex inequalities for bipartite bilinear programs, Lifting convex inequalities for bipartite bilinear programs, Software for Cut-Generating Functions in the Gomory–Johnson Model and Beyond, Dual-feasible functions for integer programming and combinatorial optimization: algorithms, characterizations, and approximations, Toward Computer-Assisted Discovery and Automated Proofs of Cutting Plane Theorems, Equivariant perturbation in Gomory and Johnson's infinite group problem. VII: Inverse semigroup theory, closures, decomposition of perturbations, Light on the infinite group relaxation. I: Foundations and taxonomy

Uses Software

• SageMath
• infinite group relaxation
• GitHub

Cites Work

• A counterexample to a conjecture of Gomory and Johnson
• On the extreme inequalities of infinite group problems
• Valid inequalities for mips and group polyhedra from approximate liftings
• T-space and cutting planes
• Cyclic group and knapsack facets
• Generalized mixed integer rounding inequalities: Facets for infinite group polyhedra
• The Group-Theoretic Approach in Mixed Integer Programming
• Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. I. The One-Dimensional Case
• Some continuous functions related to corner polyhedra
• Some continuous functions related to corner polyhedra, II