|
|||||
|
|
| A BRANCH-AND-PRICE ALGORITHM FOR SOLVING THE CUTTING STRIPS PROBLEM | |
| 引用本文： | CHENZHIPING C.A.J.HURKENS J.L.DEJONG. A BRANCH-AND-PRICE ALGORITHM FOR SOLVING THE CUTTING STRIPS PROBLEM[J]. 高校应用数学学报(英文版), 1997, 12(2): 215-224. DOI: 10.1007/s11766-997-0022-y |
| 作者姓名： | CHENZHIPING C.A.J.HURKENS J.L.DEJONG |
| 作者单位： | [1]DepantmeatofMathematicsandComputingSciences,EindhovenUniversityofTechnology,TheNertherlands. [2]DepartmentofMathematicsandComputingSciences,EindhovenUniversityofTechnology,TheNertherlands. [3]DepartmeatofMathematics,Xi＇anJiaotongUniversity,Xi＇an710049. |
| 摘 要： | After giving a suitable model for the cutting strips problem, we present a branch-and-price algorithm for it by combining the column generation technique and the branch-and-hound 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 computarional experience is reported. |
| 关 键 词： | 巴拿赫价格法则 切割带 LP松弛 定价问题 |
| 收稿时间： | 1995-10-04 |
A branch-and-price algorithm for solving the cutting strips problem |
|
| Chen Zhiping,C. A. J. Hurkens,J. L. de Jong. A branch-and-price algorithm for solving the cutting strips problem[J]. Applied Mathematics A Journal of Chinese Universities, 1997, 12(2): 215-224. DOI: 10.1007/s11766-997-0022-y | |
| Authors: | Chen Zhiping C. A. J. Hurkens J. L. de Jong |
| Affiliation: | (1) Departmeat of Mathematics, Xi′an Jiaotong University, 710049 Xi′an;(2) Depantmeat of Mathematics and Computing Sciences, Eindhoven University of Technology, The Nertherlands;(3) Department of Mathematics and Computing Sciences, Eindhoven University of Technology, The Nertherlands |
| Abstract: | After giving a suitable model for the cutting strips problem, we present a branch-and-price 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. |
| Keywords: | Cutting strips problem column generation branch-and-bound |
| 本文献已被 CNKI 维普 SpringerLink 等数据库收录！ | |