Article ID: | iaor20073406 |
Country: | United States |
Volume: | 49 |
Issue: | 9 |
Start Page Number: | 1268 |
End Page Number: | 1273 |
Publication Date: | Sep 2003 |
Journal: | Management Science |
Authors: | Magnanti Thomas L., Gendron Bernard, Croxton Keely L. |
Keywords: | lagrange multipliers |
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.