6ª Aula

27 Março 2017, 14:00 • João Marques Silva

A sexta aula iniciou o estudo de problemas sobre-restringidos (overconstrained). Foram apresentados vários tipos de problemas relacionados com a análise de problemas sobre-restringidos: explicações minímas e minimais, e relaxações máximas a maximais. Foram apresentados dois problemas concretos, nomeadamente o problema de maximum satisfiability (MaxSAT) e o problema de minimum satisfiability (MinSAT). A aula estudou com maior detalhe o problema de MaxSAT. Foram apresentados vários exemplos de modelação, realçando aplicações práticas. Finalmente, foram estudados algoritmos baseados em resolução iterativa de restrições, procura branch-and-bound, e baseados em identificação iterativa de cores.