A branch-and-price algorithm for solving the cutting strips problem

被引：0

作者：

Zhiping C. ^{[1
]}

Hurkens C.A.J. ^{[2
]}

De Jono J.L. ^{[3
]}

机构：

[1] Departmeat of Mathematics, Xi'an Jiaotong University, Xi'an

[2] Depantmeat of Mathematics and Computing Sciences, Eindhoven University of Technology

[3] Department of Mathematics and Computing Sciences, Eindhoven University of Technology

来源：

Applied Mathematics-A Journal of Chinese Universities | 1997年 / 12卷 / 2期

关键词：

Branch-and-bound; Column generation; Cutting strips problem;

D O I：

10.1007/s11766-997-0022-y

中图分类号：

学科分类号：

摘要：

After giving a suitable model for the cutting strips problem, we present a branch-andprice algorithm for it by combining the column generation technique and the branch-and-bound method with LP relaxations. Some theoretical issues and implementation details about the algorithm are discussed, including the solution of the pricing subproblem, the quality of LP relaxations, the branching scheme as well as the column management. Finally, preliminary computational experience is reported. © 1997, Appl. Math. J. Chinese Univ. Ser. B. All rights reserved.

引用

页码：215 / 224

页数：9

共 10 条

[1]

Barnhart C., Branch-and-price: Column generation for solving huge integer programs, Report COC-94-03, School of Industrial and Systems Engineering, Georgia Institute of Technolog, (1994)

[2]

Forrest J., Practical solution of large mixed integer programming problems with UMPIRE, Management Scienc, 20, pp. 736-773, (1974)

[3]

Geoffrion A.M., Lagrangian relaxation for integer programming, Math. Programming Stud, 2, pp. 82-114, (1974)

[4]

Gilmore P.C., Gomory R.E., A linear programming approach to the cutting-stock problem, Oper. Re, 9, pp. 849-859, (1961)

[5]

Gilmore P.C., Gomory R.E., Multistage cutting stock problems of two and more dimensions, Oper. Re, 13, pp. 94-120, (1964)

[6]

Martello S., Toth P., Knapsack Problems: Algorithms and Computer Implementation, (1990)

[7]

Nemhauser G.L., Wolsey L.A., Integer and Combinatorial Optimizatio, (1988)

[8]

Savelsbergh M.W.P., Nemhauser G.L., Functional Description of MINTO, a Mixed Integer Optimize, (1993)

[9]

Sol M., Column Generation Techniques for Pickup and Delivery Problem, (1994)

[10]

Vance P.H., Et al., Solving binary cutting stock problems by column generation and branch-and bound, Computational Optimization and Application, 3, pp. 111-130, (1994)

← 1 →