Computational results with a primal-dual subproblem simplex method

被引：20

作者：

Hu, J ^{[1
]}

Johnson, EL ^{[1
]}

机构：

[1] Georgia Inst Technol, Sch Ind & Syst Engn, Atlanta, GA 30332 USA

来源：

OPERATIONS RESEARCH LETTERS | 1999年 / 25卷 / 04期

关键词：

linear programming algorithm; simplex;

D O I：

10.1016/S0167-6377(99)00048-6

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

The two main ideas implemented are a primal-dual subproblem simplex method and a compact matrix storage scheme to speed up linear programming solution times. Two classes of problems are solved: crew-pairing optimization and cutting stock. The matrix storage schemes are different for these two problem classes, and the one for cutting stock is a hybrid using dynamic programming ideas. (C) 1999 Elsevier Science B.V. All rights reserved.

引用

页码：149 / 157

页数：9

共 11 条

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

ANBIL, R ;

TANGA, R ;

JOHNSON, EL .

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

[2]

[Anonymous], THESIS GEORGIA I TEC

[3] Branch-and-price: Column generation for solving huge integer programs [J].

Barnhart, C ;

Johnson, EL ;

Nemhauser, GL ;

Savelsbergh, MWP ;

Vance, PH .

OPERATIONS RESEARCH, 1998, 46 (03) :316-329

[4] VERY LARGE-SCALE LINEAR-PROGRAMMING - A CASE-STUDY IN COMBINING INTERIOR POINT AND SIMPLEX METHODS [J].

BIXBY, RE ;

GREGORY, JW ;

LUSTIG, IJ ;

MARSTEN, RE ;

SHANNO, DF .

OPERATIONS RESEARCH, 1992, 40 (05) :885-897

[5] Solving large scale crew scheduling problems [J].

Chu, HD ;

Gelman, E ;

Johnson, EL .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1997, 97 (02) :260-268

[6]

Dantzig G. B., 1963, LINEAR PROGRAMMING E

[7] A LINEAR-PROGRAMMING APPROACH TO THE CUTTING-STOCK PROBLEM [J].

GILMORE, PC ;

GOMORY, RE .

OPERATIONS RESEARCH, 1961, 9 (06) :849-859

[8]

HU J, 1996, THESIS GEORGIA I TEC

[9] THE PIVOT AND PROBE ALGORITHM FOR SOLVING A LINEAR PROGRAM [J].

SETHI, AP ;

THOMPSON, GL .

MATHEMATICAL PROGRAMMING, 1984, 29 (02) :219-233

[10]

Vance P. H., 1994, Computational Optimization and Applications, V3, P111, DOI 10.1007/BF01300970

← 1 2 →