A comparison of mixed-integer programming models for nonconvex piecewise linear cost minimization problems

• 成果类型: Article
• 署名作者: Croxton, KL; Gendron, B; Magnanti, TL
• 署名单位: University System of Ohio; Ohio State University; Universite de Montreal; Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
• 刊物名称: MANAGEMENT SCIENCE
• ISSN/ISSBN: 0025-1909
• DOI: 10.1287/mnsc.49.9.1268.16570
• 发表日期: 2003
• 页码: 1268-1273
• 关键词: piecewise linear; integer programming; linear relaxation; Lagrangian relaxation

摘要

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.