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

Keely L. Croxton (), Bernard Gendron () and Thomas L. Magnanti ()
Additional contact information
Keely L. Croxton: Fisher College of Business, The Ohio State University, Columbus, Ohio 43210
Bernard Gendron: Département d'informatique, et de recherche opérationnelle, and Centre de recherche sur les transports, Université de Montréal, Montréal, Quebec H3C 3J7, Canada
Thomas L. Magnanti: School of Engineering, and Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts

Management Science, 2003, vol. 49, issue 9, 1268-1273

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 (search for similar items in EconPapers)
Date: 2003
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (45)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.49.9.1268.16570 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:49:y:2003:i:9:p:1268-1273

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().