A study of the knapsack problem with special constraints

• Grant number: 17/26969-9
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: April 01, 2018
• End date: December 31, 2019
• Field of knowledge: Engineering - Production Engineering - Operational Research
• Principal Investigator: Maria Do Socorro Nogueira Rangel
• Grantee: Natália da Silva Rodrigues
• Host Institution: Instituto de Biociências, Letras e Ciências Exatas (IBILCE). Universidade Estadual Paulista (UNESP). Campus de São José do Rio Preto. São José do Rio Preto , SP, Brazil
• Associated research grant: 16/01860-1 - Cutting, packing, lot-sizing, scheduling, routing and location problems and their integration in industrial and logistics settings, AP.TEM

Abstract

The knapsack problem is one of the most studied problem in the combinatorial optimization literature. It has several direct applications and also appears as a subproblem in various production planning problems, such as the lot sizing problem and the cut and packing problem. Strong valid inequalities for the knapsack polytope have been successfully used in the solution process of integer optimization problems and are present in several general purpose mixed integer optimization systems. However, there are limitations in these systems that indicate the need to develop specific solution methods. In this project we propose the study of the mathematical formulation and solution methods for the knapsack problem with emphasis on the study of strong valid inequalities that can be useful in solving special cases of the problem that involve setup constraints. This study will contribute to increase the efficiency of the solution methods used to solve production planning problems for the furniture industry.