Existem muitas maneiras diferentes de definir e resolver problemas de otimização. Você pode, por exemplo, usar algoritmos gulosos, programação de restrição, programação inteira mista, algoritmos genéticos ou pesquisa local. Neste post, estamos mergulhando na programação de restrições. Como exemplo, o problema de coloração de grafos é usado para ilustrar como funciona a programação de restrições.

Se você precisar de uma introdução aos problemas de otimização e heurística de pesquisa, leia o post abaixo.

Coloração do Gráfico

Vamos começar com o problema de coloração de grafos. Este problema é usado ao longo do post para ilustrar conceitos de programação de restrições.

Para um determinado mapa, você deseja colorir todos os países. Você tem uma quantidade ilimitada de cores. Não é permitido dar a países adjacentes a mesma cor. Qual é a menor quantidade de cores que você precisa para preencher o mapa?

As variáveis ​​são as cores que você dá aos países. A restrição é que não é permitido dar a países adjacentes a mesma cor. O objetivo é minimizar o número de cores usadas.

Parece fácil? Na prática pode ser difícil! Aqui está uma parte da solução para a África:

Outra forma de visualizar este problema é usando vértices e arestas. Os países adjacentes estão conectados com uma vantagem. Os vértices correspondem aos países. Este é o exemplo anterior ilustrado desta forma:

O que é Programação de Restrições?

A ideia-chave da programação por restrição (CP) é que ela usa restrições para reduzir o conjunto de valores que cada variável pode assumir. No CP, o programa (ou solucionador) acompanha os valores que podem aparecer. Após cada movimento, o espaço de busca é podado. Isso significa que os valores que não podem mais acontecer são removidos. Pode ocorrer que não haja mais movimentos possíveis enquanto o solucionador ainda não encontrou uma solução viável. Nesse caso, o solucionador parte de um ponto anterior em que tomou uma decisão e a reconsidera.

Fundamentos

O foco do CP está na viabilidade, em vez da otimização. Após uma decisão, o solucionador verifica a viabilidade e poda o espaço de busca. Na imagem abaixo você pode ver um solucionador CP básico. Grandes partes são a pesquisa e o armazenamento de restrições, que explicarei em detalhes mais adiante. Resumindo: a pesquisa é onde as decisões são tomadas e o armazenamento de restrições contém todos os valores possíveis de variáveis ​​no armazenamento de domínio e contém as restrições. Uma movimentação é feita (por exemplo, você colore um país de vermelho) e, no armazenamento de restrições, o armazenamento de domínio é removido com base na movimentação. Há também a verificação de viabilidade, ou seja, quando o movimento não é possível por violar uma ou mais restrições, ele precisa ser revertido (falha).

No exemplo abaixo, você pode ver que quando você colore um país de vermelho, para os países conectados, o vermelho deve ser removido do armazenamento de domínio, porque essas movimentações não são mais possíveis.

Você pode se perguntar: como a programação de restrições pode encontrar uma solução ótima? Especialmente no problema de coloração de grafos, é fácil encontrar uma solução viável. O mais fácil é dar uma cor diferente para cada país. Essa é uma solução viável, mas está longe de ser a ideal. Existem diferentes maneiras de resolver isso. Um exemplo é continuar resolvendo o problema continuamente e adicionar uma restrição de que a nova solução deve usar menos cores que a anterior.

Procurar

Para pesquisar, existem algumas regras legais que você pode seguir que podem melhorar drasticamente a pesquisa. O primeiro é o princípio da primeira falha . Isso significa que você tenta primeiro onde tem mais probabilidade de falhar. Isso facilita as coisas no final e reduz ao máximo a árvore de pesquisa. Na coloração de gráficos, é melhor começar com um país conectado a muitos outros países do que com um país que não tem muitas conexões:

Isso ajuda, porque é mais difícil dar uma cor a este país se você já pintou os países vizinhos. As chances são altas de que, quando você não começa com este país, precisa dar uma nova cor a ele, algo que você deseja evitar.

Existem diferentes tipos de pesquisa que você pode implementar. Dependendo do problema, você pode escolher o melhor (ou experimentar todos):

• Rotulagem de variável/valor
  Com este método de pesquisa, você começa com as variáveis. Na coloração do gráfico, os países são as variáveis ​​e as cores são os valores. Você escolhe a variável (país) para atribuir a seguir de maneira inteligente. Você pode, por exemplo, escolher aquele que tem os valores mais baixos possíveis. Em seguida, você escolhe o valor (cor) que essa variável receberá. Freqüentemente, é escolhido um valor que deixa tantas opções quanto possível para as outras variáveis. Abaixo um exemplo fácil.

• Rotulagem de valor/variável
  Outra maneira de lidar com a pesquisa é começar com os valores. Você tem uma cor e seleciona um país para dar essa cor. Isso é exatamente o oposto em comparação com a rotulagem de variável/valor. No problema de coloração de gráficos, você pode criar conjuntos de países que podem ter a mesma cor.
• Divisão de domínio
  Com a divisão de domínio, você não atribui um valor diretamente a uma variável. Em vez disso, você divide o domínio (valores possíveis) de uma variável em dois ou mais conjuntos. Esse é um compromisso mais fraco do que dizer: esse país deveria ter esse valor, porque você ainda tem opções de país, um dos valores do conjunto.
