IA aumentada: entendendo e praticando otimização com OR-Tools

Definindo um modelo de restrições - Apresentação

Olá, pessoal! Meu nome é Guilherme Silveira e sou o instrutor aqui na Alura.

Audiodescrição: Guilherme é uma pessoa de pele clara, cabelos castanho-escuros bem curtos e olhos castanhos. Está usando um headphone com fio e uma camiseta branca com estampa amarela e preta. Ao fundo, um ambiente com iluminação verde decorado com enfeites, plantas e uma placa azul neon da Alura.

Vamos passar juntos por um problema clássico que encontramos em aeroportos, mas que também aparece em diversas outras áreas do nosso dia a dia.

Vamos imaginar que temos cinco aviões pousando, mas apenas três lugares disponíveis para eles pousarem. Qual avião deve pousar em qual estacionamento, de forma a minimizar o custo operacional do aeroporto? Como minimizar o tempo que o avião fica no solo e o tempo de deslocamento dos passageiros entre o ponto de chegada e o ponto de saída? Como vamos gerenciar tudo isso?!

Primeiro, precisamos parar e pensar, pois este é um problema de encaixe de fatores.

Cada um desses aviões tem características específicas, como o número de passageiros, se estes precisarão de verificação de passaporte ou não, se são grandes ou pequenos.

Além disso, os estacionamentos têm suas características: estão próximos ou distantes do ponto de controle de passaporte, suportam aviões grandes ou não? Há outras regras em relação a eles?

Ou seja, temos diversas restrições que devemos aplicar ao nosso problema.

Quando modelarmos isso no código, criando um modelo que configure tudo isso para nós, precisamos considerar que o pior caso seria um programa que tenta todas as possibilidades manualmente. Por exemplo, tentar o avião 1 no estacionamento 1, avião 2 no estacionamento 2, avião 3 no estacionamento 3 e verificar se todas as regras são atendidas. Depois, tentar outras combinações e seguir testando até encontrar uma solução.

Essa é uma abordagem muito ingênua e simples, que pode até funcionar, mas demora uma eternidade.

Existem ferramentas de pesquisa operacional que fazem esse trabalho de forma mais inteligente, utilizando algoritmos comprovados pela teoria que convergem para uma solução do problema, muitas vezes sem precisar explorar todo o espaço de possibilidades. Precisamos tentar caminhos que nos levem a uma solução mais rápida.

Este é um problema complexo do ponto de vista computacional, um desafio clássico de combinatória na matemática e computação. Vamos usar essas ferramentas e aprender a pensar de forma mais matemática sobre esses problemas, para podermos programá-los e encontrar soluções.

Vamos adicionar diversas restrições e encontrar a solução ótima, não apenas para o exemplo do aeroporto, mas isso também poderia ser aplicado para alocar professores em turmas numa universidade, por exemplo, ou decidir a ordem de retirada de contêineres de um navio, ou qualquer problema que envolva várias combinações e sequências de ações.

Nos encontramos na próxima aula.

Até!

Definindo um modelo de restrições - Restrições simples

Olá, pessoal! Vamos começar com o código para resolver nossos problemas. Primeiramente, o ambiente de desenvolvimento que utilizaremos é o Google Colab, suficiente para criarmos os diversos experimentos que faremos. Porém, se desejarem, vocês podem usar outras ferramentas, seus próprios computadores locais, e assim por diante.

No Colab, clicaremos em "Novo bloco de notas" no canto inferior esquerdo da janela "Abrir notebook" inicial. Assim, começaremos nosso próprio notebook (bloco de notas), onde escreveremos nosso código em Python.

Desenhando nosso problema

Agora, vamos pensar em qual é nosso problema. Para isso, vamos abrir uma planilha (no Excel ou Google Planilhas) chamada "Aeroporto".

Nosso problema inicial é que temos alguns aviões que vão pousar no nosso aeroporto. São cinco aviões, numerados de 1 a 5. E, no nosso aeroporto, um aeroporto pequeno, temos apenas um ponto de estacionamento. Em English (inglês), é esse ponto se chama stand, portanto usaremos esse termo às vezes. Dessa maneira, a variável estacionamento1 pode ter um desses cinco valores: 1, 2, 3, 4, 5.

Vocês podem pensar que é muito simples resolver isso.

