This is a research project in Computational Mathematics. Our goal is to use new algebraic ideas for the development of algorithms to solve discrete optimization problems. Discrete optimization is the study of optimization problems in which there are a finite (but usually very large) number of potential solutions. These are not enumerated but rather defined implicitly by equation or inequality constraints, e.g., linear or nonlinear relations. We focus in non-linear integer programs with polynomial constraints which are notoriously difficult and we explore several non-traditional tools for solving them, including multivariate rational functions and complex analysis, polynomial Hilbert's Nullstellensatz certificates, and new canonical reformulations for integer linear programs. We are also interested on closely related problems in computational convexity. Including the computation of polyhedra related to optimization, the practical approximation of regions by unions of polyhedra and the solution of geometric problems using convex programming methods.
Software and algorithms for solving discrete optimization problems has potential applications to many fields of huge practical importance, such as data mining, finances and economics, transport scheduling (e.g. crew scheduling problems), and circuit design. Examples of discrete optimization problems include the minimum spanning tree problem of selecting the least expensive network connecting given sites or the traveling salesman problem (TSP) consists of selecting the least expensive tour of a given set of locations. Since most discrete optimization problems are useful but very difficult to solve, researchers have explored special structures to be able to solve them in practice (e.g., in the case of the TSP) or settle for algorithms that compute near-optimal solutions. In our project we try non-traditional tools based on recent mathematical progress as a way to approach these very difficult problems. We also have a strong educational component for this project. Several graduate and undergraduate students will all play important roles in the project's development.
