Desenvolvimento de uma Abordagem CLP-MILP Híbrida Utilizando o Ambiente Java

André Augusto Kaviatkovski; Leandro Magatao

doi:10.20906/CPS/SICITE2015-0706

Resumo

O presente trabalho propõe uma abordagem híbrida sequencial CLP-MILP para resolução de problemas combinatórios. Para desenvolvimento desta proposta, é tomado como base um problema de scheduling, no qual se pretende planejar e agendar atividades de curto prazo em um duto que liga uma refinaria à um porto, e para este problema são propostos dois modelos matemáticos distintos de solução, um construído utilizando-se uma abordagem MILP e, o outro, CLP, tais modelos se utilizam das mesmas variáveis em sua construção e são equivalentes. Deste modo, após uma análise dos benefícios de cada abordagem de solução individual, é proposta uma forma híbrida sequencial CLP-MILP para resolução, que consiste na realização de um processamento inicial do problema no modelo CLP, de forma a se obter uma resposta inicial e um novo domínio para as variáveis de decisão e então estes valores são passados como entrada para o modelo MILP, o qual resolve o problema, utilizando-se, portanto, de uma série de condições iniciais a mais obtidas pelo modelo CLP. A partir desta proposta de abordagem é desenvolvido, neste trabalho, uma implementação no ambiente Java da referida abordagem híbrida CLP-MILP. Deste modo, tornou-se possível a realização de experimentos para comparação do desempenho computacional das abordagens básicas, em relação a abordagem combinada proposta. A partir destes experimentos foi possível se identificar que, (a) a abordagem CLP é, nas condições atuais dos solvers, inferior as abordagens MILP e CLP-MILP; (b) a abordagem combinada proposta não possui um peso computacional elevado, podendo ser utilizada em problemas que envolvam modelagem MILP e CLP; (c) os testes realizados indicam que a abordagem combinada tem um desempenho equivalente, várias vezes superior, ao da abordagem MILP de base. Contudo, os dados obtidos dos experimentos computacionais realizados não permitem se identificar a existência de um ganho real na questão computacional com a abordagem proposta.

Palavras-chave: MILP; CLP; Hibridização; Scheduling; Pesquisa Operacional