A cutting plane algorithm for the one-dimensional cutting stock problem with multiple stock lengths

被引：86

作者：

Belov, G ^{[1
]}

Scheithauer, G ^{[1
]}

机构：

[1] Dresden Univ Technol, Dept Numer Math, D-01062 Dresden, Germany

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 2002年 / 141卷 / 02期

关键词：

cutting; cutting planes; column generation; heuristics; branch-and-bound;

D O I：

10.1016/S0377-2217(02)00125-X

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

A cutting plane approach combining Chvatal-Gomory cutting planes with column generation is generalized for the case of multiple stock lengths in the one-dimensional cutting stock problem. Appropriate modifications of the column generation procedure and the rounding heuristic are proposed. A comparison with the branch-and-price method for the problem with one stock type and representative test results are reported. (C) 2002 Elsevier Science B.V. All rights reserved.

引用

页码：274 / 294

页数：21

共 20 条

[1]

BELOV G, 2000, THESIS TU DRESDEN

[2]

DEGRAEVE Z, 2000, OPTIMAL INTEGER SO 2

[3]

DYCKHOFF H, 1997, ANNOTATED BIBLIOGRAP, P393

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

GILMORE, PC ;

GOMORY, RE .

OPERATIONS RESEARCH, 1963, 11 (06) :863-888

[5]

KUPKE J, 1998, THESIS U KOLN

[6] AN INSTANCE OF THE CUTTING STOCK PROBLEM FOR WHICH THE ROUNDING PROPERTY DOES NOT HOLD [J].

MARCOTTE, O .

OPERATIONS RESEARCH LETTERS, 1986, 4 (05) :239-243

[7]

Martello S., 1990, KNAPSACK PROBLEMS AL

[8]

Mukhacheva E. A., 2000, PESQUI OPER, V20, P153

[9]

MUKHACHEVA EA, 1981, OPT STOCK CUTT 2 ALL

[10]

Nemhauser GL, 1988, INTEGER COMBINATORIA

← 1 2 →