75 citations · 671 across the 41 of their papers we have counts for
42 papers
Fine-Grained Liquid Democracy for Cumulative Ballots
Matthias Köppe, Martin Koutecký, Krzysztof Sornat +1
We investigate efficient ways for the incorporation of liquid democracy into election settings in which voters submit cumulative ballots, i.e., when each voter is assigned a virtua…
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…
Generating functions and triangulations for lecture hall cones
Matthias Beck, Benjamin Braun, Matthias Köppe +2
We investigate the arithmetic-geometric structure of the lecture hall cone \[ L_n \ := \ \left\{λ\in \mathbb{R}^n: \, 0\leq \frac{λ_1}{1}\leq \frac{λ_2}{2}\leq \frac{λ_3}{3}\leq \c…
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-…
Three Ehrhart Quasi-polynomials
Velleda Baldoni, Nicole Berline, Jesús A. De Loera +2
Let be a semi-rational parametric polytope, where is a real multi-parameter. We study intermediate sums of polynomial functions on ,…
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…
Intermediate Sums on Polyhedra II: Bidegree and Poisson Formula
Velleda Baldoni, Nicole Berline, Jesús A. De Loera +2
We continue our study of intermediate sums over polyhedra, interpolating between integrals and discrete sums, which were introduced by A. Barvinok [Computing the Ehrhart quasi-poly…
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…
Coefficients of Sylvester's Denumerant
Velleda Baldoni, Nicole Berline, Jesús De Loera +3
For a given sequence of positive integers, we consider the combinatorial function that counts the nonnegative integer so…
s-Lecture Hall Partitions, Self-Reciprocal Polynomials, and Gorenstein Cones
Matthias Beck, Benjamin Braun, Matthias Köppe +2
In 1997, Bousquet-Melou and Eriksson initiated the study of lecture hall partitions, a fascinating family of partitions that yield a finite version of Euler's celebrated odd/distin…
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…