A Comparison of Mixed-Integer Programming Models for Nonconvex Piecewise Linear Cost Minimization Problems

Keely L. Croxton, Bernard Gendron, Thomas L. Magnanti

Management Science · 2003 · Volume 49 · Issue 9

Abstract

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.

Keywords

Piecewise Linear, Integer Programming, Linear Relaxation, Lagrangian Relaxation

Enable JavaScript for citation tools and additional paper interactions.