Title: Relaxing MINLPs with discrete product terms
Speaker: Akshay Gupte, Clemson University
Time: Monday, December 29, 2014, 10:30 a.m.
Venue: LC 201, Lecture Hall Complex
Abstract: We address the problem of deriving strong polyhedral relaxations of MINLPs having upper bounded product terms between continuous variables and nonlinear functions of 0/1 variables. This structure is motivated by discretization of bilinear MINLPs. The nonlinear function is assumed to vanish at some vertices of the [0,1] hypercube and, for example, can be a composite convex function. We disaggregate the product terms and study the convex hull of the level set of a single product term. A direct relationship is obtained between this level set and a specific supermodular function. Polymatroidal inequalities for this supermodular function and the use of disjunctive programming techniques leads to an exponential number of valid inequalities, which we prove define the convex hull of our level set when the upper bounds on the continuous variable in the product term are "large enough". Interestingly, these facets can be understood as specific tiltings of polymatroids. We also show how to strengthen these disjunctive polymatroidal inequalities when the product terms have additional special structure. This is joint work with Shabbir Ahmed and Santanu Dey.
Bio: Akshay Gupte is an Assistant Professor in the Department of Mathematical Sciences at Clemson University. He obtained his Ph.D. degree in Operations Research from Georgia Institute of Technology. Akshay's main research interests are in the area of discrete optimization with particular emphasis on theory and algorithms for mixed integer nonlinear problems (MINLPs). His secondary interest is in studying the polyhedral structure of special knapsack systems. He also has fringe interests in decomposition methods for optimizing highly nonlinear problems arising in the design of complex integrated systems. Applications of his research can be found in discrete mathematics, chemical engineering, mechanical engineering.