Este projeto propõe o estudo de problemas de otimização combinatória sob restrições disjuntivas. Dados um problema de otimização combinatória P e um conjunto de restrições disjuntivas C composto por pares de componentes do problema P, busca-se uma solução para o problema P tal que as componentes da solução satisfaçam as restrições disjuntivas. São consideradas duas classes de restrições disjuntivas. As restrições disjuntivas positivas impõem que, dadas duas componentes do problema, pelo menos uma delas pertença à solução. Por sua vez, as restrições disjuntivas negativas impõem que dadas duas componentes do problema apenas uma delas pode pertencer à solução. Problemas clássicos de otimização combinatória com métodos de solução polinomial na sua formulação original como caminhos mínimos, árvores geradoras mínimas e emparelhamento viram NP–difíceis na presença de restrições disjuntivas. No presente projeto pretende-se atacar este tipo de problemas tanto em forma aproximada quanto exata.

Alunos envolvidos: Graduação: (1) / Mestrado acadêmico: (2) / Doutorado: (1) .

Integrantes: Sebastián Alberto Urrutia – Coordenador.