The volume algorithm: producing primal solutions with a subgradient method

被引：165

作者：

Barahona, F ^{[1
]}

Anbil, R ^{[1
]}

机构：

[1] IBM Corp, Thomas J Watson Res Ctr, Yorktown Heights, NY 10598 USA

来源：

MATHEMATICAL PROGRAMMING | 2000年 / 87卷 / 03期

关键词：

subgradient algorithm; Dantzig-Wolfe decomposition; large scale linear programming;

D O I：

10.1007/s101070050002

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We present an extension to the subgradient algorithm to produce primal as well as dual solutions. It can he seen as a fast way to carry out an approximation of Dantzig-Wolfe decomposition. This gives a Fast method for producing approximations for large scale linear programs. It is based on a new theorem in linear programming duality. We present successful experience with linear programs coming from set partitioning, set covering, max-cut and plant location.

引用

页码：385 / 399

页数：15

共 29 条

[1] A GLOBAL APPROACH TO CREW-PAIRING OPTIMIZATION [J].

ANBIL, R ;

TANGA, R ;

JOHNSON, EL .

IBM SYSTEMS JOURNAL, 1992, 31 (01) :71-78

[2]

ANSTREICHER KM, 1993, DUAL SOLUTIONS SUBGR

[3]

BAKER BM, 1996, ACCELERATING CONVERG

[4]

BALAS E, 1980, MATH PROGRAM STUD, V12, P37, DOI 10.1007/BFb0120886

[5] ON THE CUT POLYTOPE [J].

BARAHONA, F ;

MAHJOUB, AR .

MATHEMATICAL PROGRAMMING, 1986, 36 (02) :157-173

[6] Plant location with minimum inventory [J].

Barahona, F ;

Jensen, D .

MATHEMATICAL PROGRAMMING, 1998, 83 (01) :101-111

[7] A generalized subgradient method with relaxation step [J].

Brannlund, U .

MATHEMATICAL PROGRAMMING, 1995, 71 (02) :207-219

[8]

Camerini P. M., 1975, MATH PROGRAMMING STU, V3, P26

[9]

CAPRARA A, 1995, OR958 U BOL

[10]

CERIA S, 1995, 406 IASICNR

← 1 2 3 →