Solving mixed-integer nonlinear problems by means of piecewise linear relaxations can be 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 compare different reformulations in terms of behavior and runtime to determine which method to apply in practice. To this end, we implement eight different mixed-integer representations for piecewise linear relaxations and evaluate them on a benchmark set from the MINLPLib consisting of over 300 instances. We utilize existing expression trees to reformulate all nonlinearities to one-dimensional functions and afterwards compute a set of interpolation breakpoints for each function based on a given maximum error per segment. Our analysis includes a comprehensive comparison of the number of problems solved, runtimes, and optimality gaps. Overall, the classical incremental method Markowitz and Manne 1957 has the best performance, leading to a general recommendation of this method for solving nonlinear problems by piecewise linear relaxations.
Article
View A Computational Study for Piecewise Linear Relaxations of Mixed-Integer Nonlinear Programs