Extreme functions with an arbitrary number of slopes

DOI10.1007/s10107-017-1184-xzbMath1406.90078arXiv1701.06700OpenAlexW2741379864MaRDI QIDQ1801005

Amitabh Basu, Joseph Paat, Marco Di Summa, Michele Conforti

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.06700

zbMATH Keywords

minimal valid functionsinfinite group relaxationcutting plane theoryextreme valid functions

Mathematics Subject Classification ID

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

Related Items

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, Equivariant perturbation in Gomory and Johnson's infinite group problem. VI: The curious case of two-sided discontinuous minimal valid functions, Piecewise smooth extreme functions are piecewise linear, An extreme function which is nonnegative and discontinuous everywhere, 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, Equivariant perturbation in Gomory and Johnson's infinite group problem. VII: Inverse semigroup theory, closures, decomposition of perturbations

Uses Software

• infinite group relaxation
• GitHub
• cutgeneratingfunctionology

Cites Work

• Unnamed Item
• Light on the infinite group relaxation. I: Foundations and taxonomy
• A counterexample to a conjecture of Gomory and Johnson
• On the extreme inequalities of infinite group problems
• Relations between facets of low- and high-dimensional group problems
• Corner polyhedra and their connection with cutting planes
• T-space and cutting planes
• New computer-based search strategies for extreme functions of the Gomory-Johnson infinite group problem
• A geometric approach to cut-generating functions
• A $(k+1)$-Slope Theorem for the $k$-Dimensional Infinite Group Relaxation
• The Group-Theoretic Approach in Mixed Integer Programming
• Facets of Two-Dimensional Infinite Group Problems
• Some continuous functions related to corner polyhedra
• Some continuous functions related to corner polyhedra, II