Mixed-integer nonlinear programs are typically solved using branch-and-bound
algorithms. A key determinant of the success of such methods is their ability to construct tight and tractable relaxations. The predominant relaxation strategy used by
most state-of-the-art solvers is the factorable programming technique. This technique
recursively traverses the expression tree for each nonlinear function and relaxes each
operator over a bounding box that covers the ranges for all the operands. While
it is versatile, and allows finer control over the number of introduced variables, the
factorable programming technique often leads to weak relaxations because it ignores
operand structure while constructing the relaxation for the operator.<div>In this thesis, we introduce new relaxations, called composite relaxations, for
composite functions by convexifying the outer-function over a polytope, which models an ordering structure of outer-approximators of inner functions. We devise a fast
combinatorial algorithm to separate the hypograph of concave-extendable supermodular outer-functions over the polytope, although the separation problem is NP-Hard
in general. As a consequence, we obtain large classes of inequalities that tighten
prevalent factorable programming relaxations. The limiting composite relaxation obtained with infinitely many outer-approximators for each inner-function is shown to
be related to the solution of an optimal transport problem. Moreover, composite relaxations can be seamlessly embedded into a discretization scheme to relax nonlinear
programs with mixed-integer linear programs. Combined with linearization, composite relaxations provide a framework for deriving cutting planes used in relaxation
hierarchies and more.<br></div>
| Identifer | oai:union.ndltd.org:purdue.edu/oai:figshare.com:article/9118661 |
| Date | 13 August 2019 |
| Creators | Taotao He (7047464) |
| Source Sets | Purdue University |
| Detected Language | English |
| Type | Text, Thesis |
| Rights | CC BY 4.0 |
| Relation | https://figshare.com/articles/New_relaxations_for_composite_functions/9118661 |
Page generated in 0.0021 seconds