Professor, Mathematics —
Member, Applied
Mathematics (Graduate Group)
Member, Optimization group —
Faculty
Affiliate, DataLab
—
Member, Computer Science (Graduate Group)
News & Events —
Research —
Publications —
Math Software —
Teaching —
Other —
Contact
Events
On sabbatical 2019–2020. Follow me on Twitter (mkoeppe_math) for updates.
Past talks and events
News
 June 2019:
An improved
SageMath interface
to polymake is
available in SageMath,
version 8.8,
using JuPyMake instead of pseudoterminal (pexpect) interactions.
It can be used directly or via the backend
for polyhedral computations using polymake.
 June 2019:
The final paper of our series
on Intermediate Sums on Polyhedra (with V. Baldoni,
N. Berline, J.A. De Loera,
M. Vergne)
has just appeared in the new open access
journal Algebraic Combinatorics.
Part III: Three Ehrhart quasipolynomials
concludes the series by giving an algorithmic approximation theory for
real multiparameter Ehrhart quasipolynomials.
It builds upon Part 0: Computation of the highest
coefficients of weighted Ehrhart quasipolynomials ...,
Part I: Computation and
real Ehrhart theory, and Part
II: Bidegree and Poisson formula.
 May 2019: IPCO
2019, the 20th Conference on
Integer Programming and Combinatorial Optimization, Ann Arbor,
Michigan. Accepted paper: On perturbation spaces of minimal
valid functions: Inverse semigroup theory and equivariant
decomposition theorem (with Robert Hildebrand, Yuan Zhou).
Full paper (arXiv, 61 pages).
More about the infinite
group problem
 June 2017: IPCO
2017, the 19th Conference on
Integer Programming and Combinatorial Optimization,
June 26–28, 2017, Waterloo, Canada.
Accepted
paper: On the
notions of facets, weak facets, and extreme functions of the
Gomory–Johnson infinite group problem (with Yuan
Zhou)
 March
2017: The
lives of mathematics,
by Francesc
Serés, describes his impressions
of Sage Days 84:
Polytopes in Sage, February 27–March 12, 2017, at the
Faber Residency in Olot,
Catalunya, Spain.
 March 2017: SageMath,
version 7.6, now has
a polyhedral
computation backend based on Normaliz, making the outstanding
performance of Normaliz for polyhedral computation in medium to
high dimensions available to SageMath users.
 January 2017: Normaliz
version 3.2.0, developed by Winfried Bruns et al. at Osnabrück, has a new
autotools build system contributed by me.
 November 2016: Our paper New
computerbased search strategies for extreme functions of the
Gomory–Johnson infinite group problem (with Yuan
Zhou; version 3) has appeared in
Math. Programming Computation.

May 2016: New paper: Toward
computerassisted discovery and automated proofs of
cutting plane theorems (with Yuan Zhou),
presented at ISCO
2016.
 New undergraduate major at UC Davis (from
2014/15): B.S. in
Mathematical Analytics and Operations Research.
Research
My research interests are mathematical optimization
(integer programming) and
computational discrete mathematics.
 Selected funded projects
 Workgroup at UC Davis:
 Jiawei Wang (Ph.D. candidate)
 Alumni of the workgroup:
 Amitabh Basu
(Krener
Assist. Prof. 2010–2013; faculty at Johns Hopkins
University, Dept. of Applied Mathematics and Statistics, 2013–)
 Robert
Hildebrand (Ph.D. 2013; postdoc at ETH Zürich 2013–2015;
Goldstine
Fellow at IBM Research 2015–2017; Simons Institute
Fellow 2017; tenuretrack faculty at Virginia Tech, 2018–)
 Brandon Dutra (Ph.D. 2016; coadvised with J. De Loera;
now software engineer at Google)
 Yuan Zhou
(Ph.D. 2017; tenuretrack faculty at U. Kentucky, Mathematics 2017–)
 Chun Yu Hong (undergraduate researcher 2013; now Ph.D. student
at UC Berkeley)
 Peijun Xiao (undergraduate researcher 2015–2017)
 Yao Shuidie (undergraduate researcher 2016–2017)
 Other collaborators at UC Davis:

Selected Publications, Theses and
Preprints (see also
my Google
Scholar profile
and arXiv)
... on multirow cuts, cutgenerating functions,
Gomory–Johnson's infinite group relaxation:
 The triangle closure
is a polyhedron (with A. Basu, R. Hildebrand,
2011)
 A (k+1)slope theorem
for the kdimensional infinite group relaxation (with
A. Basu, R. Hildebrand, M. Molinaro, 2011)
 Equivariant