No Google Colab, poderíamos escrever estacionamento1 = 3, ou seja, o avião 3 pousará nesse estacionamento. Mas isso não é suficiente.

Não podemos, nós, pessoas humanas, calcular mentalmente todas as restrições de um aeroporto, considerando as características de cada avião e estacionamento, e simplesmente escrever a solução. Precisamos, na verdade, informar ao nosso programa as restrições existentes.

A variável estacionamento1 precisa ser maior que zero e menor que 6. No entanto, não seremos nós a atribuir valor a essa variável, pois é muito complexo fazer isso para um aeroporto.

Essa é uma forma inicial de desenhar nosso problema: queremos uma variável cujo valor não seja atribuído em tempo de digitação, compilação e etc., mas apenas em execução, pois a ferramenta calculadora calculará esse valor para nós, de forma otimizada.

Mas, como essas ferramentas resolverão isso por nós?

Importando as ferramentas

Já definimos uma variável. Agora, precisamos importar a ferramenta de operações e pesquisa escolhida para este curso, chamada OR-Tools do Google.

Para importá-la, abrimos uma nova primeira célula no nosso notebook do Colab e executamos o comando !pip install ortools na versão atual, 9.7.2996. Ela também precisa do Pandas na versão 2.1.0:

!pip install ortools==9.7.2996 pandas==2.1.0

Pressionamos "Shift + Enter" para executar esses comandos. Pode ser que o Colab exiba uma mensagem de erro na saída, mas ainda dirá se a operação foi bem sucedida.

Agora, vamos começar a trabalhar com definição de variável. Para isso, numa nova célula do notebook, vamos importar a biblioteca do OR-Tools: from ortools.sat.python (SAT é um método para resolver esse tipo de problema), import cp_model. O CP Model é o modelo que cria restrições (constraints) nas nossas variáveis.

from ortools.sat.python import cp_model

Criando nosso modelo

Agora, vamos criar nosso modelo, dentro da variável modelo. Ele será igual a cp_model.CpModel(), instanciando esse módulo do Python.

modelo = cp_model.CpModel()

Criado o modelo, vamos definir a variável estacionamento1 como uma nova variável de tipo inteiro (NewIntVar()), com limites entre 1 e 5 (maior e menor valor), do modelo.

Quando criamos uma variável inteira, precisamos dar um nome para ela. Você pode até pensar "mas nós já demos uim nome para ela, estacionamento1!". Isso é verdade, mas esse nome vale apenas para nós. Precisamos fornecer um nome dessa variável para a biblioteca, como parâmetro de NewIntVar(). O nome será também 'estacionamento1':

estacionamento1 = modelo.NewIntVar(1, 5, 'estacionamento1')

Após fazer isso, para resolver esse problema, precisamos pegar um solucionador, dentro da variável solucionador, com o método CpSolver() do pacote cp_model:

solucionador = cp_model.CpSolver()

Agora, pediremos ao solucionador para resolver esse problema com o método .Solve(), passando o modelo como parâmetro. Ele nos retornará uma situação, ou seja, um status:

status = solucionador.Solve(modelo)

Então, podemos imprimir (print()) o status, com solucionador.StatusName(), passando o nome do status como parâmetro.

print(solucionador.StatusName(status))

Ao executar todos esses códigos, recebemos a seguinte saída:

OPTIMAL

Ou seja, o solucionador encontrou uma solução ótima que resolve o problema do estacionamento 1! Mas, qual é esse valor?

Vamos imprimir o valor da variável estacionamento1 com o método solucionador.Value(), para verificar a solução encontrada.

print(solucionador.Value(estacionamento1))

Ao rodar esse código, temos a saída:

OPTIMAL

1

O valor é 1!

Mas, e se não fosse possível esse valor 1, será que ele funcionaria? Vamos tentar, mudando o limite da variável estacionamento1 para 3, 5, ou seja, valor mínimo de três:

modelo = cp_model.CpModel()

estacionamento1 = modelo.NewIntVar(3, 5, 'estacionamento1')
solucionador = cp_model.CpSolver()
status = solucionador.Solve(modelo)
print(solucionador.StatusName(status))
print(solucionador.Value(estacionamento1))

Ao rodar, recebemos "OPTIMAL: 3" na saída.

Então, ele coloca sempre o menor valor possível? Não dá para garantir isso com a forma que rodamos esse modelo, pois não adicionamos essa garantia, o valor é aleatório.

