Introdução prática à programação por restrições com CP-SAT e Python

Introdução prática usando programação por restrições: CP-SAT e Python

Paradigma declarativo

• Programação por restrições (CP) é um paradigma declarativo para resolver problemas de otimização discreta
• Diferentemente da programação imperativa, você descreve o resultado desejado e o programa deriva a solução por conta própria
• Por exemplo, explica a diferença entre a abordagem imperativa e a abordagem declarativa ao extrair uma lista de adultos

Fundamentos da programação por restrições (CP)

• Modelo: descrever o resultado desejado do problema
• Variáveis: os valores que se deseja encontrar; cada variável tem um domínio (conjunto de valores permitidos)
• Restrições: descrevem as relações entre as variáveis
• Solução: atribuir valores às variáveis de modo a satisfazer as restrições

Exemplo prático com Python e CP-SAT

• Problema: gerar a escala semanal de trabalho dos funcionários
• Criação do modelo: usar o CP-SAT para criar um modelo vazio
• Dados: definir a lista de funcionários e funções, os dias de trabalho e os turnos
• Definição de variáveis: criar variáveis booleanas que indiquem se cada funcionário trabalha ou não
• Adição de restrições: adicionar restrições às variáveis de acordo com a descrição do problema

Resolvendo o modelo

• Resolução: resolver o modelo e obter o resultado
• Restrições adicionais: adicionar restrições extras, como evitar horas extras, limitar a carga horária de determinados funcionários e impedir sobreposição de horários entre certos funcionários

No meio do caminho: status da solução

• Status da solução: retorna estados como ótimo, viável, inviável e desconhecido
• Exemplo: explica cada estado por meio de um exemplo simples

"Desculpe, Emma"

• Estado inviável: é impossível que Emma folgue 5 dias durante a semana
• Sugestão de alternativa: sugerir que Emma folgue apenas 3 dias durante a semana

Objetivo: distribuição equilibrada da carga horária

• Adicionar objetivo: incluir um objetivo para distribuir a carga horária de forma equilibrada
• Resultado: a carga horária de cada funcionário é distribuída de maneira uniforme

Conclusão

• Introdução aos conceitos básicos: apresenta os conceitos fundamentais da programação por restrições e os explica com um exemplo prático
• Prévia do próximo artigo: o próximo artigo tratará de como usar programação por restrições na escolha de índices do Postgres

Opinião do GN⁺

• Utilidade da programação por restrições: é extremamente útil para resolver problemas complexos de otimização
• Pontos fortes do CP-SAT: desenvolvido como parte do projeto OR-Tools do Google, o CP-SAT se destaca pelo alto desempenho
• Casos de uso reais: pode ser aplicado a problemas reais, como a geração de escalas de trabalho de funcionários
• Considerações para adoção de tecnologia: ao adotar uma nova tecnologia, é preciso considerar a curva de aprendizado e os desafios de integração com sistemas existentes
• Recomendação de projetos semelhantes: solvers comerciais como IBM CPLEX e Gurobi também oferecem funcionalidades semelhantes

[GN⁺]

Comentários do Hacker News

• Já usei resolvedores de restrições no passado, e essas ferramentas entregam um desempenho realmente impressionante

  • O problema é que quase não há material para iniciantes
  • A maior parte do material é sobre como resolver Sudoku ou consiste em material de pesquisa altamente técnico
  • Seria ótimo se mais ferramentas capazes de resolver mais problemas fossem mais acessíveis
  • Acessíveis ainda significa que um programador é necessário

• Estou reescrevendo um capítulo curto do meu livro antigo usando MiniZinc e Python

  • MiniZinc é um sistema de programação por restrições
  • Há um bom curso no Coursera que usa MiniZinc

• Muitos programas tentam ter uma única representação de dados, mas isso é irracional na maioria dos casos

  • É preciso muita distorção para fazer algoritmos funcionarem com uma nova representação
  • Sempre sinto falta de vermos conversões de representação com mais frequência
  • Ao converter a representação, é possível obter uma forma muito concisa, o que permite execução mais rápida

• Tenho um cliente que opera um acampamento esportivo

  • As crianças podem solicitar os esportes que querem e amigos
  • Isso cria um problema de agendamento difícil para humanos
  • Construímos um sistema simples usando uma ferramenta de otimização baseada em OR-Tools
  • Agora o agendamento fica pronto com alguns cliques

• Tenho experiência com muitos resolvedores desde o início dos anos 2000

  • Atualmente trabalho com software (web) usando Python
  • Fico feliz em ver uma exploração profunda desse tema
  • Converter restrições em um modelo é 90% do trabalho e a parte mais difícil

• Fico me perguntando se existe algum CAD paramétrico que funcione principalmente com resolvedor de restrições

  • No começo, muitas vezes é incômodo ter de estimar valores de parâmetros com os quais ainda não me importo
  • Em vez disso, eu gostaria de restringir os parâmetros de interesse e otimizar o restante

• Fico me perguntando como isso se compara à programação inteira mista