An Inexact Bundle Approach to Cutting-Stock Problems

被引：6
作者：
Kiwiel, Krzysztof C. [1 ]
机构：
[1] Polish Acad Sci, Syst Res Inst, PL-01447 Warsaw, Poland
来源：
INFORMS JOURNAL ON COMPUTING | 2010年 / 22卷 / 01期
关键词：
nondifferentiable convex optimization; Lagrangian relaxation; integer programming; bundle methods; knapsack problems; cutting stock; LINEAR-PROGRAMMING APPROACH; OPTIMAL INTEGER SOLUTIONS; LAGRANGIAN-RELAXATION; ALGORITHM; DECOMPOSITION;
D O I：
10.1287/ijoc.1090.0326
中图分类号：
TP39 [计算机的应用];
学科分类号：
081203 ; 0835 ;
摘要：
We show that the linear programming relaxation of the cutting-stock problem can be solved efficiently by the recently proposed inexact bundle method. This method saves work by allowing inaccurate solutions to knapsack subproblems. With suitable rounding heuristics, our method solves almost all the cutting-stock instances from the literature.
引用
收藏
页码：131 / 143
页数：13
相关论文
共 32 条
  • [1] [Anonymous], 1990, Knapsack Problems: Algorithms and ComputerImplementations
  • [2] OR-LIBRARY - DISTRIBUTING TEST PROBLEMS BY ELECTRONIC MAIL
    BEASLEY, JE
    [J]. JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 1990, 41 (11) : 1069 - 1072
  • [3] A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting
    Belov, G
    Scheithauer, G
    [J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2006, 171 (01) : 85 - 106
  • [4] A cutting plane algorithm for the one-dimensional cutting stock problem with multiple stock lengths
    Belov, G
    Scheithauer, G
    [J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2002, 141 (02) : 274 - 294
  • [5] Setup and open-stacks minimization in one-dimensional stock cutting
    Belov, Gleb
    Scheithauer, Guntram
    [J]. INFORMS JOURNAL ON COMPUTING, 2007, 19 (01) : 27 - 35
  • [6] Ben Amor H., 2005, COLUMN GENERATION, P131
  • [7] BENAMOR H, 2004, G200462 GERAD
  • [8] Comparison of bundle and classical column generation
    Briant, O.
    Lemarechal, C.
    Meurdesoif, Ph.
    Michel, S.
    Perrot, N.
    Vanderbeck, F.
    [J]. MATHEMATICAL PROGRAMMING, 2008, 113 (02) : 299 - 344
  • [9] Chvatal Vasek, 1983, Linear Programming
  • [10] de Carvalho JMV, 2005, INFORMS J COMPUT, V17, P175, DOI 10.1287/ijoc.1030.0060
1234