Para demonstrar, podemos adicionar outras restrições.

Adicionando mais restrições ao modelo

Após criar a variável estacionamento1, podemos dizer "modelo, adicione mais uma restrição" com o método Add(). Essa restrição pode ser, por exemplo, que o estacionamento1 não seja igual a 1:

modelo.Add(estacionamento1 != 1)

Ao rodar, recebemos na saída: "OPTIMAL: 2". Ou seja, nossa restrição funcionou.

Outra restrição pode ser: estacionamento1 deve ser maior que 4. Isso deve restringir as possibilidades apenas para o número 5.

modelo.Add(estacionamento1 > 4)

Ao rodar, de fato, recebemos na saída: "OPTIMAL: 5".

Se adicionarmos uma restrição impossível, como modelo.Add(estacionamento1 > 10), o modelo será inviável e devolverá a saída "INFEASIBLE" em vez de "OPTIMAL". Ou seja, não é possível chegar a uma solução com essa restrição.

Então, vamos tirar essa linha do nosso modelo. No entanto, não conseguiremos executá-lo novamente porque a variável modelo já foi instanciada anteriormente, já com todas essas restrições.

Nesse caso, vamos ao menu superior do Colab e clicamos em "Tempo de execução > Reiniciar e executar tudo". A saída, considerando a restrição final, é "OPTIMAL: 5" novamente. Ou seja, a solução ótima é 5.

A partir dessas variáveis e restrições, conseguiremos criar um aeroporto complexo com várias regras (opção mais econômica, com menos atraso, etc.) que seríamos incapazes de calcular manualmente para encontrar a melhor solução.

No próximo vídeo, começaremos a trabalhar com versões mais complexas do nosso modelo.

Até lá.

Definindo um modelo de restrições - Restrições condicionais

Adicionamos três restrições para o estacionamento1 e descobrimos, claro, que a terceira não era possível implementar:

estacionamento1 = modelo.NewIntVar(1, 5, 'estacionamento1')

modelo.Add(estacionamento1 != 1)
modelo.Add(estacionamento1 > 4)
# modelo.Add(estacionamento1 > 10)

Adicionando um estacionamento

Vamos colocar dois estacionamentos agora, adicionando estacionamento2, apenas para verificar que o cálculo também funciona com duas variáveis.

Lembrando que são duas variáveis do Python (Python), mas, acima disso, são duas variáveis do nosso modelo matemático, por isso recebem modelo.NewIntVar().

Nossa variável do modelo matemático de números inteiros terá valores entre 1 e 5, e será chamada de estacionamento2. Então, teremos:

estacionamento1 = modelo.NewIntVar(1, 5, 'estacionamento1')
estacionamento2 = modelo.NewIntVar(1, 5, 'estacionamento2')

Esse modelo matemático não está adicionando mais nenhuma restrição para a variável estacionamento2, mas no final também vamos imprimir o valor dela, com print(solucionador.Value(estacionamento2)):

solucionador = cp_model.CpSolver()
status = solucionador.Solve(modelo)
print(solucionador.StatusName(status))
print(solucionador.Value(estacionamento1))
print(solucionador.Value(estacionamento2))

Vamos executar primeiro a célula de definição do modelo (modelo = cp_model.CpModel()) do zero e depois executar os cálculos novamente. Como resposta, temos:

Saí****da

OPTIMAL
5
1

O solucionador colocou o avião 5 no primeiro estacionamento e o avião 1 no segundo estacionamento, pois não havia nenhuma restrição.

Ou seja, podemos criar diversas variáveis e trabalhar com elas. Maravilha!

Mas você pode pensar: o o estacionamento 1 não pode ser maior que 10, mas o estacionamento 2? Pode ser maior do que 10?

Não faz sentido que o estacionamento 2 seja maior do que 10, pois ele também está restrito, com um constraint (restrição) entre 1 e 5, então dá o mesmo erro. Não é viável uma solução para esse modelo.

Soft constraint (restrição leve)

Mas, e se quiséssemos colocar uma regra do tipo "se possível, atenda a nossa demanda"?

Por exemplo, em um aeroporto, temos dois aviões pousando e dois pontos de estacionamento, que preferimos não utilizar ao mesmo tempo. Então, se possível, o modelo não deve usar os dois pontos ao mesmo tempo. Mas, claro, se o avião estiver sem combustível, ou em uma situação de emergência, é para usar os dois simultaneamente.

