Framework para Constraint Programming

  • Article

A Microsoft disponibilizou um framework chamado Solver Foundation que facilita a resolução de problemas lógicos e/ou matemáticos complexos.

Este Solver utiliza a técnica de Constraint Programming que é um tipo de programação baseada em declarações e visa resolver com poucas linhas problemas que vão desde logística (caminho de menor custo, etc.) até jogos simples como o Sudoku.

Neste tipo de programação começamos por algo que chamamos de Modelo, que define o espaço de soluções possíveis para o problema e um conjunto de restrições (constraints) que farão com que apenas umas poucas, senão uma única, solução exista (obs.: podendo também não haver soluções para a restrição dadas).

Um bom exemplo é o clássico problema da equação de adição

    S  E N  D      +

    M O R E

--------------

M O N E Y

onde cada letra corresponde a um dígito e nosso problema é encontrar esta correspondência para que a adição dê certo (não vou dar a resposta para que você sinta como é difícil. Mesmo assim, aqui fica a minha proposta: tente resolver por programação! Com isto, você dará mais valor ao Solver)

Para resolver este problema com o Solver Foundation podemos simplesmente descrever o modelo abaixo:

Model[

Decisions[Integers[0,9],s,e,n,d,m,o,r,y],

Constraints[

                             1000*s + 100*e + 10*n + d +

                             1000*m + 100*o + 10*r + e

              == 10000*m + 1000*o + 100*n + 10*e + y,

             Unequal[s,e,n,d,m,o,r,y],

             s>=1,

            m>=1

        ]

]

Neste modelo (que usa a linguagem OML) podemos perceber que:

  • Decisions declara os valores possíveis para cada letra (o que chamei de espaço do problema);
  • Constraints declara as restrições ao espaço.

O Solution Foundation permite que você use um AddIn do Excel para resolver problemas deste tipo ou, que você programe em .Net utilizando a API do Solution Foundation para obter a(s) solução(ões). Nesta segunda opção, você poderá fazer binding com seu banco de dados para trazer dados reais para o modelo antes de mandar resolver o problema. Não é poderoso?

clip_image002

Imagine agora como será simples inserir na sua aplicação a facilidade de resolver problemas como os de MinMax, logística, ou outros.

Aqui vão alguns links interessantes para o Solution Foundation:

Vale uma olhada!