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

被引：143

作者：

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 [J].

AGHEZZAF, EH ;

WOLSEY, LA .

DISCRETE APPLIED MATHEMATICS, 1994, 50 (02) :101-109

[2] A COMPOSITE ALGORITHM FOR A CONCAVE-COST NETWORK FLOW PROBLEM [J].

BALAKRISHNAN, A ;

GRAVES, SC .

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 [J].

Croxton, KL ;

Gendron, B ;

Magnanti, TL .

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 →