MODELOS E ALGORITMOS PARA O PROBLEMA DA MOCHILA QUADRÁTICO 0-1

Resumo

Suponha uma mochila com uma determinada capacidade e um conjunto de objetos, onde cada objeto possui um peso, benefícios associados a si, e benefícios cruzados, onde temos uma relação entre pares de objetos. Considere como objetivo escolher um subconjunto desses objetos tal que quando colocados na mochila tenhamos um benefício total máximo e a capacidade da mochila seja respeitada. Denomina-se tal problema como Problema da Mochila Quadrática 0-1 (QKP). Podemos interpretar o QKP em termos de Teoria dos Grafos. Considere um grafo G=(V,E), completo, não direcionado, com um conjunto V de vértices e um conjunto E de arestas. Adicionalmente, assuma que um conjunto de pesos para cada vértice de G e um conjunto de benefícios associados aos vértices e arestas de G. Neste caso o QKP corresponde a encontrar um subconjunto de G com a soma máxima dos benefícios, tal que a soma dos pesos dos vértices não ultrapasse uma determinada capacidade. Apesar de sua fácil descrição e formulação o QKP é um problema desafiador, tendo sido amplamente estudado na literatura. Ele é considerado um problema NP-difícil. Este trabalho tem como objetivo o estudo das formulações existentes na literatura para o problema da mochila quadrática 0-1, o estudo dos algoritmos/heurísticas existentes na literatura para o problema e o estudo de aplicações relacionadas ao problema. A realização do trabalho de pesquisa em questão se baseia em consultas a fontes bibliográficas, estudos teóricos sobre o problema, desenvolvimento e implementação de algoritmos e execução de experimentos computacionais. Para realizar implementações computacionais pretendemos utilizar a linguagens de programação Python, e o resolvedor de MIP Gurobi.