Improved Space-State Relaxation for Constrained Two-Dimensional Guillotine Cutting Problems
Christofides and Hadjiconstantinou introduced a dynamic programming state space relaxation for obtaining upper bounds for the Constrained Two-dimensional Guillotine Cutting Problem. The quality of those bounds depend on the chosen item weights, they are adjusted using a subgradient-like algorithm. This paper proposes Algorithm X, a new weight adjusting algorithm based on integer programming that provably … Read more