Otimização de restrições, ou programação de restrições (CP, na sigla em inglês), é o nome dado à identificação de soluções viáveis em um conjunto muito grande de candidatos, em que o problema pode ser modelado em termos de restrições arbitrárias. Os problemas de CP surgem em muitas áreas científicas e de engenharia. A palavra "programação" é um pouco equivocada, semelhante a como "computador" significava "uma pessoa que faz cálculos". Aqui, "programação" se refere à organização de um plano, e não à programação em uma linguagem de computador.
A CP é baseada na viabilidade (encontrar uma solução viável), em vez da otimização (encontrar uma solução ideal), e se concentra nas restrições e variáveis, não na função de objetivo. Na verdade, um problema de CP pode nem ter uma função objetiva. O objetivo pode ser restringir um conjunto muito grande de soluções possíveis a um subconjunto mais gerenciável adicionando restrições ao problema.
Um exemplo de problema adequado para a CP é a programação de funcionários.
O problema surge quando as empresas que operam continuamente, como
fábricas, precisam criar programações semanais para os funcionários. Veja um exemplo muito simplificado: uma empresa realiza três turnos de oito horas por dia e atribui
três de seus quatro funcionários a turnos diferentes todos os dias, com um
quarto dia de folga. Mesmo em um caso tão pequeno, o número de escalas possíveis
é grande: todos os dias, existem 4! = 4 * 3 * 2 * 1 = 24 possíveis atribuições de funcionários, então o número de horários semanais possíveis é de 2474, o que
é mais de 5 bilhões.
Normalmente, haverá outras restrições que reduzem o número de soluções
viáveis. Por exemplo, cada funcionário trabalha pelo menos um número
mínimo de dias por semana. O método CP monitora quais soluções permanecem viáveis quando você adiciona novas restrições, o que o torna uma ferramenta poderosa para resolver grandes problemas de programação do mundo real.
A CP tem uma comunidade ampla e muito ativa em todo o mundo, com periódicos científicos dedicados, conferências e um arsenal de diferentes técnicas de solução. A CP foi aplicada com sucesso no planejamento, programação e vários outros domínios com restrições heterogêneas.
Ferramentas
O Google oferece algumas maneiras de resolver os problemas de CP:
- Solucionador de problemas C-SAT: um solucionador de restrições de programação que usa métodos de satisfação (SAT, na sigla em inglês).
- Solucionador de CP original: um solucionador de restrição de programação usado na biblioteca de roteamento.
Se o problema puder ser modelado com um objetivo linear e restrições lineares, você tem um problema de programação linear e deve considerar MPSolver (link em inglês). No entanto, os problemas de definição de trajeto costumam ser resolvidos mais facilmente com nossa biblioteca de roteamento de veículos, mesmo que possam ser representados com um modelo linear.
Exemplos
A próxima seção descreve o solucionador CP-SAT, o solucionador principal de ferramentas OR para programação de restrições. SAT significa satisfabilidade: o solucionador usa técnicas para resolver problemas de SAT junto com métodos de CP.
Veja alguns exemplos de problemas de programação adequados para o solucionador C-SAT:
Dois problemas clássicos de CP são o problema do N-Queens e os enigmas criptoaritméticos.