Comparing Formulations for Piecewise Convex Problems

In this paper we address non-convex Mixed-Integer Non-Linear Programs where the non-convexity is manifested as the sum of non-convex univariate functions. Motivated by the Sequential Convex Mixed Integer Non Linear Programming technique, we compare the three classical different formulations for piecewise problems: the incremental model, the multiple choice model, and the convex combination model. For piecewise-linear functions, these models are known to be equivalent. We show that this is not the case for piecewise-convex functions, where one of the three formulations is weaker than the other two. Computational results on a target application illustrate the practical impact of this property.