The following information was submitted:
Transactions: WSEAS TRANSACTIONS ON INFORMATION SCIENCE AND APPLICATIONS
Transactions ID Number: 53-343
Full Name: Cláudio Alves
Position: Assistant
Professor
Age: ON
Sex: Male
Address: Departamento de Produção e Sistemas, Campus de Gualtar, 4710-057 Braga
Country: PORTUGAL
Tel:
Tel prefix:
Fax:
E-mail address: claudio@dps.uminho.pt
Other E-mails:
Title of the Paper: Computing lower bounds with low complexity using dual-feasible functions
Authors as they appear in the Paper: Jürgen Rietz, Rita Macedo, Cláudio Alves, José Valério de Carvalho
Email addresses of all the authors: juergen_rietz@gmx.de,rita@dps.uminho.pt,claudio@dps.uminho.pt,vc@dps.uminho.pt
Number of paper pages: 10
Abstract: In this paper, we explore the use of maximal dual-feasible functions to compute strong lower bounds for hard combinatorial optimization problems. We consider in particular the 2-dimensional cutting stock problem with and without guillotine cuts, and especially the exact and the inexact case of cutting in two stages. These problems have a wide scope of applicability in industries like furniture, metallurgy and the paper industry. We describe a set of lower bounding algorithms with low polynomial complexity for each case, and we describe the best set of parameters that should be used for given functions. Extensive computational experiments on instances of the literature prove the strength of the bounds.
Keywords: Combinatorial optimization; Lower bounds; Maximal dual-feasible functions; Polynomial complexity; 2-dimensional cutting stock problem; Guillotine cuts
EXTENSION of the file: .doc
Special (Invited) Session:
Organizer of the Session:
How Did you learn about congress: Operations Research; Optimization Techniques
IP ADDRESS: 83.132.0.161
