A Comparison of Mixed-Integer Programming Models for Nonconvex Piecewise Linear Cost Minimization Problems - Croxton, Keely L.; Gendron, Bernard; Magnanti, Thomas L. (Management Science, 2003)
We study a generic minimization problem with separable nonconvex piecewise linear costs, showing that the linear programming (LP) relaxation of three textbook mixed-integer programming formulations each approximates the cost function by its lower convex envelope. We also show a relationship between this result and classical Lagrangian duality theory.