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 k≥2, 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.

Extreme functions with an arbitrary number of slopes

Basu, Amitabh;Conforti, Michelangelo;Di Summa, Marco;Paat, Joseph
2018

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 k≥2, 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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11577/3269686
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact