Solving mixed-integer nonlinear problems by means of piecewise linear relaxations has emerged as a reasonable alternative to the commonly used spatial branch-and-bound. These relaxations have been modeled by various mixed-integer models in recent decades. The idea is to exploit the availability of mature solvers for mixed-integer problems.
In this work, we implement a framework that reformulates mixed-integer nonlinear problems to eight commonly used different mixed-integer representations for piecewise linear relaxations where the reformulations can be compared in terms of behavior and runtime to determine which method to apply in practice. We use expression trees to reformulate all nonlinearities to one-dimensional functions and then compute a set of interpolation breakpoints for each function based on a given maximum error. This framework is made publicly available, see https://github.com/kristinbraun/pwl-t-rex.
Further, we conduct an analysis on a benchmark set created from the MINLPLib consisting of over 750 instances.It includes a comprehensive comparison of the number of problems solved, runtimes, and optimality gaps.
Article