Solving binary cutting stock with matheuristics Chapter in Scopus uri icon

Abstract

  • © Springer International Publishing Switzerland 2014. Many Combinatorial Optimization (CO) problems are classifed as NP - complete problems. The process of solving CO problems in an efficient manner is important since several industry, government and scientific problems can be statedin this form. This work presents a benchmark of three different methodologies to solve the Binary Cutting Stock (BCS) problem; exact methodology by applying Column Generation (CG), a Genetic Algorithm (GA) and an hybrid between exact methods and Genetic Algorithms in a Column Generation framework which we denominate Matheuristic (MA). This benchmark analysis is aimed to show Matheuristic solution quality is as good as the obtained by the exact methodology. Details about implementation and computational performance are discussed.

Publication date

  • January 1, 2014