Operations Research · 1985 · 491 citations · 15 references
Natural SciencesComputer ScienceMathematicsAlgorithmsDesign OptimizationOptimizationBranch And BoundCombinatorial OptimizationConstrained OptimizationDiscrete OptimizationInteger ProgrammingOptimization TheoryBranch-and-cutInteger Programming RelaxationsTree Search
We consider the two‑dimensional cutting problem of extracting rectangular pieces from a single large rectangle to maximize the total value of the pieces cut. The study develops a Lagrangean relaxation of a zero‑one integer programming formulation to serve as a bound in a tree search procedure. Subgradient optimization refines the Lagrangean bound, and problem‑reduction tests derived from both the original problem and the relaxation are applied. Incorporating the bound and the reduction tests into the tree search enables moderately sized problems to be solved.
We consider the two-dimensional cutting problem of cutting a number of rectangular pieces from a single large rectangle so as to maximize the value of the pieces cut. We develop a Lagrangean relaxation of a zero-one integer programming formulation of the problem and use it as a bound in a tree search procedure. Subgradient optimization is used to optimize the bound derived from the Lagrangean relaxation. Problem reduction tests derived from both the original problem and the Lagrangean relaxation are given. Incorporating the bound and the reduction tests into a tree search procedure enables moderately sized problems to be solved.
15
Orthogonal Packings in Two Dimensions
Brenda S. Baker, E. G. Coffman, Ronald L. Rivest · SIAM Journal on Computing · 1980 · 695 citations
The Theory and Computation of Knapsack Functions
Paul C. Gilmore, Ralph E. Gomory · Operations Research · 1966 · 607 citations