75 citations · 671 across the 41 of their papers we have counts for
27 papers · 1 filter
Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. VII. Inverse semigroup theory, closures, decomposition of perturbations
Robert Hildebrand, Matthias Köppe, Yuan Zhou
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…
Characterization and Approximation of Strong General Dual Feasible Functions
Matthias Köppe, Jiawei Wang
Dual feasible functions (DFFs) have been used to provide bounds for standard packing problems and valid inequalities for integer optimization problems. In this paper, the connectio…
Structure and Interpretation of Dual-Feasible Functions
Matthias Köppe, Jiawei Wang
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 usin…
On the notions of facets, weak facets, and extreme functions of the Gomory-Johnson infinite group problem
Matthias Köppe, Yuan Zhou
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 kn…
Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. V. Software for the continuous and discontinuous 1-row case
Chun Yu Hong, Matthias Köppe, Yuan Zhou
We present software for investigations with cut-generating functions in the Gomory--Johnson model and extensions, implemented in the computer algebra system SageMath.
Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. VI. The curious case of two-sided discontinuous minimal valid functions
Matthias Köppe, Yuan Zhou
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 ot…
Software for cut-generating functions in the Gomory--Johnson model and beyond
Chun Yu Hong, Matthias Köppe, Yuan Zhou
We present software for investigations with cut generating functions in the Gomory-Johnson model and extensions, implemented in the computer algebra system SageMath.
Toward computer-assisted discovery and automated proofs of cutting plane theorems
Matthias Köppe, Yuan Zhou
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 generati…
Approximating the maximum of a polynomial over a polytope: Handelman decomposition and continuous generating functions
Jesús De Loera, Brandon Dutra, Matthias Köppe
We investigate a way to approximate the maximum of a polynomial over a polytopal region by using Handelman's polynomial decomposition and continuous multivariate generating functio…
New computer-based search strategies for extreme functions of the Gomory--Johnson infinite group problem
Matthias Köppe, Yuan Zhou
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 ex…
An Electronic Compendium of Extreme Functions for the Gomory--Johnson Infinite Group Problem
Matthias Köppe, Yuan Zhou
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-…
Light on the Infinite Group Relaxation
Amitabh Basu, Robert Hildebrand, Matthias Köppe
This is a survey on the infinite group problem, an infinite-dimensional relaxation of integer linear optimization problems introduced by Ralph Gomory and Ellis Johnson in their gro…
Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. III. Foundations for the k-Dimensional Case with Applications to k=2
Amitabh Basu, Robert Hildebrand, Matthias Köppe
We develop foundational tools for classifying the extreme valid functions for the k-dimensional infinite group problem. In particular, (1) we present the general regular solution t…
Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. II. The Unimodular Two-Dimensional Case
Amitabh Basu, Robert Hildebrand, Matthias Köppe
We give an algorithm for testing the extremality of a large class of minimal valid functions for the two-dimensional infinite group problem.
Graver basis and proximity techniques for block-structured separable convex integer minimization problems
Raymond Hemmecke, Matthias Köppe, Robert Weismantel
We consider N-fold 4-block decomposable integer programs, which simultaneously generalize N-fold integer programs and two-stage stochastic integer programs with N scenarios. In pre…
Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. I. The One-Dimensional Case
Amitabh Basu, Robert Hildebrand, Matthias Köppe
We give 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…
The Triangle Closure is a Polyhedron
Amitabh Basu, Robert Hildebrand, Matthias Köppe
Recently, cutting planes derived from maximal lattice-free convex sets have been studied intensively by the integer programming community. An important question in this research ar…
A (k+1)-Slope Theorem for the k-Dimensional Infinite Group Relaxation
Amitabh Basu, Robert Hildebrand, Matthias Köppe +1
We prove that any minimal valid function for the k-dimensional infinite group relaxation that is piecewise linear with at most k+1 slopes and does not factor through a linear map w…
Unique Minimal Liftings for Simplicial Polytopes
Amitabh Basu, Gérard Cornuéjols, Matthias Köppe
For a minimal inequality derived from a maximal lattice-free simplicial polytope in , we investigate the region where minimal liftings are uniquely defined, and we characteri…
A new Lenstra-type Algorithm for Quasiconvex Polynomial Integer Minimization with Complexity 2^O(n log n)
Robert Hildebrand, Matthias Köppe
We study the integer minimization of a quasiconvex polynomial with quasiconvex polynomial constraints. We propose a new algorithm that is an improvement upon the best known algorit…
A polynomial-time algorithm for optimizing over N-fold 4-block decomposable integer programs
Raymond Hemmecke, Matthias Köppe, Robert Weismantel
In this paper we generalize N-fold integer programs and two-stage integer programs with N scenarios to N-fold 4-block decomposable integer programs. We show that for fixed blocks b…
A parametric integer programming algorithm for bilevel mixed integer programs
Matthias Köppe, Maurice Queyranne, Christopher Thomas Ryan
We consider discrete bilevel optimization problems where the follower solves an integer program with a fixed number of variables. Using recent results in parametric integer program…
Pareto Optima of Multicriteria Integer Linear Programs
Jesús A. De Loera, Raymond Hemmecke, Matthias Köppe
We settle the computational complexity of fundamental questions related to multicriteria integer linear programs, when the dimensions of the strategy space and of the outcome space…
FPTAS for optimizing polynomials over the mixed-integer points of polytopes in fixed dimension
Jesús A. De Loera, Raymond Hemmecke, Matthias Köppe +1
We show the existence of a fully polynomial-time approximation scheme (FPTAS) for the problem of maximizing a non-negative polynomial over mixed-integer sets in convex polytopes, w…