On stabilizing column generation for cutting stok problem

Author(s)

Marco Antonio Lozano Porta Lopes

• Document type: Master's Dissertation
• Press: São Carlos.
• Institution: Universidade de São Paulo (USP). Instituto de Ciências Matemáticas e de Computação (ICMC/SB)
• Defense date: 2006-03-14

Examining board members

Marcos Nereu Arenales; Robinson Samuel Vieira Hoto; Franklina Maria Bragion de Toledo

• Advisor: Marcos Nereu Arenales

Abstract

The cutting stock problem consists of cutting large available objects in stock to produce a quantity of ordered smaller itens, in such a way as to optimize a given objective function. A linear optmizatim model has been widely used to solve this problem since the 60s, in which part of a combinatorial structure of the problem is embedded. The columns of the constraint matrix are generated in each iteration of the Simplex Method, called the column generation technique. Although, the Simplex Method is widely used, it has a low convergence near to optimality. In this way, strategies to accelerate the Simplex Method are welcome which can be obtained by adding dual cuts (primal columns). The goal of this work is to study published dual cuts and to proposed others. In this book us extend two families of dual cuts, which were recently published, and analyse the computational impact of these dual cuts on the converge of the Simplex Method (AU)