julio-cmdr/agrupamento-de-arts-crea

O objetivo desse código é minimizar o gasto de Anotações de Responsabilidade Técnica (A.R.T.) com o CREA mediante a criação de projetos para crédito rural.

Agrupamento de projetos de crédito rural para minimização dos gastos com ARTs perante o CREA.

O objetivo desse código é minimizar o gasto com Anotações de Responsabilidade Técnica (A.R.T.) para o CREA mediante a criação de projetos para crédito rural. Esse desafio pode ser considerado uma variação do problema da mochila binária. No entanto nenhum produto (projeto) pode ser deixado para trás e o desafio consiste em utilizar o menor número possível de mochilas (A.R.T coletivas).

De acordo com a soma de todos os projetos e o limite máximo de cada grupo é possível levantar uma hipótese para o número mínimo de grupos a ser utilizado. Sendo assim para a solução foi implementado uma heurística gulosa e um método de força bruta paralelizado através do OpenMp. O código inicialmente executa a heurística e tenta encontrar o número mínimo de projetos. Caso a heurística não resulte no valor esperado o força bruta é executado. Se o força bruta também não encontrar o número de grupos esperado fica provado que a hipótese inicialmente levantada é falsa e a execução reinicia tentando agora uma quantidade de grupos maior que a anterior (+1). Esse processo é realizado até que os grupos sejam formados.

Observe que esse é um problema exponencial e no caso do força bruta a execução pode ser impraticável, tendo no pior caso uma complexidade de (2^n)^m, em que n é o número de projetos e m o número de grupos. Por esse motivo a execução foi limitada a 64 projetos, apesar de que com aproximadamente 35 projetos o força bruta já possa demorar mais que um dia. Na paralelização, buscando um balanceamento de carga entre as threads, o processo foi realizado no laço for mais interno. Isso faz com que o tempo para criação das threads a cada iteração de um laço externo se torne mais relevante que a execução quando o número de projetos é baixo. Portanto para quantidades pequenas de projetos (aproximadamente < 27) o programa deve ser executado com apenas uma thread.

O arquivo de entrada deve seguir os padrões do arquivo "entradas.txt", em que na primeira linha é informado a quantidade de projetos e nas seguintes um identificador e o valor da ART de cada um. Após o make, compatível com vários sistemas operacionais, a execução deve passar como parâmetro para o binário o arquivo de entrada e o número de threads. Exemplo para windows:

main-release.exe entrada.txt 1