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

 (pganalyze.com)
1 pontos por GN⁺ 2024-07-05 | 1 comentários | Compartilhar no WhatsApp
  • Programação por restrições (CP) é uma abordagem declarativa para modelar problemas de otimização discreta por meio de variáveis, domínios e restrições, em vez de código procedural, deixando que o solver encontre uma solução que satisfaça as condições
  • O núcleo do modelo são as variáveis, que representam os valores a encontrar; os domínios, que definem a faixa de valores possíveis; e as restrições, que limitam as relações entre variáveis. Se necessário, também é possível usar uma função objetivo para escolher uma solução melhor
  • O exemplo da divisão do custo de balas entre Alice, Bob e Carol mostra como alldifferent, maximum e minimize permitem evoluir de uma solução válida para uma solução mais equilibrada
  • O exemplo prático usa o solver open source CP-SAT do Google OR-Tools com Python para montar uma escala semanal de trabalho com 4 funcionários, 7 dias, 3 turnos e 2 funções
  • Ao mesmo modelo, é possível adicionar gradualmente condições como limite semanal de 40 horas, horário de aulas, combinações de pessoas que não podem trabalhar juntas, distribuição equilibrada dos turnos de fim de semana, pedidos de folga e minimização da diferença no número de turnos

Forma básica de pensar em programação por restrições

  • Programação por restrições (CP) é um paradigma declarativo para resolver problemas de otimização discreta
  • Na programação imperativa, escreve-se passo a passo o procedimento para chegar ao resultado; na abordagem declarativa, descrevem-se as condições do resultado desejado e o sistema de execução encontra esse resultado
  • No exemplo de obter a lista de adultos, o código imperativo percorre a lista de pessoas verificando Age >= 18, enquanto o SQL declarativo expressa diretamente a condição, como em SELECT person_name FROM people WHERE age >= 18;
  • Em CP, o resultado desejado também é descrito como um modelo, cujos elementos centrais são variáveis, domínios e restrições
    • Variáveis indicam o que se quer encontrar
    • Domínios são o conjunto de valores que uma variável pode assumir
    • Restrições limitam as relações entre variáveis

Variáveis, domínios, restrições e função objetivo

  • Uma solução é uma atribuição em que cada variável assume um valor dentro do seu domínio e todas as restrições são satisfeitas
  • O exemplo do custo das balas trata do problema em que Alice, Bob e Carol, cada um com no máximo 20 dólares, juntam dinheiro para comprar balas que custam 50 dólares
    • As variáveis a, b e c são os valores pagos por cada pessoa
    • O domínio das três variáveis é {0, ..., 20}
    • a + b + c == 50 faz o total bater
    • a >= b garante que Alice pague pelo menos o mesmo que Bob
    • c % 5 == 0 restringe o valor de Carol a múltiplos de 5
    • Para impedir que duas pessoas paguem o mesmo valor, podem ser usadas a != b, a != c e b != c
  • Condições que envolvem várias variáveis podem ser expressas como restrições globais (global constraints), e alldifferent(a, b, c) faz com que as três variáveis tenham valores distintos
  • O solver recebe o modelo e retorna uma solução válida
    • A solução de exemplo a = 19, b = 11, c = 20 satisfaz todas as restrições
    • Mas como Carol paga quase o dobro de Bob, pode existir uma solução mais equilibrada
  • A função objetivo minimiza ou maximiza uma expressão específica entre as soluções que satisfazem as restrições
    • Uma nova variável x representa a maior contribuição, usando maximum(x, [a, b, c])
    • Ao aplicar minimize: x, obtém-se a = 18, b = 17, c = 15, x = 18
    • A diferença entre a maior e a menor contribuição cai de 9 dólares para 3 dólares

Criando um modelo de escala com CP-SAT e Python

  • O exemplo prático trata da geração de uma escala semanal de trabalho para uma pequena loja
    • A loja abre todos os dias das 8h às 20h
    • Cada dia tem três turnos: Morning, Afternoon e Evening, com 4 horas cada
    • Há duas funções: Cashier e Restocker
    • Os funcionários são Phil, Emma, David e Rebecca
  • CP-SAT é um solver de CP open source incluído no OR-Tools do Google
  • Um modelo vazio é criado com cp_model.CpModel() de ortools.sat.python
  • As funções possíveis para cada funcionário são as seguintes
    • Phil: Restocker
    • Emma: Cashier, Restocker
    • David: Cashier, Restocker
    • Rebecca: Cashier
  • A escala é representada por variáveis booleanas que combinam funcionário, função, dia da semana e turno
    • schedule["Emma"]["Restocker"]["Monday"]["Evening"] vale 1 se Emma trabalhar como Restocker no turno da noite de segunda-feira, e 0 caso contrário
    • model.new_bool_var() cria uma variável com domínio {0, 1}

