Matthias Köppe It is well known that the classical Markowitz model for portfolio optimization is extremely sensitive to estimation errors on the expected asset returns. Robust optimization mitigates this issue. We focus on ellipsoidal uncertainty sets around the point estimates of the expected asset returns. We investigate the performance of diagonal estimation-error matrices in the description of … Read more
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 those that admit effective perturbations. We give a precise description of the space of these perturbations as a direct sum of certain finite- and infinite-dimensional subspaces. The … Read more
We give a variant of Basu–Hildebrand–Molinaro’s approximation theorem for continuous minimal valid functions for Gomory–Johnson’s infinite group problem by piecewise linear two-slope extreme functions [Minimal cut-generating functions are nearly extreme, IPCO 2016]. Our theorem is for piecewise linear minimal valid functions that have only rational breakpoints (in 1/q Z for some q ∈ N) and … Read more
We study two techniques to obtain new families of classical and general Dual-Feasible Functions: A conversion from minimal Gomory–Johnson functions; and computer-based search using polyhedral computation and an automatic maximality and extremality test. Citation6 pages extended abstract to appear in Proc. LAGOS 2017, with 21 pages of appendix.ArticleDownload View PDF
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 … Read more
We present software for investigations with cut generating functions in the Gomory-Johnson model and extensions, implemented in the computer algebra system SageMath. CitationAn extended abstract of 8 pages appeared under the title “Software for cut-generating functions in the Gomory–Johnson model and beyond” in Proc. International Congress on Mathematical Software 2016ArticleDownload View PDF
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 linear minimal valid functions. This anomalous behavior results from combining features of Hildebrand’s two-sided discontinuous extreme functions and Basu–Hildebrand–Koeppe’s piecewise linear extreme function with irrational breakpoints. … Read more
Using a metaprogramming technique and semialgebraic computations, we provide computer-based proofs for old and new cutting-plane theorems in Gomory–Johnson’s model of cut generating functions. Citationto be presented at ISCO 2016ArticleDownload View PDF
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 several open questions. ArticleDownload View PDF
In this note we announce the availability of an electronic compendium of extreme functions for Gomory–Johnson’s infinite group problem. These functions serve as the strongest cut-generating functions for integer linear optimization problems. We also close several gaps in the literature. ArticleDownload View PDF