 |
Center for Nonlinear Studies |
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 is the result of a new way to exploit inner function structure when relaxing composite functions. The relaxation is constructed in two steps. First, the inner-function structure is captured as a polytope in a generic fashion. Second, the graph of the outer-function over this polytope is relaxed into a convex set. Although the separation problem for the convex hull of this graph is NP-Hard in general, we show that separation is tractable in several cases. In particular, consider an outer-function, which is supermodular and concave-extendable and let d and n denote respectively the number of inner functions and the number of estimators for each inner-function. For this case, we develop an O(dn log d) algorithm for separating the hypograph of the outer-function over the previously described polytope that captures inner-function structure. We show that tractable separation is also possible when the outer-functions are not supermodular but d is fixed. We argue that the composite relaxations are particularly well-suited for constructing MIP relaxations via discretization strategies and for relaxations of functions with discrete domains. Moreover, composite relaxations can also be used to improve most relaxation hierarchies without introducing additional variables. When the outer-function is convex in each argument, the limiting relaxation obtained with infinitely many estimators for each inner-function is shown to be related to the solution of an optimal transport problem. We conclude with preliminary computational experience with these relaxations.
Host: Harsha Nagarajan