Class constrained cutting stock problems

• Grant number: 14/25892-4
• Support type: Scholarships in Brazil - Master
• Effective date (Start): April 01, 2015
• Effective date (End): February 29, 2016
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Cooperation agreement: Coordination of Improvement of Higher Education Personnel (CAPES)
• Principal researcher: Flávio Keidi Miyazawa
• Grantee: Yulle Glebbyo Felipe Borges
• Home Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil

Abstract

In this project, we interested in studying the cutting stock problem under class constraints. In this problem, we look for the minimal amount of rolls from which we can cut smaller items of different classes (or colors), sizes and demands, knowing that each roll has a limit on the amount of items with different colors that can be cut from it. This kind of problem has received little attention from the literature. We intendo to use Branch-and-Price techniques to look for optimal integer solutions for this problem. Branch-and-Price has shown success in solving some cutting and packing problems such as the simple cutting stock problem, however there are few works on using this technique to solve problems with class constraints. This technique uses the problem's structure to find integer solutions, so it is necessary to be cautious to implement it so that the problem' structure is not modified in a way that makes it even harder to be solved. One of the main objectives of this project is to present an effective Branch-and-Price technique to solve the class-constrained cutting stock problem in its unidimensional and bidimensional variants. (AU)

Scientific publications

(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)

BORGES, YULLE G. F.; MIYAZAWA, FLAVIO K.; SCHOUERY, RAFAEL C. S.; XAVIER, EDUARDO C. Exact algorithms for class-constrained packing problems. COMPUTERS & INDUSTRIAL ENGINEERING, v. 144, JUN 2020. Web of Science Citations: 1.

Academic Publications

(References retrieved automatically from State of São Paulo Research Institutions)

. Algoritmos branch-and-price para o problema de empacotamento em recipientes com restrições de classe. 2016. 60 f. Master's Dissertation - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação.