Banca de QUALIFICAÇÃO: MATHEUS MACHADO VIEIRA

Uma banca de QUALIFICAÇÃO de MESTRADO foi cadastrada pelo programa.
STUDENT : MATHEUS MACHADO VIEIRA
DATE: 26/07/2022
TIME: 10:00
LOCAL: Remoto (meet)
TITLE:

Metaheuristics for the Knapsack Problem with Forfeits

KEY WORDS:

Combinatorial Optimization, Knapsack Problem, Metaheuristics, Iterated Local Search, Variable Neighborhood Descent.

PAGES: 40
BIG AREA: Ciências Exatas e da Terra
AREA: Ciência da Computação
SUBÁREA: Teoria da Computação
SPECIALTY: Análise de Algoritmos e Complexidade de Computação
SUMMARY:

The knapsack problem is among one the most well-known and studied optimization problems. Its potential applications make it a good model for a real-life problem. In this work, the Knapsack Problem with Forfeits will be addressed. In this variant, pairs of conflicting items in the solution imply a penalty. Given a set of items and a conflict graph, the objective is to find a collection of items that respect the knapsack's capacity and maximizes the total value of the items minus the penalties. This problem can be applied from the organization of the workforce on the shop floor to investment decision problems. This work proposes the construction of a new method for the problem using well-established tools, the ILS meta-heuristic, and the VND local search heuristic, and there is also the possibility of verifying other heuristics and meta-heuristics. Preliminary results have already been obtained, showing that the new method surpasses others approaches. It can be expected that this work offers an indication of the path that can be taken to refine the resolution of the problem, presenting analyzes and comparisons between methods applied to the problem.

 

 

 

BANKING MEMBERS:
Presidente - 1114959 - RIAN GABRIEL SANTOS PINHEIRO
Interno - 1388993 - BRUNO ALMEIDA PIMENTEL
Interno - 1803490 - BRUNO COSTA E SILVA NOGUEIRA
Interno - 2343385 - ERICK DE ANDRADE BARBOZA