# On the Notions of Facets, Weak Facets, and Extreme Functions of the Gomory-Johnson Infinite Group Problem

@inproceedings{Kppe2017OnTN, title={On the Notions of Facets, Weak Facets, and Extreme Functions of the Gomory-Johnson Infinite Group Problem}, author={Matthias K{\"o}ppe and Yuan Zhou}, booktitle={IPCO}, year={2017} }

We investigate three competing notions that generalize the notion of a facet of finite-dimensional polyhedra to the infinite-dimensional Gomory–Johnson model. These notions were known to coincide for continuous piecewise linear functions with rational breakpoints. We show that two of the notions, extreme functions and facets, coincide for the case of continuous piecewise linear functions, removing the hypothesis regarding rational breakpoints. We then separate the three notions using… Expand

#### 9 Citations

Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. VI. The Curious Case of Two-Sided Discontinuous Functions

- Mathematics
- 2016

We construct a two-sided discontinuous piecewise linear minimal valid function for the 1-row Gomory--Johnson model which is not extreme, but which is not a convex combination of other piecewise… Expand

Extreme Functions with an Arbitrary Number of Slopes

- Mathematics, Computer Science
- IPCO
- 2016

This work constructs a sequence of extreme valid functions that are piecewise linear and such that for every natural number k, there is a function in the sequence with k slopes that is an extreme valid function that is continuous and has an infinite number of slopes. Expand

Extreme functions with an arbitrary number of slopes

- Mathematics, Computer Science
- Math. Program.
- 2018

A sequence of extreme valid functions that are piecewise linear and such that for every natural number k, there is a function in the sequence with k slopes settles an open question regarding a universal bound on the number of slopes for extreme functions. Expand

Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. VII. Inverse semigroup theory, closures, decomposition of perturbations

- Mathematics
- 2018

In this self-contained paper, we present a theory of the piecewise linear minimal valid functions for the 1-row Gomory-Johnson infinite group problem. The non-extreme minimal valid functions are… Expand

Equivariant perturbation in Gomory and Johnson's infinite group problem. VI. The curious case of two-sided discontinuous minimal valid functions

- Mathematics, Computer Science
- Discret. Optim.
- 2018

A two-sided discontinuous piecewise piecewise linear minimal valid function is constructed for the 1-row Gomory--Johnson model which is not extreme, butWhich is not a convex combination of other piecewiselinear minimal valid functions. Expand

An extreme function which is nonnegative and discontinuous everywhere

- Mathematics, Computer Science
- Math. Program.
- 2020

This paper considers Gomory and Johnson’s infinite group model with a single row, and constructs an extreme function π, which is discontinuous everywhere, within the set of nonnegative valid functions. Expand

New computer-based search strategies for extreme functions of the Gomory–Johnson infinite group problem

- Mathematics, Computer Science
- Math. Program. Comput.
- 2017

We describe new computer-based search strategies for extreme functions for the Gomory–Johnson infinite group problem. They lead to the discovery of new extreme functions, whose existence settles… Expand

Theoretical challenges towards cutting-plane selection

- Computer Science, Mathematics
- Math. Program.
- 2018

The different classes of cutting-planes available, known theoretical results about their relative strength, important issues pertaining to cut selection, and some possible new directions to be pursued in order to accomplish cutting-plane selection in a more principled manner are reviewed. Expand

O C ] 7 M ay 2 01 8 Theoretical challenges towards cutting-plane selection

- 2018

While many classes of cutting-planes are at the disposal of integer programming solvers, our scientific understanding is far from complete with regards to cutting-plane selection, i.e., the task of… Expand

#### References

SHOWING 1-10 OF 25 REFERENCES

The Structure of the Infinite Models in Integer Programming

- Mathematics, Computer Science
- IPCO
- 2017

The relationships between these two descriptions of infinite models, convex hull of some points or as the intersection of halfspaces derived from valid functions, are studied to discover new facts about corner polyhedra with non-rational data. Expand

Facets of Two-Dimensional Infinite Group Problems

- Mathematics, Computer Science
- Math. Oper. Res.
- 2008

Two different constructions are presented that yield the first known families of facet-defining inequalities for 2DMIIGP, and it is proved that this construction yields all continuous piecewise linear facets of the two-dimensional group problem that have exactly two gradients. Expand

Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. VI. The Curious Case of Two-Sided Discontinuous Functions

- Mathematics
- 2016

We construct a two-sided discontinuous piecewise linear minimal valid function for the 1-row Gomory--Johnson model which is not extreme, but which is not a convex combination of other piecewise… Expand

T-space and cutting planes

- Mathematics, Computer Science
- Math. Program.
- 2003

It is shown how knowledge about T-space translates directly into cutting planes for general integer programming problems, and a variety of constructions for T- space facets are given, all of which translate intocutting planes, and continuous families of facets are introduced. Expand

Corner Polyhedron and Intersection Cuts

- Mathematics
- 2011

Four decades ago, Gomory introduced the corner polyhedron as a relaxation of a mixed integer set in tableau form and Balas introduced intersection cuts for the corner polyhedron. A recent paper of… Expand

Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. I. The One-Dimensional Case

- Mathematics, Computer Science
- Math. Oper. Res.
- 2015

An algorithm for testing the extremality of minimal valid functions for Gomory and Johnson's infinite group problem that are piecewise linear possibly discontinuous with rational breakpoints and an extreme function, whose extremality follows from a new principle is presented. Expand

Some continuous functions related to corner polyhedra

- Mathematics, Computer Science
- Math. Program.
- 1972

It is shown how faces previously generated and those given here can be used to give valid inequalities for any integer program. Expand

Light on the infinite group relaxation I: foundations and taxonomy

- Computer Science, Mathematics
- 4OR
- 2016

The survey presents the infinite group problem in the modern context of cut generating functions with recent developments, such as algorithms for testing extremality and breakthroughs for the k-row problem for general k≥1 that extend previous work on the single-row and two-row problems. Expand

Light on the infinite group relaxation II: sufficient conditions for extremality, sequences, and algorithms

- Computer Science, Mathematics
- 4OR
- 2016

This survey presents the infinite group problem in the modern context of cut generating functions with recent developments, such as algorithms for testing extremality and breakthroughs for the k-row problem for general $$k\ge 1$$k≥1 that extend previous work on the single-row and two-row problems. Expand

Equivariant perturbation in Gomory and Johnson's infinite group problem. VI. The curious case of two-sided discontinuous minimal valid functions

- Mathematics, Computer Science
- Discret. Optim.
- 2018

A two-sided discontinuous piecewise piecewise linear minimal valid function is constructed for the 1-row Gomory--Johnson model which is not extreme, butWhich is not a convex combination of other piecewiselinear minimal valid functions. Expand