Mohit Tawarmalani, Purdue University

Abstract

We introduce a new relaxation framework for MINLPs. These new relaxations, called composite relaxations, are tighter than the prevalent factorable programming relaxations, implemented in many state-of-the-art solvers. The tightness arises from a new way to exploit multiple estimators for each inner function at a time. Our relaxation procedure involves two steps. First, the inner function structure is encoded in a polytope. Second, the outer function is relaxed over this polytope. Although the separation problem for the graph of the outer function over the aforementioned polytope is NP-Hard in general, there are several tractable instances, which provide new ways to develop tight relaxations for MINLP. For example, we show that if the outer function is supermodular and concave-extendable, its hypograph can be separated in O(dn log d) where d is the number of inner functions and n is the number of estimators of each inner function. The validity of the derived inequalities can be seen easily using certain telescoping expansions. This derivation allows us to generalize the construction of valid inequalities to cases where the outer-function is not concave extendable. The composite relaxations, we develop, are well-suited for constructing MIP relaxations via discretization strategies and for relaxing functions over discrete domains. Exploiting these results, we develop various discretization strategies. When the outer function is supermodular and the inner functions are univariate, our relaxations yield an ideal MIP formulation for the discrete case. For the continuous case, when the outer function is also Liptschitz continuous, the ideal formulation yields a sequence of relaxations that converge to the concave envelope.  When the outer-function is convex in each argument, the limiting relaxation obtained with infinitely many estimators for each inner-function arises as a solution of an optimal transport problem. We conclude with preliminary computational experience with these relaxations.

Joint work with Taotao He.