Advanced search
Start date

A study of the knapsack problem with special constraints

Grant number: 17/26969-9
Support Opportunities:Scholarships in Brazil - Scientific Initiation
Effective date (Start): April 01, 2018
Effective date (End): 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


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 sub problem 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. (AU)

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

Please report errors in scientific publications list using this form.