Restrições básicas da escala

  • Como é necessário exatamente um caixa em todos os horários, para cada dia e turno a soma da função Cashier deve ser 1
  • Como o responsável por reposição é necessário em apenas um turno por dia, a soma total da função Restocker em cada dia é 1
  • Para evitar que o turno Evening de reposição de um dia seja seguido pelo turno Morning de reposição no dia seguinte, restringe-se a soma das duas atribuições a no máximo 1
  • Um funcionário não pode assumir duas funções ao mesmo tempo no mesmo turno, então a soma das funções por funcionário, dia e turno deve ser no máximo 1
  • Para impedir atribuições a funções não qualificadas, todas as variáveis de funções que o funcionário não pode exercer são fixadas em 0
  • O máximo diário de trabalho é 8 horas, ou seja, 2 turnos
    • Se Morning e Evening forem atribuídos no mesmo dia, surge um intervalo ocioso de 4 horas durante o Afternoon
    • Ao restringir a soma das atribuições de Morning e Evening por funcionário e por dia a no máximo 1, evita-se ao mesmo tempo exceder 2 turnos diários e criar esse intervalo ocioso no meio do dia

Execução do solver e resultado inicial

  • Ao resolver o modelo, cria-se um cp_model.CpSolver() e chama-se solver.solve(model)
  • Depois de obter a solução, os valores das variáveis em schedule são lidos com solver.value(...)
  • A escala inicial satisfaz todas as restrições básicas, mas Rebecca acaba recebendo 14 turnos na semana
  • Para evitar horas extras, adiciona-se a restrição de no máximo 40 horas semanais por funcionário, ou seja, 10 turnos
  • Phil é estudante em tempo integral, então trabalha exatamente 4 turnos por semana e não pode trabalhar em Morning nem Afternoon nos dias úteis por causa das aulas
  • Para impedir que Phil e Emma trabalhem no mesmo turno, a soma das atribuições dos dois em cada dia e turno é limitada a no máximo 1
  • Como ninguém gosta de trabalhar no fim de semana, adiciona-se a restrição de distribuir os 8 turnos totais de sábado e domingo em 2 turnos para cada um dos quatro funcionários

Status da solução: OPTIMAL, INFEASIBLE, FEASIBLE, UNKNOWN

  • O solver recebe o modelo e retorna um status junto com a solução
  • OPTIMAL significa que foi encontrada uma solução para a qual não existe solução melhor
    • Por exemplo, se x + y >= 5 e o objetivo é minimizar x + y, então (x, y) = (5, 0) é uma solução ótima
    • (x, y) = (3, 2) também pode ser ótima, pois tem o mesmo valor objetivo
  • INFEASIBLE significa que não há como atribuir valores às variáveis de forma a satisfazer as restrições
    • Por exemplo, se x ∈ {0, ..., 10} mas é exigido x >= 15, isso é impossível
  • Quando o solver é interrompido por limite de tempo devido ao tamanho do problema ou à complexidade da função objetivo, podem surgir dois status
    • FEASIBLE: foi encontrada uma solução que satisfaz as restrições, mas não se sabe se ela é ótima
    • UNKNOWN: nenhuma solução foi encontrada, e também não se sabe se existe ou não uma solução

Pedido de folga e distribuição justa

  • Se for adicionada a restrição de que Emma quer folgar de segunda a sexta, o status do solver passa a ser INFEASIBLE
    • Isso acontece porque não é possível preencher a escala sem violar outras restrições
  • Se a condição for alterada para Emma folgar apenas de segunda a quarta, a escala volta a ser viável
    • Phil trabalha exatamente 4 turnos, como desejado
    • Emma fica com 6 turnos, David com 10 e Rebecca com 8
  • Para equilibrar melhor a quantidade de turnos entre Emma, David e Rebecca, adiciona-se uma função objetivo
    • Cria-se uma variável inteira total_shifts para representar o número total de turnos de cada funcionário
    • model.new_int_var(0, 10, ...) cria uma variável inteira com valores de 0 a 10
    • Como Phil é part-time, ele é excluído, e model.add_min_equality(...) e model.add_max_equality(...) são usados para acompanhar o menor e o maior número de turnos
    • model.minimize(max_shifts - min_shifts) minimiza a diferença entre o maior e o menor número de turnos
  • O resultado final é Phil com 4 turnos, Emma com 6, David com 9 e Rebecca com 9
    • Emma fica com 6 turnos porque folga 3 dias
    • David e Rebecca recebem a mesma carga, com 9 turnos cada

