Some of my papers in ALGEBRAIC OPTIMIZATION

  • The paper Pareto Optima of Multicriteria Int eger Linear Programs proves a generalization of Lenstra's theorem for integer programming in fixed dimension. In this case, a multiobjective integer linear optimization problem with fixed number of variables and a fixed number of objective functions can be solved in polynomial time.

  • The paper Integer polynomial optimization in fixed dimension settles the computational complexity of this kind of integer programs and then gives an FPTAS for the problem of finding approximations to the maximization of a polynomial over the lattice points of a polyhedron. Appeared in Mathematics of Operations Research

  • Also accepted in Mathematical Programming is our follow up paper on the the mixed-integer case for the same problem above.

  • Test sets are important tools in Algebraic Optimization. Recently we wrote two papers on a nice situation when the computation of Graver bases can be efficiently done and optimization can also be carried on efficiently: First, to appear in the journal Discrete Optimization is a prove that n-fold integer linear programs can be solved efficiently. There is a follow-up paper to appear in the Journal of Pure and Applied Algebra where we deal with convex objective maximization problems n-fold convex maximization

  • The paper All Linear and Integer Programs are Slim 3-way Transportation Programs (joint with S. Onn) presents a polynomial time algorithm that encodes ANY convex rationalpolyhedron as a 3-way transportation polytope. This means that3-way transportation polytopes are as nasty as any general polytope.This has consequences in Discrete Optimization and Statistics. The software implementing this algorithm is available here too. This paper appeared in SIAM journal of Optimization

    Some of my papers in COMBINATORICS

  • The paper Ehrhart polynomials of matroids and polymatroids (joint with D. Haws and M. Koeppe) shows a curious family of polytopes whose dimension grows yet we can efficiently compute their Ehrhart polynomials (we dont know many of them).

  • The paper On the computation of Clebsch-Gordan coefficients and the dilation effect (joint with T.B. McAllister) we investigate the problem of computing tensor product multiplicities for complex semisimple Lie algebras. Remarkable new conjectures generalizing the saturation theorem are proposed (the dilation effect). Download software from Tyrrell's web page.

  • The paper The many aspects of counting lattice points in polytopes is a survey of the applications, theory and algorithms for the problem in the title.

  • The paper All Linear and Integer Programs are Slim 3-way Transportation Programs (joint with S. Onn) presents a polynomial time algorithm that encodes ANY convex rational polyhedron as a 3-way transportation polytope. This means that 3-way transportation polytopes are as nasty as any general polytope. This has consequences in Discrete Optimization and Statistics. The software implementing this algorithm is available here too.

  • The paper Effective Lattice Point Counting in Rational Convex Polytopes (joint with R. Hemmecke, J. Tauzer and R. Yoshida) presents the software LATTE the first full implementation of Barvinok's algorithm. The paper discusses our tricks to implement it, a ``polar'' variation that runs faster in practice, and presents LOTS of concrete calculations and applications (e.g explicit Ehrhart quasipolynomials). For more information on LattE, please see LattE's home page

  • Here is an example, in MAPLE, of our formula for the volume of the Birkhoff polytope $B_3$.

  • The paper Algebraic Unimodular Counting (joint with B. Sturmfels) This is the great-grand father of the LATTE project. The paper presents several computational results regarding counting unimodular vector partition functions, in particular the problem of counting Contingency tables and Kostant's partition function of the root system An. You can also play online with Kostant's partition function and download software for counting contingency table here

    Some software

  • Here is a link to our popular software LattE for counting integer lattice points in convex polytopes and computing Ehrhart polynomials.

  • The program PUNTOS allows you to compute regular triangulations of point sets. It also has useful subroutines for checking regularity and computing the GKZ coordinates of the secondary polytope. BUT you should REALLY use TOPCOM instead!

  • The program universalbuilder, written together with Samuel Peterson, is a C++ program that generates CPLEX readable integer programs to compute minimal and maximal triangulations of convex polytopes of arbitrary dimension. It can also compute chirotopes of point configurations.