Tri-Dung Nguyen
University of Southampton

Wednesday, May 16 at 2:30 PM

Abstract

Algebraic geometry has recently been emerged as an alternative approach for solving integer (non)-linear programs by studying the algebraic structure of the underlying lattice and generating sets. Although algebraic geometry is, in general, still not as competitive as mainstream IP solvers such as CPLEX, there are certain classes of problems where using algebraic geometry is more effective. This includes the problem of finding the Shapley value of a class of integer maximization games where an exponentially large number of IPs must be solved. A major obstacle in using algebraic geometry for integer programming is the computational bottleneck of finding the Groebner and the Graver bases. In the second part, we present a recent progress in refining the project-and-lift method, which is the current state-of-the-art algorithm for finding the Graver basis, such that the algebraic geometry method can handle larger IPs.

Categories: Seminar