Optimization Online


Improved Space-State Relaxation for Constrained Two-Dimensional Guillotine Cutting Problems

André Velasco(asvelasco***at***iff.edu.br )
Eduardo Uchoa(uchoa***at***producao.uff.br)

Abstract: 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 obtains the optimal weights. In order to obtain even better upper bounds, that algorithm is generalized into Algorithm X2 for obtaining optimal two-dimensional item weights. We also present a full hybrid method, called Algorithm X2D, that computes those strong upper bounds but also provides feasible solutions obtained by: (1) exploring the suboptimal solutions hidden in the dynamic programming matrices; (2) performing a number of iterations of a GRASP based primal heuristic; and (3) executing X2H, an adaptation of Algorithm X2 to transform it into a primal heuristic. Extensive experiments with instances from the literature, for both variants with and without item rotation, show that X2D can consistently deliver high-quality solutions and sharp upper bounds. In many cases the provided solutions are certificated to be optimal.

Keywords: Cutting, Dynamic Programming, Integer Programming

Category 1: Combinatorial Optimization

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Citation: @techreport{VelascoUchoa2017, Author = {Andr{\'e} Velasco and Eduardo Uchoa}, Title = {Improved Space-State Relaxation for Constrained Two-Dimensional Guillotine Cutting Problems}, Institution = {Cadernos do LOGIS-UFF}, Address = {Niter{\'o}i, Brazil}, Number = {L-2017-1}, pages = {25}, month = {July}, Year = {2017} }

Download: [PDF]

Entry Submitted: 07/07/2017
Entry Accepted: 07/14/2017
Entry Last Modified: 07/07/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society