Ou seja: existem situações em que gostaríamos de impor uma restrição, se possível. Temos um certo prejuízo e um certo risco envolvidos em utilizar o mesmo ponto para dois aviões simultaneamente, então, gostaríamos que isso não acontecesse; porém, é possível que aconteça.

Ou seja, trata-se de uma restrição, mas uma restrição suave. Chamamos isso de soft constraint, que é uma restrição mais leve, flexível.

Como adicionamos, então, essa restrição branda para o estacionamento 2? Não podemos simplesmente impor como fizemos nas outras, porque isso seria uma restrição rígida. Sendo assim, usaremos uma palavra mencionada anteriormente: bônus.

Se o estacionamento 2 for um número menor do que 10, teremos um certo prejuízo, pois preferíamos que não fosse assim. Se for um valor maior que 10, temos um certo bônus, pois atende todas as nossas demandas, inclusive as opcionais.

Então, como fazemos isso? Criamos um bonus e ele só ocorrerá se o estacionamento tiver um valor maior do que 10.

Esse bonus será uma nova variável modelo.NewIntVar(). A variável será de dois valores, sem bônus ou com bônus, isto é, 0 ou 1, respectivamente — poderia ser 0 ou 1000, 0 ou 1000000, de fato; mais tarde no curso, trabalharemos com outros tipos de bônus. Chamaremos essa variável de, claro, 'bonus'.

bonus = modelo.NewIntVar(0, 1, 'bonus')

Com essa variável bonus, poderemos dizer: se o estacionamento 2 for maior do que 10, ótimo, esse é o caso em que temos bônus. Então, se o bonus for 1, gostaríamos de adicionar essa condição ao modelo (estacionamento 2 maior que 10):

bonus = modelo.NewIntVar(0, 1, 'bonus')
if bonus==1
modelo.Add(estacionamento2 > 10)

Você pode dizer: "mas você não tem um valor 1 no bonus, pois não é uma variável inteira, mas uma variável do modelo". De fato, são variáveis do modelo; não é como estacionamento1 = 5, por exemplo; não existe isso. Não existem condicionais if bonus===1 no código solto, não é assim que programamos. Então vamos apagar essa linha.

Estamos instruindo o modelo, então, temos que programá-lo para entender que, se bonus for 1, adicionamos essa restrição. Então adicionamos depois da restrição: .If(bonus==1); desse modo, se bonus for igual a 1, adicionaremos a restrição que vem antes.

No entanto, o método correto não é if, é OnlyEnforceIf (somente reforçar se); então, somente se o bônus for 1. Isso equivale a usar apenas a palavra bonus, pois significa que o valor é 1. Então:

bonus = modelo.NewIntVar(0, 1, 'bonus')
modelo.Add(estacionamento2 > 10).OnlyEnforceIf(bonus)

Então, se bonus for 1, restringimos que o nosso estacionamento deve ser maior do que 10. Isso significa que, se o estacionamento for maior do que 10, teremos um bônus; o que é uma possibilidade, mas ainda não é garantido.

Isso porque precisamos garantir o contrário: quando colocamos a regra de que o estacionamento é menor do que 10? Quando não temos bônus! Então, agora, usamos a negação Not(), que verificará se o valor de bonus é zero.

bonus = modelo.NewIntVar(0, 1, 'bonus')
modelo.Add(estacionamento2 > 10).OnlyEnforceIf(bonus)
modelo.Add(estacionamento2 <= 10).OnlyEnforceIf(bonus.Not())

Vamos entender o que estamos restringindo, de baixo para cima. Se o bônus for zero, adicionamos a restrição de que o estacionamento 2 deve ser menor ou igual a 10. Se o bônus for 1, então adicionamos uma restrição de que o estacionamento 2 deve ser maior do que 10. Então, adicionamos uma variável bonus.

Agora vamos dizer ao modelo: por favor, maximize nosso bônus: modelo.Maximize(bonus). O que significa maximizar o bônus? Colocar o maior valor possível para bônus, que é 1.

Se o modelo conseguir colocar 1, o que acontece? Restringe o estacionamento para ser maior do que 10. Se não conseguir, tudo bem. Estamos pedindo para maximizar, se não for possível, tudo bem; o estacionamento 2 será menor do que 10.

