Programação por Restrições
- Proposto por
- Rossi, van Beek & Walsh
- Ano
- 2006
- Tipo
- Declarative combinatorial optimization
- Família
- Mathematical programming
Este texto é uma tradução automática e ainda não foi revisado. Ler o original em inglês
O que ele faz?
Programação por Restrições (CP) é um paradigma de otimização declarativo no qual um problema é formulado como um conjunto de variáveis, domínios finitos e restrições, e um resolvedor busca sistematicamente atribuições que satisfaçam todas as restrições.
Formalizada de forma abrangente por Rossi, van Beek e Walsh em seu Handbook of Constraint Programming de 2006, a CP unifica a poda baseada em propagação com a busca inteligente com retrocesso para abordar problemas combinatórios em domínios de agendamento, planejamento e configuração.
A intuição por trás do método
Pense na CP como preencher um quebra-cabeça complexo: cada célula é uma variável com um conjunto de valores legais, e cada regra do quebra-cabeça é uma restrição. Em vez de adivinhar cegamente, a CP usa as regras para eliminar imediatamente valores impossíveis de células vizinhas sempre que uma célula é preenchida. Essa propagação reduz drasticamente o espaço de busca, de modo que o resolvedor explora apenas combinações plausíveis — retrocedendo e revisando apenas quando atinge um beco sem saída.
História
A Programação por Restrições surgiu da pesquisa em inteligência artificial na década de 1970 com trabalhos iniciais sobre satisfação de restrições por Montanari e Mackworth. Amadureceu nas décadas de 1980 e 1990 com o desenvolvimento de algoritmos de consistência de arco, restrições globais e resolvedores práticos como CHIP e ILOG Solver. O campo foi consolidado de forma autoritária por Rossi, van Beek e Walsh no Handbook of Constraint Programming de 2006, que permanece a referência definitiva, cobrindo teoria, algoritmos e aplicações em otimização combinatória.
Quando usar
A Programação por Restrições é mais adequada para problemas combinatórios com restrições complexas e heterogêneas — agendamento, elaboração de horários, configuração e roteamento — onde a viabilidade é tão importante quanto a otimalidade. Ela assume que os problemas podem ser modelados com domínios de variáveis discretos ou enumeráveis. A CP é menos eficaz para otimização contínua ou programas lineares de grande escala, onde os resolvedores de Programação Linear ou Programação Inteira Mista geralmente dominam. Quando as restrições são altamente estruturadas e a propagação pode podar grandes porções do espaço de busca, a CP supera as meta-heurísticas de propósito geral.
Limitações e considerações
- Escalabilidade: a busca exponencial no pior caso torna a CP lenta em instâncias muito grandes com propagação fraca.
- Requer boa modelagem: heurísticas de ordenação de variáveis/valores ruins ou a falta de restrições globais levam a árvores de busca desnecessariamente grandes.
- Domínios contínuos: a CP é nativamente projetada para domínios discretos; problemas contínuos exigem extensões especializadas ou abordagens híbridas.
- Experiência com resolvedores: o uso eficaz exige familiaridade com técnicas de modelagem de restrições e bibliotecas de restrições globais específicas do resolvedor.
As condições da fonte não substituem a revisão científica independente nem a validação por um motor de análise.
Pontos fortes
- Modelagem declarativa: regras complexas do mundo real são expressas diretamente como restrições sem especificar o procedimento de busca.
- Poda poderosa: a propagação de restrições elimina regiões inviáveis precocemente, muitas vezes reduzindo a busca em ordens de magnitude.
- Lida com restrições heterogêneas: restrições lógicas, aritméticas, globais e definidas pelo usuário coexistem naturalmente em um único modelo.
- Garante completude: o resolvedor encontra uma solução ótima ou prova a inviabilidade, ao contrário dos métodos heurísticos.
Aplicações
- Agendamento de funcionários e enfermeiros: atribuir equipes a turnos, satisfazendo restrições de disponibilidade, legislação trabalhista e habilidades.
- Elaboração de horários: construção de horários universitários ou escolares sujeitos a capacidade de sala, disponibilidade de instrutores e restrições curriculares.
- Configuração: montagem de configurações de produtos (computadores, veículos) a partir de catálogos de componentes sob restrições de compatibilidade e recursos.
- Roteamento de veículos e logística: planejamento de rotas de entrega sujeitas a janelas de tempo, capacidades de veículos e regulamentações de motoristas.
- Leilões combinatórios e alocação de recursos: atribuição de recursos a licitantes ou tarefas sob restrições de exclusividade e orçamento.
Como funciona
Como funciona
O problema é codificado como uma tripla de Problema de Satisfação de Restrições, consistindo de variáveis X, seus domínios finitos D e um conjunto de restrições C. Cada variável x_i pode receber qualquer valor de seu domínio D_i. As restrições definem combinações permissíveis de valores em subconjuntos de variáveis, traduzindo regras do mundo real — limites de capacidade, relações de precedência, conflitos de recursos — em uma estrutura matemática sobre a qual o resolvedor pode raciocinar.
Fórmula
\text{CSP} = \langle X, D, C \rangle \quad X = \{x_1, x_2, \ldots, x_n\},\; D = \{D_1, D_2, \ldots, D_n\}Antes e durante a busca, o resolvedor aplica consistência de arco e outros algoritmos de consistência local para podar valores de domínio que não podem participar de nenhuma solução válida. Para cada par de variáveis restritas, a consistência de arco remove valores do domínio de uma variável para os quais não existe um valor de suporte no domínio da outra. Essa propagação é acionada repetidamente após cada atribuição, reduzindo drasticamente o espaço de busca efetivo.
Fórmula
\text{AC}(x_i, x_j): \forall a \in D_i,\; \exists b \in D_j \text{ s.t. } c_{ij}(a, b) \text{ holds}O resolvedor seleciona uma variável não atribuída — tipicamente usando heurísticas como valores mínimos restantes ou grau — e tenta atribuir-lhe um valor de seu domínio podado. A propagação é executada novamente; se uma contradição for detectada (um domínio vazio), o resolvedor retrocede para o ponto de escolha mais recente e tenta um valor alternativo. O salto para trás (backjumping) e o registro de nogoods podem acelerar ainda mais a recuperação de falhas.
Fórmula
x_i \leftarrow a_i \in D_i,\quad \text{propagate},\quad \text{if fail: backtrack and reassign}Quando todas as variáveis foram atribuídas a valores consistentes com todas as restrições, a atribuição completa S* constitui uma solução. Para problemas de otimização, uma função objetivo guia a busca em direção à melhor solução viável, e as estratégias de ramificação e poda (branch-and-bound) apertam progressivamente o limite à medida que soluções melhores são encontradas, até que o ótimo global seja certificado ou um limite de tempo seja atingido.
Fórmula
S^* = \{(x_1, a_1^*), \ldots, (x_n, a_n^*)\} : \forall c \in C,\; c(a_1^*, \ldots, a_n^*) = \text{true}Erros comuns
- Sobre-restringir o modelo com restrições redundantes ou conflitantes faz com que o resolvedor relate incorretamente a inviabilidade.
- Negligenciar restrições globais (por exemplo, alldifferent, cumulative) perde oportunidades de propagação que algoritmos especializados fornecem gratuitamente.
- Ignorar heurísticas de busca e confiar na ordenação padrão de variáveis/valores pode desperdiçar tempo exponencial em ordenações patológicas.
- Confundir satisfação de restrições com otimização: esquecer de adicionar uma função objetivo e o aperto de limites (bound-tightening) produz apenas a primeira solução viável, não a melhor.
Perguntas frequentes
Como a Programação por Restrições difere da Programação Linear Inteira?
Embora ambas resolvam problemas combinatórios, a PLI exige que todas as restrições e objetivos sejam lineares, permitindo limites eficientes de relaxamento LP. A CP não impõe tal requisito de linearidade e, em vez disso, baseia-se na propagação de restrições e na busca sistemática. A CP lida com restrições lógicas e globais complexas de forma mais natural, enquanto a PLI geralmente escala melhor em problemas com forte estrutura linear e grande número de variáveis.
O que são restrições globais e por que elas são importantes?
Restrições globais são restrições de alto nível sobre um número arbitrário de variáveis — por exemplo, alldifferent (todas as variáveis assumem valores distintos) ou cumulative (o uso de recursos a qualquer momento não excede a capacidade). Elas são importantes porque os resolvedores implementam algoritmos de propagação dedicados e altamente eficientes para cada uma, alcançando uma poda muito mais forte do que decompor a mesma condição em muitas restrições binárias, o que deixaria grande parte do espaço de busca inexplorado.
A Programação por Restrições pode encontrar soluções ótimas ou apenas viáveis?
A CP pode encontrar soluções ótimas combinando a busca de viabilidade com uma função objetivo. O resolvedor usa ramificação e poda (branch-and-bound): uma vez encontrada uma solução viável, ele adiciona uma restrição exigindo que qualquer solução subsequente seja estritamente melhor, continuando até que nenhuma melhoria seja possível. Isso certifica a otimalidade. Se o tempo de execução for limitado, a melhor solução encontrada até o momento é retornada como uma aproximação.
Métodos relacionados
Fontes
Rossi, F., van Beek, P., & Walsh, T. (Eds.). (2006). Handbook of Constraint Programming. Elsevier.
ISBN: 978-0-444-52726-4Copiado.