Minimal cut-generating functions are nearly extreme

DOI10.1007/s10107-017-1153-4zbMath1414.90230arXiv1701.06698OpenAlexW2611137176MaRDI QIDQ1801006

Amitabh Basu, Robert Hildebrand, Marco Molinaro

Publication date: 26 October 2018

Published in: Mathematical Programming. Series A. Series B, Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

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

zbMATH Keywords

cut-generating functionsdense

Mathematics Subject Classification ID

Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Related Items

Theoretical challenges towards cutting-plane selection ⋮ Approximation of Minimal Functions by Extreme Functions ⋮ Equivariant perturbation in Gomory and Johnson's infinite group problem (V). Software for the continuous and discontinuous 1-row case ⋮ Piecewise smooth extreme functions are piecewise linear ⋮ Dual-feasible functions for integer programming and combinatorial optimization: algorithms, characterizations, and approximations

Uses Software

• infinite group relaxation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Light on the infinite group relaxation. I: Foundations and taxonomy
• Monoidal cut strengthening revisited
• Computing with multi-row gomory cuts
• T-space and cutting planes
• The triangle closure is a polyhedron
• A geometric approach to cut-generating functions
• On the facets of mixed integer programs with two integer variables and two constraints
• A 3-slope theorem for the infinite relaxation in the plane
• Cut-Generating Functions for Integer Variables
• A $(k+1)$-Slope Theorem for the $k$-Dimensional Infinite Group Relaxation
• Minimal Valid Inequalities for Integer Constraints
• Maximal Lattice-Free Convex Sets in Linear Subspaces
• Some continuous functions related to corner polyhedra
• Some continuous functions related to corner polyhedra, II