É assim que trabalhamos para conseguir uma restrição opcional. Criamos uma variável de "bônus", ou de "pênalti". No caso do bônus, dizemos que queremos maximizá-lo; no caso da penalidade, minimizá-la.

Assim, temos a restrição desejada se tivermos o bônus; se não tivermos o bônus, não temos a restrição desejada, que é opcional. Dessa forma, fornecemos duas opções. Como indicamos qual das duas opções queremos? Dizemos para maximizar, então o modelo dará preferência para a maior delas.

Vamos tentar executar novamente. O resultado é 5 e 1, porque ainda não é possível executar essas restrições - afinal, não temos dez aviões.

Então, vamos recortar a célula de cima, em que declaramos o modelo, e colocar dentro da célula abaixo, para poder rodar tudo de uma vez:

modelo = cp_model.CpModel()

estacionamento1 = modelo.NewIntVar(1, 5, 'estacionamento1')
estacionamento2 = modelo.NewIntVar(1, 5, 'estacionamento2')

modelo.Add(estacionamento2 !=1)
modelo.Add(estacionamento2 > 4)

bonus = modelo.NewIntVar(0, 1, 'bonus')
modelo.Add(estacionamento2 > 10).OnlyEnforceIf(bonus)
modelo.Add(estacionamento2 <= 10).OnlyEnforceIf(bonus.Not())

modelo.Maximize(bonus)

solucionador = cp_model.CpSolver()
status = solucionador.Solve(modelo)
print(solucionador.StatusName(status))
print(solucionador.Value(estacionamento1))
print(solucionador.Value(estacionamento2))

Executando esse código, temos 5 e 1 como resultado novamente. Agora vamos copiar tudo isso, no notebook, e colar na célula abaixo. Por quê?

Porque agora vamos dizer que o estacionamento 2 pode ser de 1 a 50, ou seja, temos 50 aviões voando.

estacionamento1 = modelo.NewIntVar(1, 5, 'estacionamento1')
estacionamento2 = modelo.NewIntVar(1, 50, 'estacionamento2')

Ao rodar o código agora, o solucionador coloca o avião 11 no estacionamento 2. Isso aconteceu porque ele tentou colocar um valor maior do que 10, ao tentar colocar a variável bônus com o maior valor possível.

Você pode pensar: "mas será que ele colocou o valor 1 na variável bonus?". Vamos verificar imprimindo o valor de nonus junto das outras impressões:

print(solucionador.StatusName(status))
print(solucionador.Value(estacionamento1))
print(solucionador.Value(estacionamento2))
print(solucionador.Value(bonus))

Executando novamente, temos a seguinte saída:

OPTIMAL
5
11
1

O avião 5 está no estacionamento 1, o avião 11 está no estacionamento 2 e o bônus tem valor 1. Antes, quando ele não conseguia calcular a restrição, o bonus era 0.

Conclusões e adendos

A ideia é essa: criar uma variável extra que vai trabalhar uma penalidade, ou um bônus, conforme nossa restrição opcional. Se atingir, ótimo; se não atingir, tudo bem também.

Um detalhe que algumas pessoas podem estar se perguntando agora é: por que os métodos estão em letra maiúscula no código? No Python (Python), o padrão é o método que chamamos estar em letra minúscula.

Acontece que esse código vem de bibliotecas de C, C++, etc., cujo padrão era em letra maiúscula. Então, elas são apenas uma camada em cima dessa biblioteca, e mantiveram o mesmo padrão.

Com isso, entendemos ser possível trabalhar com mais de uma variável, incluindo restrições opcionais, que serão importantes para nós.

Até a próxima!

Sobre o curso IA aumentada: entendendo e praticando otimização com OR-Tools

O curso IA aumentada: entendendo e praticando otimização com OR-Tools possui 110 minutos de vídeos, em um total de 40 atividades. Gostou? Conheça nossos outros cursos de Machine Learning em Data Science, ou leia nossos artigos de Data Science.

Matricule-se e comece a estudar com a gente hoje! Conheça outros tópicos abordados durante o curso:

• Definindo um modelo de restrições
• Analisando combinações de restrição
• Garantindo o pouso de todos os aviões
• Utilizando orientação a objetos
• Restringindo condições do próprio modelo