Operations Research · 1985 · 483 citations · 15 references
Mathematical ProgrammingBranch-and-bound AlgorithmLagrangean RelaxationEngineeringRange SearchingComputer-aided DesignDiscrete OptimizationOperations ResearchDiscrete MathematicsCombinatorial OptimizationComputational GeometryGeometric ModelingInteger OptimizationComputer ScienceTwo-dimensional Cutting ProblemRectangular PiecesProblem ReductionInteger ProgrammingGeometric AlgorithmNatural SciencesMixed Integer OptimizationAlgorithmic EfficiencyLinear Programming
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