Código de exemplo e próximo tema

  • Esse modelo gera uma escala que atende ao mesmo tempo às necessidades do dono da loja e dos funcionários
  • É possível continuar adicionando restrições ao mesmo modelo de CP para verificar se os pedidos são viáveis e, entre as soluções possíveis, usar a função objetivo para encontrar uma distribuição mais justa
  • O código de exemplo está disponível no pganalyze GitHub
  • O tema do próximo texto é como usar programação por restrições na escolha de índices no Postgres

Leituras relacionadas

1 comentários

 
GN⁺ 2024-07-05
Opiniões no Hacker News

  • Já usei resolvedores de restrições no passado, e o que eles conseguem fazer parece mesmo mágica. O problema é que não há muito material bom para iniciantes
    A maior parte é resolver Sudoku (o Hello World dessa área) ou literatura de pesquisa primária altamente técnica, voltada só para especialistas do domínio
    O que é uma pena, porque, se essas ferramentas se tornassem mais acessíveis, acho que poderiam resolver uma quantidade enorme de problemas. E, aqui, "acessíveis" ainda significa que é preciso haver um programador; moldar um problema em uma DSL de restrições não é algo que a maioria das pessoas consiga fazer bem

    • Acho que o motivo de essas ferramentas não serem acessíveis o suficiente é que a maioria dos resolvedores é baseada em programação inteira mista (MIP), então é preciso escrever o domínio como equações matemáticas. Para isso, o usuário precisa conhecer tanto o domínio quanto a matemática para conseguir escrever as restrições corretamente
      Mas MIP não é tudo que existe em resolvedores. Também há resolvedores de restrições baseados em busca local, e essa abordagem não impõe a limitação de modelar todas as restrições como relações ou equações entre variáveis inteiras
      Em resolvedores de busca local, as restrições em geral são tratadas como uma caixa-preta que informa quão boa é uma determinada solução. Por isso, é difícil garantir a solução ótima sem testar todas as soluções possíveis, mas eles costumam encontrar soluções quase ótimas em um tempo razoável
      O Timefold Solver é um desses resolvedores baseados em busca local. O usuário anota o domínio para que o resolvedor saiba quais são as variáveis e os valores possíveis. Assim, as restrições lidam com Shift e Employee em vez de int, e também podem acessar seus métodos
      Divulgação: trabalho no Timefold Solver
    • É exatamente isso. A sintaxe ou API real dos resolvedores de restrições é tão simples que dá para aprender rapidamente. A parte que realmente exige tempo e conhecimento especializado é modelar o problema dessa forma, e quase não há exemplos de escala e complexidade reais para consultar
      Tenho cerca de 5 anos de experiência resolvendo problemas de escalonamento com MiniZinc, mas, infelizmente, todo esse código é privado e nunca será publicado como open source
      Gostaria de criar um exemplo completo de programação por restrições, incluindo conteinerização, visualização e modelagem, mas o obstáculo é encontrar um problema que valha a pena resolver de verdade e que tenha dados open source utilizáveis
    • Concordo que a redução (reduction) é muito mais difícil do que a teoria em si. "SAT/SMT by Example", de Dennis Yurichev (https://smt.st/), é um bom material sobre esse tema, mas é bem intimidador
    • A afirmação de que “a maioria dos materiais é sobre resolver Sudoku ou literatura de pesquisa para especialistas do domínio” é precisa. Tentei usar um resolvedor SAT em um motor de regras e não fazia a menor ideia de como aplicá-lo
      Depois de bastante dedução, consegui montar uma prova de conceito básica, mas não consegui escalá-la até o nível de que eu realmente precisava. A distância entre uma implementação de brinquedo e algo mais substancial era enorme
    • Programo há muito tempo, embora esteja meio enferrujado agora. No ano passado, criei um otimizador de times de futebol com o OR-Tools do Google, com restrições opcionais como jogar junto com um amigo e condições como equilibrar o nível de habilidade entre os times
      Um LLM ajudou a me levar rapidamente na direção mais ou menos certa. Hoje ele ainda falha em acertar exatamente, mas ajudou o suficiente para que eu pudesse completar o restante por conta própria

  • O ponto central de tudo isso é aprender a modelar algo em uma forma que possa ser enviada ao resolvedor. Depois disso, vem descobrir como representar a solução produzida de um modo que humanos consigam entender
    O que é uma pena é que a maioria dos programas tenta manter os dados em uma única representação, indo contra esse modo de pensar. Na maioria dos casos, isso não é razoável e gera muitas complicações para adaptar algoritmos à nova representação
    Este texto também toca nesse ponto no começo, ao falar brevemente sobre o estilo declarativo. Sempre me arrependo de meu código não fazer conversões entre representações com mais frequência. Isso permite obter representações muito concisas e, por ficarem mais concisas, ainda traz o benefício duplo de serem mais rápidas
    Claro, sei que isso, no fim das contas, descreve muitos pipelines de dados: uma estrutura em que se passa a maior parte do tempo transformando dados e ramificando-os para vários locais de computação

  • Um livro que escrevi há algum tempo e que estou reescrevendo agora tem um capítulo curto sobre usar MiniZinc em Python: https://leanpub.com/pythonai/read#constraint-programming-wit...
    MiniZinc é um sistema de programação por restrições. Também há um bom curso da Coursera que usa MiniZinc

    • Fiquei curioso se você tem o link do curso da Coursera

  • Depois de estudar econometria, usei bastante resolvedores em um mestrado em pesquisa operacional no início dos anos 2000. Hoje trabalho com software web usando Python, e fico feliz em ver um texto aprofundado sobre este tema
    Gosto desse assunto, e ler o texto trouxe muitas lembranças. Também me fez perceber de novo que traduzir restrições para um modelo (variáveis, estruturas etc.) é 90% do trabalho e a parte mais difícil

    • No mestrado, usei um programa chamado GAMS
      A estrutura da sintaxe é totalmente de formato livre
      https://www.gams.com/latest/docs/UG_GAMSPrograms.html#UG_GAM...
    • LLMs podem ajudar bastante a transformar restrições em um modelo. Eu queria testar um adaptador que convertesse de LLM para modelo de restrições
      Parece um fruto relativamente fácil de colher; fico curioso para saber se outras pessoas também se beneficiariam
    • Acho que a parte mais difícil é fazer o problema rodar de forma minimizada em um ambiente de produção. Leva bastante tempo para escalar e torná-lo robusto a mudanças nos dados

  • Há um cliente que opera um acampamento esportivo infantil. As crianças podem solicitar os esportes que querem praticar e os amigos com quem querem ficar na mesma turma.
    Por causa disso, surgiu um problema de escalonamento difícil de resolver manualmente, e antes algumas semanas de trabalho de pessoas eram gastas nisso todos os anos. Criamos um sistema simples que conecta os dados do cliente a um otimizador baseado no OR-Tools, e agora o escalonamento termina com alguns cliques.

    • Exato. Se você colocar corretamente no sistema os dados, as restrições e a função de utilidade, dá para encontrar muitas soluções boas o suficiente muito rapidamente.
      Sou técnico de uma liga de basquete e há 8 períodos. Nenhum jogador pode jogar 2 períodos ou mais a mais do que qualquer outro jogador. O número de escalações possíveis por jogo, mesmo satisfazendo as restrições de tempo em quadra, é astronomicamente grande.
      Encontrar um conjunto de escalações que satisfaça as restrições é muito fácil, mas encontrar um conjunto ótimo ou quase ótimo é muito difícil. Fica ainda mais divertido quando é preciso levar em conta jogadores que chegam atrasados ou faltam sem avisar.
      *Nem sempre é totalmente viável
    • Um post no blog detalhando como isso foi feito certamente faria enorme sucesso.

  • Fico curioso se existe algum CAD paramétrico que funcione principalmente como um solucionador de restrições.
    Incomoda muito ter que estimar grosseiramente, no início, valores de parâmetros com os quais você não se importa. Seria ótimo poder colocar como restrições os parâmetros de interesse e otimizar o restante.

  • Fico curioso sobre como essa abordagem se compara à programação inteira mista. E quanto a problemas de física?

    • Muitos problemas podem ser formulados das duas formas. MILP sempre tem uma função objetivo, e as restrições são sempre combinações lineares das variáveis de decisão.
      Como o Gurobi é incrivelmente rápido, pode valer a pena forçar o problema a caber em MILP para obter uma solução.
    • O CP-SAT é apenas para inteiros, então acho que não é muito bom para física. Dá para escalar números reais, mas não é tão bom quanto lidar diretamente com ponto flutuante.
      A vantagem do CP-SAT é que ele lida com variáveis e restrições booleanas e inteiras de forma muito mais eficiente do que solucionadores MIP, especialmente em restrições de alto nível como all_different.
    • Imagino que, no geral, sejam parecidos. https://www.amazon.com/gp/product/1107658799/ foi o último livro que li sobre esse tema, e ele aborda muitas das mesmas ideias.
      Em particular, a parte deste texto que tenta minimizar algum valor me parece estar escrevendo diretamente a mesma coisa.