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

被引：142

作者：

Croxton, KL ^{[1
]}

Gendron, B

Magnanti, TL

机构：

[1] Ohio State Univ, Fisher Coll Business, Columbus, OH 43210 USA

[2] Univ Montreal, Ctr Res Transports, Montreal, PQ H3C 3J7, Canada

[3] MIT, Sch Engn, Cambridge, MA 02139 USA

[4] MIT, Alfred P Sloan Sch Management, Cambridge, MA 02139 USA

来源：

MANAGEMENT SCIENCE | 2003年 / 49卷 / 09期

关键词：

piecewise linear; integer programming; linear relaxation; Lagrangian relaxation;

D O I：

10.1287/mnsc.49.9.1268.16570

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

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.

引用

页码：1268 / 1273

页数：6

共 22 条

[1] MODELING PIECEWISE-LINEAR CONCAVE COSTS IN A TREE PARTITIONING PROBLEM
AGHEZZAF, EH
WOLSEY, LA
[J]. DISCRETE APPLIED MATHEMATICS, 1994, 50 (02) : 101 - 109
[2] A COMPOSITE ALGORITHM FOR A CONCAVE-COST NETWORK FLOW PROBLEM
BALAKRISHNAN, A
GRAVES, SC
[J]. NETWORKS, 1989, 19 (02) : 175 - 202
[3] Bienstock D., 1996, INFORMS Journal on Computing, V8, P243, DOI 10.1287/ijoc.8.3.243
[4] CHAN L, 1997, SUPPLY CHAIN MANAGEM
[5] COMINETTI R, 1997, BRANCH BOUND METHOD
[6] Croxton, 1999, THESIS MIT CAMBRIDGE
[7] Models and methods for merge-in-transit operations
Croxton, KL
Gendron, B
Magnanti, TL
[J]. TRANSPORTATION SCIENCE, 2003, 37 (01) : 1 - 22
[8] CROXTON KL, 2002, VARIABLE DISAGGREGAT
[9] CROXTON KL, 2002, COMP MIXED INTEGER P
[10] Dantzig G. B., 1963, LINEAR PROGRAMMING E

← 1 2 3 →