Professor, Mathematics
Faculty Member, Applied
Mathematics, Mathematics, Computer Science (graduate programs/groups)
Faculty Member, UC Davis TETRAPODS Institute of Data Science (UCD4IDS)
Faculty Affiliate, UC Davis Center for Data Science and Artificial Intelligence Research (CeDAR)
Faculty Affiliate, UC Davis DataLab
News & Events —
Research —
Publications —
Math Software —
Teaching —
Other —
Contact
News and Events
- Follow me on The Platform Formerly Known As Twitter (@mkoeppe_math) for updates.
- I am a core developer of SageMath. For recent developments, see the SageMath release tours for versions 9.x and 10.x, the materials from the Global Virtual SageDays 112.358, held in June 2022, and my YouTube channel.
- July 2024: International Congress on Mathematical Software 2024, Durham, UK.
- September 2022: Our paper Equivariant perturbation in Gomory and Johnson’s infinite group problem. VII. Inverse semigroup theory, closures, decomposition of perturbations (with R. Hildebrand, Y. Zhou) has appeared in the new open access journal Open Journal of Mathematical Optimization (CC BY 4.0). More about the infinite
group problem
- June 2022:
I received the 2015–2021 SageMath prize
(jointly with E.M. Bray, F. Chapoton, T. Monteil, A. Novoseltsev, D. Pasechnik, V. Pons, H. Schilly, T. Scrimshaw, N.M. Thiéry).
- 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 quasi-polynomials
concludes the series by giving an algorithmic approximation theory for
real multi-parameter Ehrhart quasi-polynomials.
It builds upon Part 0: Computation of the highest
coefficients of weighted Ehrhart quasi-polynomials ...,
Part I: Computation and
real Ehrhart theory, and Part
II: Bidegree and Poisson formula.
- 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.
- Past talks and events
Research
My work is in mathematical optimization
(integer programming),
computational discrete mathematics, and mathematical software.
Selected funded projects
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; tenure-track faculty at Virginia Tech, 2018–)
- Brandon Dutra
(Ph.D. 2016, co-advised with J. De Loera;
software engineer at Google, 2016–)
- Yuan Zhou
(Ph.D. 2017; tenure-track faculty at U. Kentucky, Mathematics 2017–)
- Jiawei Wang (Ph.D. 2020; data scientist at Uber, 2020–)
- Chun Yu (Johnny) Hong (undergraduate researcher 2013; Ph.D. 2020, UC Berkeley, Statistics; data scientist at Google, 2020–)
- Peijun Xiao (undergraduate researcher 2015–2017)
- Yao Shuidie (undergraduate researcher 2016–2017)
Other collaborators at UC Davis
Publications
... on multi-row cuts, cut-generating 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 k-dimensional 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
computer-based search strategies for extreme functions of the
Gomory–Johnson infinite group problem (with
Y. Zhou, 2015)
... on primal integer programming:
... on mixed-integer 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 Barvinok-Woods 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
quasi-polynomials (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)
- s-lecture hall
partitions, self-reciprocal 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... (see also
my Google
Scholar profile
and arXiv)
- 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 state-of-the-art 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 quasi-polynomials.
- 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 state-of-the-art 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
1-row 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 SageMath, an open source mathematical system based on Python, originally written by W. Stein in 2005 and developed by a large community of developers.
In terms of authored commits, I am the #1 contributor for the period 2016–now.
-
more... (see also GitHub @mkoeppe)
Teaching
- Math 180: Computer Proofs (Video lectures from Winter 2022: Open Educational Resources, CC BY-SA 3.0). This upper-division course introduces logic modeling with Z3, quantifier elimination in theories of linear systems over reals and integers, and sum-of-squares techniques.
- Math 258B: Discrete Optimization (Video lectures from Fall 2021: Open Educational Resources, CC BY-SA 3.0). This Ph.D.-level course starts with a review of linear programming and polyhedral geometry and develops several classic and modern techniques of integer and mixed-integer linear programming.
- Math 168: Optimization (Video lectures from Fall 2020: Open Educational Resources, CC BY-SA 3.0). This upper-division course in optimization follows the approach of the textbook by Robert J. Vanderbei, Linear programming, foundations and extensions regarding LP theory and the notation for the simplex method. It is complemented by an introduction to integer programming modeling techniques.
-
Math 133: Mathematical Finance (Video lectures from Spring 2021: Open Educational Resources, CC BY-SA 3.0).
The course follows the textbook by Capiński and Zastawniak, Mathematics for Finance, An Introduction to Financial Engineering. The approach of the textbook is complemented by a review of probability and stochastic processes from a measure-theoretic viewpoint; and by computational explorations using the AMPL system.
-
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
- Other graduate courses:
- Other upper-division undergraduate courses:
- New undergraduate major at UC Davis (since
2014/15): B.S. in
Mathematical Analytics and Operations Research.
- more...
Etc.
Contact
- By email only:
- Business address, office and phone number:
University of California, Davis
Department of Mathematics
One Shields Avenue
Davis, CA 95616
USA
- 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.
