An exact algorithm for general, orthogonal, two-dimensional knapsack problems

摘要: Abstract We present a new exact tree-search procedure for solving two-dimensional knapsack problems in which number of small rectangular pieces, each given size and value, are required to be cut from large stock plate. The objective is maximise the value pieces or minimise wastage. consider case where there maximum times that piece may used cutting pattern. algorithm limits tree search by using bound derived Langrangean relaxation 0–1 integer programming formulaton problem. Subgradient optimisation optimise this bound. Reduction tests both original problem Lagrangean produce substantial computational gains. performance indicates it an effective capable optimally practical medium size.