• Quebra de simetria durante a pesquisa
  A quebra de simetria pode melhorar drasticamente a pesquisa. Você precisa evitar que soluções simétricas sejam exploradas, porque isso é perda de tempo. Teoricamente, as soluções simétricas são exatamente as mesmas. Uma maneira de começar a quebrar a simetria na coloração do gráfico é fixar cores para determinados países. A melhor maneira de quebrar a simetria é ordenar as variáveis ​​(países) ou levar em consideração apenas os valores atuais (cores) e um novo valor (cor).

• Randomização e reinícios
  Também é possível tentar diferentes soluções em ordem aleatória. Você apenas escolhe valores aleatoriamente para as variáveis ​​e verifica se a solução é viável. Se nenhuma solução for encontrada após algum tempo ou número de tentativas, reinicie a busca.

loja de restrição

Existem diferentes tipos de restrições possíveis de implementar no repositório de restrições. As restrições são usadas para verificação de viabilidade e remoção do armazenamento de domínio. As restrições 'normais' são, no caso da coloração do gráfico, que um país que está conectado a outro país não pode ter a mesma cor. Mas existem outras restrições interessantes que você pode criar com base no problema. O objetivo de adicionar restrições é restringir o problema. Se você fizer uma definição mais precisa, a solução ideal poderá ser encontrada mais rapidamente.

Aqui estão diferentes tipos de restrições que você pode adicionar ao repositório de restrições:

• Restrições globais
  As restrições mais importantes que você pode adicionar são restrições globais. Restrições globais ajudam na poda do espaço de busca e podem detectar a inviabilidade mais cedo. Uma restrição global ajuda a transmitir a estrutura do problema diretamente ao solucionador. Um exemplo de restrição global é a restrição alldiferente . Essa restrição significa que todas as variáveis ​​devem ter valores diferentes. Na coloração do gráfico, quando quatro países estão conectados, todos devem ter uma cor diferente. Se tivermos apenas três cores restantes para esses países, a solução é inviável: podemos reverter e relatar a falha.

• Restrições redundantes
  Uma restrição redundante é uma restrição que não agrega valor ao excluir uma solução. Mas as restrições redundantes são computacionalmente significativas, porque reduzem o espaço de busca. Uma restrição redundante captura algo que não é possível, mas não é capturado em uma restrição. Um exemplo de coloração de gráfico: o número de cores não pode exceder o número de países.
• Restrições substitutas
  Ao combinar restrições existentes, você obtém restrições substitutas. As restrições substitutas são úteis porque fornecem uma visão mais global. Um exemplo é mesclar restrições existentes ou obter uma combinação linear delas.
• Restrições implícitas
  Outro tipo de restrição que você pode adicionar são as restrições implícitas. Derivar uma propriedade de várias restrições existentes fornece restrições implícitas.

Qual a relação entre CP e MIP?

Você já deve ter ouvido falar em programação inteira mista. Esta é outra técnica para modelar problemas de otimização discreta. O MIP usa diferentes maneiras de encontrar as melhores soluções para um problema. Abaixo, você pode ler quais são as semelhanças e diferenças entre CP e MIP.

O que é programação inteira mista?

A programação inteira mista (MIP) é uma técnica de otimização matemática que envolve encontrar a solução ideal para um problema resolvendo um sistema de equações lineares e desigualdades que contêm variáveis ​​inteiras e contínuas. O MIP se concentra na otimização. Para entender corretamente o MIP e a matemática por trás dele, é importante saber como funciona a programação linear e o algoritmo simplex. Leia o artigo abaixo se quiser se atualizar sobre isso:

Um solucionador MIP relaxa as restrições permitindo valores contínuos para as variáveis ​​inteiras. Isso torna possível usar o algoritmo simplex. Depois disso, outras técnicas são usadas para encontrar uma solução válida (valores inteiros para variáveis ​​inteiras). Essas técnicas estão fora do escopo deste post, mas se você estiver interessado, pode pesquisar por termos como ramificação e limite, ramificação e corte e planos de corte (por exemplo, cortes Gomory e cortes poliédricos).

Como CP e MIP estão relacionados

Matematicamente, é possível formular qualquer problema MIP como um problema CP (ou um problema CP como um problema MIP). Então, nesse sentido, eles são iguais. Mas como as maneiras de chegar à solução ideal são diferentes, você pode querer considerar qual é a melhor abordagem para o seu problema específico. MIP usa relaxamento linear enquanto CP usa inferência lógica. O CP funciona na maioria dos casos mais rápido para problemas com muitas restrições 'ou', enquanto o MIP pode lidar com restrições 'e' mais rapidamente. Se você estiver usando um solucionador MIP comercial, eles provavelmente implementaram técnicas de CP dentro dele, como a criação de restrições de alto nível e raciocínio lógico. O MIP é geralmente mais flexível e confiável. Se você tiver tempo, é sempre bom testar diferentes técnicas para ver qual funciona melhor no seu problema.

Conclusão

Esperamos que você tenha gostado desta introdução sobre programação de restrições. É uma técnica que se concentra na viabilidade. O armazenamento de restrições e a maneira de procurar soluções são os principais componentes do CP. Você pode melhorar drasticamente a formulação do modelo se adicionar diferentes tipos de restrições ao armazenamento de restrições. O núcleo do solucionador CP se propaga pelas restrições e verifica se a solução ainda é viável e se a poda é possível. Podar significa remover valores dos domínios variáveis. Os solucionadores de CP podem encontrar soluções ideais, se você lhes der tempo suficiente.

A programação inteira mista é outra maneira de formular problemas de otimização discreta. Ele usa técnicas algébricas para encontrar uma solução ótima. Dependendo do problema, você pode escolher se CP ou MIP é mais adequado.

Abaixo você pode encontrar mais postagens sobre otimização matemática.

Relacionado