Advanced search
Start date

Theory and practice of cutting and packing problems

Grant number: 06/03496-3
Support type:Research Projects - Thematic Grants
Duration: December 01, 2006 - February 28, 2010
Field of knowledge:Engineering - Production Engineering - Operational Research
Principal researcher:Marcos Nereu Arenales
Grantee:Marcos Nereu Arenales
Home Institution: Instituto de Ciências Matemáticas e de Computação (ICMC). Universidade de São Paulo (USP). São Carlos , SP, Brazil
Pesquisadores principais:
Horacio Hideki Yanasse ; Reinaldo Morabito Neto ; Vinicius Amaral Armentano
Assoc. researchers: Adriana Cesário de Faria Alvim ; Andrea Carla Gonçalves Vianna ; Antonio Carlos Moretti ; Aurelio Ribeiro Leite de Oliveira ; Clovis Perin Filho ; Débora Pretti Ronconi ; Denise Sato Yamashita ; Ernesto Julián Goldberg Birgin ; Franklina Maria Bragion de Toledo ; Gisele Castro Fontanella Pileggi ; José Carlos Becceneri ; Marcia Aparecida Gomes Ruggiero ; Maria Cristina Nogueira Gramani ; Maria Do Socorro Nogueira Rangel ; Maristela Oliveira dos Santos ; Nei Yoshihiro Soma ; Robinson Samuel Vieira Hoto ; Silvio Alexandre de Araujo ; Valéria de Podestá Gomes ; Vinicius Amaral Armentano ; Vitória Maria Miranda Pureza
Associated scholarship(s):09/07423-9 - Contributions to the integrated vehicle routing and container loading problems, BP.DR
08/09040-7 - Theoretical and computational issues for the efficient implementation of linear optimization methods, BP.DR
08/09046-5 - Compartmentalized knapsack problems: one-dimensional and two-dimensional cases, BP.DR
+ associated scholarships 07/06532-3 - Cutting and packing problems, BP.PD
07/08352-2 - The traveling salesman problem: mathematical models and solution methods, BP.IC
07/05698-5 - The minimization of open stacks problem - new contributions, BP.DR
07/01791-0 - Effective implementations of simplex type methods for solving linear programming problems, BP.MS
07/05689-6 - The Dynamic Pickup and Delivery Problem with Time Windows, BP.MS - associated scholarships


The main subject of this thematic project is the study of Cutting and Packing Problems (CPP), which covers a large number of combinatorial optimization problems. These problems share the common feature of fitting items inside an object. This fitting, in its actual sense, can define the cutting of pieces in stock to produce the demanded items, as well as, the packing of boxes in a container. Besides the various practical applications of this actual sense version, cutting and packing problems also arise naturally in symbolic arrangements as important subproblems in the use of scarce resources which is the essence of operations research problems, such as, project selection, lot sizing, job allocation, etc. CPP's relevance comes from the increasing pressure that the industries have been receiving in order to optimize their processes. This pressure comes from, among other reasons, the increasing competition imposed by the new world economic order. Brazil is following this path and it is experiencing deep changes in its productive sector with respect to the modernization of its productive processes, better quality control of its products and administrative rationalization. This project aims to develop mathematical models for problems arising from the cutting and packing industrial sector, the development and/or improvement of solution methods, the development of computational studies, the identification of new practical problems, as well as, the review of problems in the literature. Studies on cutting and packing problems have been undertaken by many researchers in different education/research centers in S. Paulo state. They have been carried in a independent way or by means of joint research works. This project seeks to maintain this integration and to aggregate new research groups working in this subject, aiming the exchange of different experiences and knowledge developed independently. With this, we aim to achieve improved quality research, avoid parallel work, improving overall performance by the synergy of the cooperative work. (AU)

Articles published in Agência FAPESP Newsletter about the research grant:
Articles published in other media outlets (0 total):
More itemsLess items

Scientific publications (12)
(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)
BIRGIN, ERNESTO G.; MARTINEZ, J. M.. Augmented Lagrangian method with nonmonotone penalty parameters for constrained optimization. COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, v. 51, n. 3, p. 941-965, . (06/53768-0, 06/03496-3, 09/10241-0)
BIRGIN, ERNESTO G.; GENTIL, JAN M.. Evaluating bound-constrained minimization software. COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, v. 53, n. 2, SI, p. 347-373, . (09/10241-0, 06/53768-0, 06/03496-3)
RONCONI, DEBORA P.; POWELL, WARREN B.. Minimizing total tardiness in a stochastic single machine scheduling problem using approximate dynamic programming. JOURNAL OF SCHEDULING, v. 13, n. 6, p. 597-607, . (06/03496-3)
DENISE SATO YAMASHITA; REINALDO MORABITO. Um algoritmo branch-and-bound para o problema de programação de projetos com custo de disponibilidade de recursos e múltiplos modos. Gestão & Produção, v. 14, n. 3, p. 545-555, . (06/03496-3)
ANDRADE, R.; BIRGIN, E. G.. Symmetry-breaking constraints for packing identical rectangles within polyhedra. Optimization Letters, v. 7, n. 2, p. 375-405, . (10/10133-0, 06/53768-0, 06/03496-3, 09/10241-0)
BIRGIN, ERNESTO G.; RONCONI, DEBORA P.. Heuristic methods for the single machine scheduling problem with different ready times and a common due date. ENGINEERING OPTIMIZATION, v. 44, n. 10, p. 1197-1208, . (10/10133-0, 06/53768-0, 06/03496-3, 09/10241-0)
BIRGIN, E. G.; LOBATO, R. D.; MORABITO, R.. An effective recursive partitioning approach for the packing of identical rectangles in a rectangle. Journal of the Operational Research Society, v. 61, n. 2, p. 306-320, . (06/53768-0, 06/03496-3)
JUNQUEIRA, LEONARDO; MORABITO, REINALDO; YAMASHITA, DENISE SATO. Three-dimensional container loading models with cargo stability and load bearing constraints. Computers & Operations Research, v. 39, n. 1, SI, p. 74-85, . (06/03496-3)
LITVINCHEV, IGOR; RANGEL, SOCORRO; SAUCEDO, JANIA. A Lagrangian bound for many-to-many assignment problems. JOURNAL OF COMBINATORIAL OPTIMIZATION, v. 19, n. 3, SI, p. 241-257, . (06/03496-3, 07/08678-5)
RONCONI, DEBORA P.; KAWAMURA, MARCIO S.. The single machine earliness and tardiness scheduling problem: lower bounds and a branch-and-bound algorithm. COMPUTATIONAL & APPLIED MATHEMATICS, v. 29, n. 2, p. 107-124, . (06/03496-3)
LEONARDO JUNQUEIRA; REINALDO MORABITO; DENISE SATO YAMASHITA. Modelos de otimização para problemas de carregamento de contêineres com considerações de estabilidade e de empilhamento. Pesquisa Operacional, v. 30, n. 1, p. 73-98, . (06/03496-3)
SOCORRO RANGEL; ALTAMIR G. DE FIGUEIREDO. O problema de corte de estoque em indústrias de móveis de pequeno e médio portes. Pesquisa Operacional, v. 28, n. 3, p. 451-472, . (06/03496-3)

Please report errors in scientific publications list by writing to: