Piecewise smooth extreme functions are piecewise linear

• 成果类型: Article
• 署名作者: Di Summa, Marco
• 署名单位: University of Padua
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-018-1330-0
• 发表日期: 2020
• 页码: 265-293
• 关键词: gomory

摘要

The infinite relaxations in integer programming were introduced by Gomory and Johnson to provide a general framework for the theory of cutting planes: the so-called valid functions, and in particular the minimal and extreme functions, can be seen as automatic rules for the generation of cuts. However, while many extreme functions are piecewise linear and therefore easy to describe, the set of extreme functions turns out to have a very complicated mathematical structure, as several extreme functions are known that exhibit a somewhat pathological behavior. In this paper we show that if some smoothness assumption is imposed on an extreme function pi, then pi is necessarily piecewise linear. More precisely, we show that if a continuous extreme function for the Gomory-Johnson one-dimensional infinite group relaxation is a piecewise C-2 function, then it is a piecewise linear function.