perturbation in Gomory and Johnson's infinite group
problem. Part I,
Part II,
Part
III (with A. Basu, R. Hildebrand,
2012–2014); Part
V (with C. Y. Hong and Y. Zhou, 2016);
Part
VI (with Y. Zhou,
2016); Part VII
(with R. Hildebrand, Y. Zhou, 2018)
 Light
on the infinite group relaxation (survey, with A. Basu and
R. Hildebrand, 2014)
 An
electronic compendium of extreme functions for the
Gomory–Johnson infinite group problem
(with Y. Zhou, 2014)
 New
computerbased search strategies for extreme functions of the
Gomory–Johnson infinite group problem (with
Y. Zhou, 2015)
... on primal integer programming:
... on mixedinteger nonlinear optimization:
... on game theory and bilevel optimization:
... on effective generating function methods, integration, and summation:
 A primal Barvinok algorithm
based on irrational decompositions (2006)
 Computing
parametric rational generating functions with a primal Barvinok
algorithm (with S. Verdoolaege, 2008)
 An
implementation of the BarvinokWoods integer projection
algorithm (with S. Verdoolaege,
K. M. Woods, 2008)
 How to integrate
a polynomial over a simplex (with
V. Baldoni, N. Berline, J. A. De Loera,
M. Vergne, 2008)

Intermediate sums on
polyhedra: Computation and real Ehrhart theory (with
V. Baldoni, N. Berline, M. Vergne, 2010)
 Three Ehrhart
quasipolynomials (with
V. Baldoni, N. Berline, J. A. De Loera, M. Vergne, 2014)
... on enumerative combinatorics and number theory:
 Ehrhart polynomials of
matroid polytopes and polymatroids (with
J. A. De Loera and D. C. Haws, 2007)
 slecture hall
partitions, selfreciprocal polynomials, and Gorenstein
cones (with M. Beck, B. Braun, C. Savage,
Z. Zafeirakopoulos, 2012)
 Coefficients
of Sylvester's denumerant (with
V. Baldoni, N. Berline, J. A. De Loera, M. Vergne, 2013)
 Generating functions
and triangulations for lecture hall cones (with M. Beck, B. Braun, C. Savage,
Z. Zafeirakopoulos, 2015)
... a textbook and research monograph:
... more...
 Selected Mathematical
Software and Data
(see also GitHub)
 GYWOPT, an interactive
system for exploring primal reformulations of integer linear
programs, containing an implementation of the Integral Basis
Method (with U.U. Haus, 2000–2005)
 LattE integrale,
the successor to LattE and LattE macchiato (with V. Baldoni,
N. Berline,
J. De Loera, B. Dutra, M. Vergne and several
contributing students, 2006–)
This software counts lattice points in rational polyhedra
using stateoftheart variants of Barvinok's algorithm,
computes Ehrhart polynomials, volumes of polytopes and integrals
of polynomial functions over polytopes, and computes the highest coefficients of
weighted Ehrhart quasipolynomials.
 4ti2, a software package for
algebraic, geometric and combinatorial problems on linear spaces
(with R. Hemmecke, R. Hemmecke, P. Malkin,
M. Walter, 2008–)
This software implements stateoftheart algorithms for the computation of
Graver bases, Hilbert bases, extreme rays of cones, toric Gröbner bases, Markov
bases, and more.

cutgeneratingfunctionology:
SageMath
program for computation and experimentation with the
1row Gomory–Johnson infinite group problem and beyond (with
C. Y. Hong, Y. Zhou, J. Wang, 2013–)
This software implements an automated extremality test for
piecewise linear functions (which are allowed to be discontinuous)
and contains an electronic compendium of extreme functions.
 Since 2015, I have
made various
contributions
to the SageMath system: In
particular, see this metaticket
on Improvements to
the SageMath mixed integer linear programming interface (#20302).
My current project is to improve SageMath's build system
(#21566,
#21507).
Teaching

Watch my lectures (from
the 2010 MSRI summer
school "Algebraic, Geometric, and Combinatorial Methods for
Optimization") on tools from the geometry of numbers, with a
focus on rational generating function techniques for integer
programming. So in these lectures I introduce lattices, the LLL algorithm, Lenstra's
algorithm for integer programming in fixed dimension, Barvinok's
theory of short rational generating functions, and the summation
method for polynomial integer programming: Lectures 1,
2, 3, 4, 5, 6
and 7
 Recent graduate courses:
 Current/recent upperdivision undergraduate courses:
 more...
Etc.
Contact
 By email:
 Business address, office and phone number:
University of California, Davis
Department of Mathematics
One Shields Avenue
Davis, CA 95616
USA
Office: MSB 3143
Phone: none
Skype: mkoeppe.ucdavis
 Office hours for my current
classes: See
department page
 If you want to set up an appointment with me, you
might find my Availability
Calendar useful.