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

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.

MoreLess

Year of publication:	2003
Authors:	Croxton, Keely L. ; Gendron, Bernard ; Magnanti, Thomas L.
Published in:	Management Science. - Institute for Operations Research and the Management Sciences - INFORMS, ISSN 0025-1909. - Vol. 49.2003, 9, p. 1268-1273
Publisher:	Institute for Operations Research and the Management Sciences - INFORMS
Subject:	Piecewise Linear \| Integer Programming \| Linear Relaxation \| Lagrangian Relaxation

More details

Extent:	application/pdf
Type of publication:	Article
Other identifiers:	10.1287/mnsc.49.9.1268.16570 [DOI]
Source:	RePEc - Research Papers in Economics

Persistent link: https://www.econbiz.de/10009204473