Extreme functions with an arbitrary number of slopes

DOI10.1007/978-3-319-33461-5_16zbMATH Open1406.90078arXiv1701.06700OpenAlexW2741379864MaRDI QIDQ1801005FDOQ1801005

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)

Abstract: For the one dimensional infinite group relaxation, we construct a sequence of extreme valid functions that are piecewise linear and such that for every natural number $kgeq2$, there is a function in the sequence with $k$ slopes. This settles an open question in this area regarding a universal bound on the number of slopes for extreme functions. The function which is the pointwise limit of this sequence is an extreme valid function that is continuous and has an infinite number of slopes. This provides a new and more refined counterexample to an old conjecture of Gomory and Johnson stating that all extreme functions are piecewise linear. These constructions are extended to obtain functions for the higher dimensional group problems via the sequential-merge operation of Dey and Richard.

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

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

Cites Work

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

Cited In (8)

• Piecewise smooth extreme functions are piecewise linear
• 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
• 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
• 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. VII: Inverse semigroup theory, closures, decomposition of perturbations

Uses Software

• infinite group relaxation
• cutgeneratingfunctionology
• GitHub

This page was built for publication: Extreme functions with an arbitrary number of slopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1801005)