New Hierarchies, Cutting Planes, and Algorithms for Mixed Integer Optimization

The primary research objective of this project in computational mathematics is to derive novel polyhedral relaxations for the feasible regions of mixed integer problems (MIPs) through an innovative interpretation of discrete feasible regions arising from ordered sets of integral vectors under some monomial ordering. The research activities involve developing a rich body of knowledge about cutting planes, valid inequalities, and polyhedral relaxations for MIPs, approximation algorithms for MIPs, and using discretization methods to efficiently approximate MIPs with polynomial constraints. Thus, this project will establish new connections between computational algebra, combinatorics, and mathematical optimization. One of our methods for generating cutting planes using a monomial order generalizes and strengthens the cutting planes derived from the well-known split disjunctions. The theory we develop does not depend explicitly on the algebraic representation of the feasible set, therefore making it applicable to all classes of MIP and presenting a very different approach than many of the existing studies that explicitly depend on the linearity of the constraints.