IA aumentada: aprimorando técnicas de otimização em um problema prático

Adicionando restrições ao modelo - Apresentação

Olá, pessoal? Boas-vindas ao curso de IA Aumentada: Otimização na prática da Alura!

Eu sou Guilherme Silveira, instrutor deste curso, no qual vamos aprofundar nosso conhecimento em ferramentas de otimização. Tentaremos resolver um problema do mundo real onde buscamos minimizar algo. Por exemplo, minimizar o custo do uso de aviões em um aeroporto.

Audiodescrição: Guilherme Silveira é uma pessoa de pele clara, olhos castanhos, cabelos castanhos e curtos. Está vestindo uma camiseta "gola V" verde e usando headset preto. O ambiente no qual está sentado tem iluminação entre os tons de verde e azul. Ao fundo, uma prateleira com um vaso de plantas e uma placa neon onde está escrito "Alura".

Precisamos que os aviões pousem e estacionem, mas também precisamos minimizar o custo envolvido para que nossos passageiros saiam de uma posição e voem até outra, onde precisam passar pelo controle de passaporte ou pegar suas bagagens.

Temos que minimizar o custo dos ônibus que transportam passageiros quando o estacionamento é um ponto remoto, assim como o custo de colocar aviões com controle de passaporte ou sem controle.

São várias questões a serem trabalhadas, ou seja, restrições que queremos adicionar a um modelo. Vamos modelar este problema, assim como fizemos em um curso anterior, abordando vários tipos de problemas de otimização: minimizar, maximizar ou encontrar uma solução possível.

Modelaremos qualquer um desses tipos de problemas e pediremos para encontrar uma solução, seja minimizando, maximizando ou encontrando uma solução qualquer.

Esse modelo é matemático e isso envolve pensar de forma cada vez mais matemática. Até agora, para resolver esse problema, pensamos de forma computacional, algo com o qual estamos acostumados, que é com variáveis, números inteiros, etc.

Agora vamos pensar mais em matrizes e booleanos, verdadeiros e falsos, restrições que são mais naturais desse tipo de problema e solução.

O objetivo desse curso é aprender a utilizar uma das ferramentas mais famosas, o RTools com o SCP (Simplex Constraint Programming), para resolver esses problemas.

Ao mesmo tempo em que atacamos os problemas dos aviões nos aeroportos para tentar minimizar custos, dando continuidade ao curso anterior, também queremos treinar nossa capacidade de modelar essas situações. Esse é o desafio: ter uma restrição e modelá-la de forma adequada nesse modelo matemático no computador.

É nisso que focaremos aula após aula neste curso.

Até a próxima!

Adicionando restrições ao modelo - Adicionando o controle de passaporte

Tudo bem, pessoal? Vamos começar esse novo curso em que continuamos trabalhando com operações, utilizando o R-Tools para encontrar uma solução ótima para o nosso problema.

Podemos pensar que o problema é de um aeroporto, de encaixar coisas, de calcular muitas opções, mas se trata de um problema matemático, em que o computador calcula as opções e encontra uma solução ótima para o nosso problema. É isso que nós queremos!

Retomando o projeto

Então, retomando o nosso projeto, Aeroporto2 - 1.2, temos um código em que instalávamos as ferramentas, o R-Tools e o Pandas, numa versão específica, que já era boa o suficiente. Criamos uma função para resolver o problema, e ela resolveu o problema.

Também criamos uma função para afirmar que os aviões têm que ser distintos nos estacionamentos. Ou seja, se um avião está parado em um estacionamento, ele não pode estacionar em outro também, ele só estaciona em um estacionamento por vez.

Além disso, colocamos uma restrição de que todo avião tem que estacionar em algum lugar, não pode ficar voando. Se for necessário, por exemplo, que ele voe um pouco mais, temos que modelar essa possibilidade. No nosso caso, o pedido do nosso cliente foi que o plano de estacionamento permitisse que todos estacionem.

Geramos duas classes: Estacionamento e Aviao. Lembrando que o avião pode ser grande ou não, isto é, pode ser pequeno, e o estacionamento também pode ser grande ou não e ter vizinhos. Sendo assim, adicionamos uma restrição extra, que vamos encontrar mais abaixo, que é: os vizinhos estão limitados. Significa que se existe um avião grande, outro avião grande não pode ficar do lado.

Foi com isso que nós acabamos criando os últimos exemplos de modelos para testar e conferir se tudo estava funcionando e encontramos soluções ótimas quando essas soluções existiam.

Aprimorando o modelo: controle de passaporte

Nosso trabalho agora é tornar o modelo cada vez mais interessante, com mais tipos de restrições, com mais dimensões e muitas outras coisas legais, que vamos fazer agora. Para isso, a primeira restrição que vamos trabalhar é a questão de controle de passaporte em aeroportos internacionais.

Algumas das portas de entrada do aeroporto têm controle de passaporte, outras não. Por exemplo, se estamos em São Paulo e está chegando um voo de Salvador, não precisamos controlar o passaporte, então, criamos uma área do aeroporto sem controle de passaporte, em que as pessoas consigam passar direto.

Mas uma pessoa vinda da Alemanha ou de algum país da Europa, por exemplo, precisa passar pelo controle de passaporte. Por isso, criamos uma área do aeroporto com controle de passaporte. Lembrando que esta questão não se limita em separar voos internacionais e nacionais, pois existem acordos entre países, como no Mercosul, em que você só precisa de um certo tipo de documento, não necessariamente o passaporte.

Vamos trabalhar com a ideia de requer passaporte ou não requer passaporte.

Então, se o tipo de acordo é um ou outro, a questão é: precisa de passaporte ou não precisa para esse avião? Um avião vindo de Salvador não precisa de controle de passaporte, então podemos direcionar para onde não precisa. Se precisa de controle de passaporte, tem que ir para onde precisa de controle de passaporte. Não pode ir para onde não tem controle de passaporte. Então, vamos trabalhar com isso.

O primeiro ponto, é: os aviões precisam dizer se requerem controle de passaporte. Então, vamos localizar no código a parte onde definimos a classe Aviao.

class Aviao:
  def __init__(self, k, grande):
    self.k = k
    self.grande = grande

Além de saber se ele é grande ou não, queremos saber se ele requer controle de passaporte.

class Aviao:
  def __init__(self, k, grande, requer_controle_de_passaporte):
    self.k = k
    self.grande = grande
    self.requer_controle_de_passaporte = requer_controle_de_passaporte

A variável requer_controle_de_passaporte é do avião, não é do modelo matemático, é do avião. O avião requer ou não requer: True ou False.

Já no caso do estacionamento, precisamos saber se ele tem controle de passaporte ou não.

class Estacionamento:
  def __init__(self, k, total_de_avioes, grande, modelo, tem_controle_de_passaporte):
    self.grande = grande
    self.tem_controle_de_passaporte = tem_controle_de_passaporte
    self.variavel = modelo.NewIntVar(0, total_de_avioes, f'estacionamento_{k}')
    self.k = k
    self.vizinhos = []
    self.recebe_aviao_grande = modelo.NewBoolVar(f'recebe_aviao_grande_{k}')
    if not self.grande:
      modelo.Add(self.recebe_aviao_grande == 0)

Então, nos dois inicializadores, nos dois construtores dessas classes, colocamos se o estacionamento tem controle de passaporte, sim ou não, e se o avião requer controle de passaporte, sim ou não. Qual é o próximo passo?

Vamos localizar um exemplo mais abaixo no código. Quando vamos criar o nosso exemplo, definimos aviões distintos, que todo avião tem que estacionar, limitamos vizinhos, limitamos aviões grandes, mas precisamos de mais que isso.

Temos que limitar os aviões que precisam de controle de passaporte, pois eles não podem ir onde não tem controle de passaporte. Portanto, chamaremos a função limitar_avioes_que_requerem_passaporte e passaremos:

• O modelo;
• Os estacionamentos;
• Os aviões.

O código ficará assim:

avioes = [Aviao(1, False, True),
          Aviao(2, False, False)]
modelo = cp_model.CpModel()
total_de_avioes = len(avioes)

estacionamentos = [Estacionamento(1, total_de_avioes, False, modelo, True),
                   Estacionamento(2, total_de_avioes, False, modelo, False)]

avioes_distintos(estacionamentos, modelo)
todo_aviao_tem_que_estacionar(total_de_avioes, estacionamentos, modelo)
limita_vizinhos(modelo, estacionamentos, avioes)
limita_aviao_grande_para_estacionamento_grande(modelo, estacionamentos, avioes)
limitar_avioes_que_requerem_passaporte(modelo, estacionamentos, avioes)

solucionador = cp_model.CpSolver()
resolve(solucionador, modelo, estacionamentos, avioes)

Agora, criaremos um nova célula de código, def limitar_avioes_que_requerem_passaporte( ) que recebe modelo, estacionamentos, avioes, que são os objetos, listas de objetos em Python.

def limitar_avioes_que_requerem_passaporte(modelo, estacionamentos, avioes)

Precisamos saber quais são os aviões que requerem controle de passaporte. Então, queremos saber quais aviões precisam de controle.

def limitar_avioes_que_requerem_passaporte(modelo, estacionamentos, avioes)
    avioes_com_controle = 

Para trabalhar com os avioes_com_controle, usaremos um for que devolve uma lista. Então, se o avião requer passaporte, vamos devolver o próprio avião.

def limitar_avioes_que_requerem_passaporte(modelo, estacionamentos, avioes):
  avioes_com_controle = [aviao for aviao in avioes if aviao.requer_controle_de_passaporte]
  

Assom, faremos uma lista com todos os aviões que requerem controle de passaporte. Agora, precisamos saber quais são os estacionamentos que não têm controle de passaporte, ou seja, os estacionamentos_sem_controle.

def limitar_avioes_que_requerem_passaporte(modelo, estacionamentos, avioes):
  avioes_com_controle = [aviao for aviao in avioes if aviao.requer_controle_de_passaporte]
  estacionamentos_sem_controle = [estacionamento for estacionamento in estacionamentos if not estacionamento.tem_controle_de_passaporte]
 

Com isto, temos a lista dos estacionamentos sem controle e a lista dos aviões que precisam de controle. Tenho que falar que esse estacionamento não pode ter esse avião. Já fizemos esse trabalho. Ele se resume nestes passos:

• Para cada estacionamento sem controle: for estacionamento in estacionamentos_sem_controle;

• Em aviões com controle: for aviao in avioes_com_controle;

• Adicionamos uma restrição dizendo que a variável do modelo matemático do estacionamento não pode ser esse avião, portanto, tem que ser diferente de aviao: modelo.AddConstraint(estacionamento.variavel != aviao.k).

Em outras palavras, estamos dizendo ao estacionamento que a variável do modelo matemático do estacionamento 1 não pode ter o avião 3, pois ele requer passaporte e o estacionamento não.

def limitar_avioes_que_requerem_passaporte(modelo, estacionamentos, avioes):
  avioes_com_controle = [aviao for aviao in avioes if aviao.requer_controle_de_passaporte]
  estacionamentos_sem_controle = [estacionamento for estacionamento in estacionamentos if not estacionamento.tem_controle_de_passaporte]
  for estacionamento in estacionamentos_sem_controle:
    for aviao in avioes_com_controle:
      modelo.Add(estacionamento.variavel != aviao.k)

Desta forma, vamos adicionar uma centena de restrições dizendo onde o avião não pode estacionar, dependendo do tamanho do modelo, de quantos estacionamentos, quantos aviões. Então, é uma forma razoavelmente simples e direta de falar.

Vamos rodar essa célula e seguir com a criação do modelo. Nosso modelo terá dois aviões e criaremos um exemplo com apenas dois estacionamentos, bem simples, direto ao ponto. Dois estacionamentos e dois aviões.

Além disso, precisamos dizer se algum desses aviões tem necessidade de passaporte, True, e se algum não tem, False. O primeiro tem necessidade e o segundo não. O mesmo vale para o estacionamento, o primeiro avião suporta controle de passaporte, tem controle de passaporte, o segundo não.

avioes = [Aviao(1, False, True),
          Aviao(2, False, False)]
modelo = cp_model.CpModel()
total_de_avioes = len(avioes)

estacionamentos = [Estacionamento(1, total_de_avioes, False, modelo, True),
                   Estacionamento(2, total_de_avioes, False, modelo, False)]

avioes_distintos(estacionamentos, modelo)
todo_aviao_tem_que_estacionar(total_de_avioes, estacionamentos, modelo)
limita_vizinhos(modelo, estacionamentos, avioes)
limita_aviao_grande_para_estacionamento_grande(modelo, estacionamentos, avioes)
limitar_avioes_que_requerem_passaporte(modelo, estacionamentos, avioes)

solucionador = cp_model.CpSolver()
resolve(solucionador, modelo, estacionamentos, avioes)

Testando o modelo

Quer dizer que se executarmos tudo ("Tempo de execução > Executar tudo"), o primeiro avião tem que ir no primeiro estacionamento, ele não pode ir no segundo estacionamento, o primeiro avião no primeiro estacionamento.

avioes = [Aviao(1, False, True),
          Aviao(2, False, False)]
modelo = cp_model.CpModel()
total_de_avioes = len(avioes)

estacionamentos = [Estacionamento(1, total_de_avioes, False, modelo, True),
                   Estacionamento(2, total_de_avioes, False, modelo, False)]

avioes_distintos(estacionamentos, modelo)
todo_aviao_tem_que_estacionar(total_de_avioes, estacionamentos, modelo)
limita_vizinhos(modelo, estacionamentos, avioes)
limita_aviao_grande_para_estacionamento_grande(modelo, estacionamentos, avioes)
limitar_avioes_que_requerem_passaporte(modelo, estacionamentos, avioes)

solucionador = cp_model.CpSolver()
resolve(solucionador, modelo, estacionamentos, avioes)

OPTIMAL

estacionamento_1 tem aviao 1 grande=False

estacionamento_2 tem aviao 2 grande=False

Vamos trocar a ordem para nos certificarmos que o código está correto. Agora, o primeiro avião é False e o segundo é True. Feito isso, o segundo avião tem que ir no primeiro estacionamento.

avioes = [Aviao(1, False, False),
          Aviao(2, False, True)]
modelo = cp_model.CpModel()
total_de_avioes = len(avioes)

estacionamentos = [Estacionamento(1, total_de_avioes, False, modelo, True),
                   Estacionamento(2, total_de_avioes, False, modelo, False)]

avioes_distintos(estacionamentos, modelo)
todo_aviao_tem_que_estacionar(total_de_avioes, estacionamentos, modelo)
limita_vizinhos(modelo, estacionamentos, avioes)
limita_aviao_grande_para_estacionamento_grande(modelo, estacionamentos, avioes)
limitar_avioes_que_requerem_passaporte(modelo, estacionamentos, avioes)

solucionador = cp_model.CpSolver()
resolve(solucionador, modelo, estacionamentos, avioes)

OPTIMAL

estacionamento_1 tem aviao 2 grande=False

estacionamento_2 tem aviao 1 grande=False

Agora vamos criar o caso de dar errado: dois aviões que requerem controle de passaporte. Já que ambos requerem controle de passaporte, não deveria achar solução.

avioes = [Aviao(1, False, True),
          Aviao(2, False, True)]
modelo = cp_model.CpModel()
total_de_avioes = len(avioes)

estacionamentos = [Estacionamento(1, total_de_avioes, False, modelo, True),
                   Estacionamento(2, total_de_avioes, False, modelo, False)]

avioes_distintos(estacionamentos, modelo)
todo_aviao_tem_que_estacionar(total_de_avioes, estacionamentos, modelo)
limita_vizinhos(modelo, estacionamentos, avioes)
limita_aviao_grande_para_estacionamento_grande(modelo, estacionamentos, avioes)
limitar_avioes_que_requerem_passaporte(modelo, estacionamentos, avioes)

solucionador = cp_model.CpSolver()
resolve(solucionador, modelo, estacionamentos, avioes)

INFEASIBLE

Sem solucao

Não achou solução. E se tivermos um com controle de passaporte, dois sem controle de passaporte, então False e False, e três estacionamentos, sendo que só o primeiro requer passaporte e tem suporte a passaporte.

avioes = [Aviao(1, False, True),
          Aviao(2, False, False)],
          Aviao(3, False, False)]
modelo = cp_model.CpModel()
total_de_avioes = len(avioes)

estacionamentos = [Estacionamento(1, total_de_avioes, False, modelo, True),
                   Estacionamento(2, total_de_avioes, False, modelo, False)]
                    Estacionamento(3, total_de_avioes, False, modelo, False)]

avioes_distintos(estacionamentos, modelo)
todo_aviao_tem_que_estacionar(total_de_avioes, estacionamentos, modelo)
limita_vizinhos(modelo, estacionamentos, avioes)
limita_aviao_grande_para_estacionamento_grande(modelo, estacionamentos, avioes)
limitar_avioes_que_requerem_passaporte(modelo, estacionamentos, avioes)

solucionador = cp_model.CpSolver()
resolve(solucionador, modelo, estacionamentos, avioes)

OPTIMAL

estacionamento_1 tem aviao 1 grande=False

estacionamento_2 tem aviao 3 grande=False

estacionamento_3 tem aviao 2 grande=False

Vamos simular mais uma situação? Então, temos três aviões, de novo, o primeiro deles requer controle de passaporte, tem que ir no estacionamento 1. O segundo deles é grande e vamos colocar uma vaga grande no estacionamento 3. Então, ele tem que ir no estacionamento 3. Vamos conferir?

avioes = [Aviao(1, False, True),
          Aviao(2, True, False)],
          Aviao(3, False, False)]
modelo = cp_model.CpModel()
total_de_avioes = len(avioes)

estacionamentos = [Estacionamento(1, total_de_avioes, False, modelo, True),
                   Estacionamento(2, total_de_avioes, False, modelo, False)]
                    Estacionamento(3, total_de_avioes, Trug, modelo, False)]

avioes_distintos(estacionamentos, modelo)
todo_aviao_tem_que_estacionar(total_de_avioes, estacionamentos, modelo)
limita_vizinhos(modelo, estacionamentos, avioes)
limita_aviao_grande_para_estacionamento_grande(modelo, estacionamentos, avioes)
limitar_avioes_que_requerem_passaporte(modelo, estacionamentos, avioes)

solucionador = cp_model.CpSolver()
resolve(solucionador, modelo, estacionamentos, avioes)

OPTIMAL

estacionamento_1 tem aviao 1 grande=False

estacionamento_2 tem aviao 3 grande=False

estacionamento_3 tem aviao 2 grande=False

Ele foi no estacionamento 3. Para nos certificarmos que o modelo está funcionando, vamos criar mais um exemplo, adicionando outro avião grande, 4, que tem controle de passaporte. Esse avião pode ir no estacionamento 1? Não, porque o estacionamento 1 não é grande. Ele pode ir no estacionamento 2? Não, porque não é grande. Ele pode ir no estacionamento 3? Não pode, porque não tem controle de passaporte.

Sendo assim, precisamos de mais um estacionamento: estacionamento 4, que tem total de aviões, suporta avião grande e controle de passaporte. O avião 1, que tem controle de passaporte, não pode ir no último estacionamento. Não é uma solução viável, porque o avião 4 não teria onde pousar. O único lugar que o avião 4 pode pousar é no estacionamento 4.

avioes = [Aviao(1, False, True),
          Aviao(2, True, False),
          Aviao(3, False, False),
          Aviao(4, True, True)]
modelo = cp_model.CpModel()
total_de_avioes = len(avioes)

estacionamentos = [Estacionamento(1, total_de_avioes, False, modelo, True),
                   Estacionamento(2, total_de_avioes, False, modelo, False),
                   Estacionamento(3, total_de_avioes, True, modelo, False),
                   Estacionamento(4, total_de_avioes, True, modelo, True)]

avioes_distintos(estacionamentos, modelo)
todo_aviao_tem_que_estacionar(total_de_avioes, estacionamentos, modelo)
limita_vizinhos(modelo, estacionamentos, avioes)
limita_aviao_grande_para_estacionamento_grande(modelo, estacionamentos, avioes)
limitar_avioes_que_requerem_passaporte(modelo, estacionamentos, avioes)

solucionador = cp_model.CpSolver()
resolve(solucionador, modelo, estacionamentos, avioes)

OPTIMAL

estacionamento_1 tem aviao 1 grande=False

estacionamento_2 tem aviao 3 grande=False

estacionamento_3 tem aviao 2 grande=False

estacionamento_4 tem aviao 4 grande=True

Começa com o avião mais restrito, o 4. Ele só pode ir no estacionamento 4. Então, sobra outro avião restrito, que é o avião 1, como ele requer controle de passaporte, tem que ir no 1. Então, sobrou outro que é grande, o 2. Ele tem que ir no 3. E aí o outro que sobrou ficou no 2.

Resolvemos, mas ainda temos outros desafios pela frente. Até mais!

Minimizando as penalidades - Adicionando penalidades

Vamos continuar. Queremos agora dar um exemplo de um aeroporto em que nós temos uma situação um pouco mais complexa, que é muito importante para nós colocarmos tudo o que já conhecemos em prática.

Imaginem um aeroporto com quatro estacionamentos: dois com controle de passaporte e dois sem controle de passaporte. Chegaram dois aviões que não precisam de controle de passaporte. Para onde vocês vão direcionar esses aviões? Eles vão aparecer no estacionamento sem controle de passaporte. Nós pensamos que faz sentido. Pessoas sem controle de passaporte vão para o local sem controle de passaporte.

Mas chega um terceiro avião com o combustível no final, precisando pousar. Você vai fazer o quê? Vai dizer para ele não pousar, se não for no estacionamento correspondente? Não vamos falar isso, vamos deixar pousar, e infelizmente, no controle de passaporte.

Não é o ideal, não é uma restrição forte, ou seja, uma restrição hard, mas sim uma restrição soft. Queremos colocar essa restrição, mas se não colocar, tudo bem.

Então, as ferramentas de otimização permitem que implementemos esse tipo de recurso. Algumas de forma explícita, através de uma chamada do tipo soft, de uma restrição soft. E outras, como já vimos no passado, no curso anterior, adicionamos uma penalidade.

Um avião sem controle de passaporte, vindo de Salvador, por exemplo, até pode ser inserido na área de controle de passaporte, mas não é bacana. Então, podemos colocar uma penalidade, podendo diminui-la.

Por exemplo, cada avião que não precisa de controle de passaporte, mas para onde precisa controle de passaporte, vou dar uma penalidade de mil. Quer dizer, queremos minimizar essa penalidade. Então, quanto mais aviões nessa situação, pior para nós. E o modelo vai tentar encontrar o ponto mínimo, a solução que minimiza esse custo.

Função Objetivo

Com o Google Sheets aberto, criaremos uma aba nova e digitaremos na célula A1: cada avião que não precisa de controle de passaporte e está no controle de passaporte tem custo de 1000. Assim, teremos uma somatória. Somaremos todos os custos de todos os aviões. Esse será o custo total e é isso que queremos minimizar.

Desejamos minimizar o custo total.

Percebam que o custo total está em função dos aviões. É uma função dos aviões, porque se o avião está aqui ou lá, estamos em função dele. Então, literalmente, é uma função matemática. Por quê? Porque é uma somatória, é a soma de todos os custos.

Soma todas essas penalidades, que podem ser zero ou mil. Zero para um avião que está onde deveria e mil para um avião que não está onde deveria. Soma todas elas e isso vai dar um custo, isso é uma função. Nós chamamos essa função de função objetivo. Essa função objetivo deve ser minimizada.

Você pode falar "ah, tenho um problema de maximização". Tudo bem, faz um de maximizar. No nosso caso, queremos minimizar. Não queremos que os aviões parem nesses lugares. Então, colocamos uma penalidade e falamos que não queremos isso. Então, essa sacada da função objetivo é super importante, já vimos no curso passado essa história da penalidade e da função objetivo para minimizar. Vamos ver agora de novo, só que com vários aviões.

Implementação

Como vamos fazer isso? Vamos subir no nosso código, nos nossos exemplos. Depois de limitar aviões que requerem passaporte, vamos indicar que preferimos aviões em determinada situação. Trata-se de uma preferência, não é uma requisição. Preferimos aviões que tem controle de passaporte. Se vier sem, adiciona uma penalidade.

Essa função vai receber um modelo, estacionamentos e avioes, como de costume. Vamos precisar dos aviões e vamos precisar dos estacionamentos adequados. Quais são os estacionamentos? Os estacionamentos que requerem controle de passaporte. Então, são os estacionamentos que têm controle.

Vamos copiar do bloco de código acima. Já temos os estacionamentos sem controle, copiaremos e colaremos. Só retirando a palavra not. Esses são os estacionamentos com controle.

Lembrem-se que esses estacionamentos com controle vão precisar de um avião que seja com ou sem controle de passaporte. Disso dependerá a penalidade. Então, vamos precisar provavelmente dos dois tipos de aviões. Vamos colocar os dois tipos de aviões, copiando de lá de cima, aviões com controle e aviões sem controle, inserindo a palavra not após o if.

def prefere_avioes_com_controle_de_passaporte(modelo, estacionamentos, avioes)
    estacionamentos_com_controle = [estacionamento for estacionamento in estacionamentos if estacionamento.tem_controle_de_passaporte]
    avioes_com_controle = [aviao for aviao in avioes if aviao.requer_controle_de_passaporte]
    avioes_sem_controle = [aviao for aviao in avioes if not aviao.requer_controle_de_passaporte]

Então, agora já temos os estacionamentos com controle de passaporte. E sabemos que para cada um desses estacionamentos, então for estacionamento in estacionamentos_com_controle, temos que verificar se o avião que está lá requer ou não passaporte.

Se ele exigir passaporte, a penalidade é igual a zero. Se ele não exigir passaporte, teremos uma penalidade de mil. Então, vamos fazer para cada avião. Quais são os aviões que queremos passar? Os aviões que não requerem. Porque se não requer, vamos colocar a penalidade. Depois vemos se vamos precisar dos que requerem.

Escreveremos for aviao in avioes_sem_controle, indicando cada avião que não precisa de passaporte. Preciso saber se esse avião está nesse estacionamento. Como fazemos isso?

Para saber se esse avião está nesse estacionamento e poder calcular uma penalidade, precisaremos da penalidade. Então, vamos calcular essa penalidade. Penalidade é igual a modelo.NewIntValue(0, 1000, f 'penalidade_{estacionamento.k}_{aviao.k}').

def prefere_avioes_com_controle_de_passaporte(modelo, estacionamentos, avioes):
    estacionamentos_com_controle = [estacionamento for estacionamento in estacionamentos if estacionamento.tem_controle_de_passaporte]
    avioes_com_controle = [aviao for aviao in avioes if aviao.requer_controle_de_passaporte]
    avioes_sem_controle = [aviao for aviao in avioes if not aviao.requer_controle_de_passaporte]
    for estacionamento in estacionamentos_com_controle:
        for aviao in avioes_sem_controle:
            penalidade = modelo.NewIntValue(0, 1000, f'penalidade_{estacionamento.k}_{aviao.k}')

Então, essa vai ser a variável que representa ou zero ou mil, que é a penalidade se esse avião estiver aqui. Agora, temos que tomar cuidado. Já trabalhamos com penalidade. Queremos que a penalidade seja mil. Assim, escreveremos modelo.Add(penalidade == 1000).

Acontece que a penalidade só vai ser mil se, ou seja, OnlyEnforceIf. Então, a penalidade vai ser mil somente se um avião sem controle estiver nesse estacionamento. Então, OnlyEnforceIf se esse avião está nesse estacionamento.

Assim, queremos que a penalidade seja mil se, em tempo de execução, o modelo matemático perceber que um avião sem controle precisa pousar em um estacionamento com controle de passaporte.

E no caso contrário? Queremos que seja zero. Então, vamos escrever o caso contrário. modelo.Add(penalidade == 0). Então, a penalidade agora é zero. Mas quando a penalidade é zero? OnlyEnforceIf, somente se, o avião não está nesse estacionamento. Então, a variável aviao_esta_nesse_estacionamento.Not(). Então, se ele não está nesse estacionamento.

Parece aquele trabalho que já fizemos de criar uma penalidade, que é uma variável com if. Só que lembrem, não é uma variável do Python. É uma variável do modelo matemático. O modelo matemático vai ter que decidir se coloca o avião lá ou não, podendo ter uma penalidade de zero ou de mil.

def prefere_avioes_com_controle_de_passaporte(modelo, estacionamentos, avioes):
    estacionamentos_com_controle = [estacionamento for estacionamento in estacionamentos if estacionamento.tem_controle_de_passaporte]
    avioes_com_controle = [aviao for aviao in avioes if aviao.requer_controle_de_passaporte]
    avioes_sem_controle = [aviao for aviao in avioes if not aviao.requer_controle_de_passaporte]
    for estacionamento in estacionamentos_com_controle:
        for aviao in avioes_sem_controle:
            penalidade = modelo.NewIntValue(0, 1000, f'penalidade_{estacionamento.k}_{aviao.k}')
            
            modelo.Add(penalidade == 1000).OnlyEnforceIf(aviao_esta_nesse_estacionamento)
            modelo.Add(penalidade == 0).OnlyEnforceIf(aviao_esta_nesse_estacionamento.Not())

Mas atenção: Estamos criando uma penalidade para cada parzinho de estacionamento com controle e avião sem controle. Então, temos muitas penalidades. Imaginem que, se tivermos dez estacionamentos com controle e dez aviões sem controle, são criadas cem variáveis penalidade.

E um monte dessas penalidades será igual a zero, porque o avião não está lá. Só, no máximo, tem um avião ali dentro. Então, a maior parte disso vai ser zero. Mas se algum desses aviões estiver nesse estacionamento, vai ser mil, porque definimos assim.

Faltou criar a variável aviao_esta_nesse_estacionamento. Mas essa variável tem que ser booleana, porque ela é uma variável true ou false. Já trabalhamos com essas variáveis booleanas. Então, criamos um modelo.NewBoolVar(), uma variável booleana, que terá um nome também. Dentro dela, escreveremos f. Queremos dizer que, no estacionamento tal, temos tal avião. Então,f 'estacionamento_(estacionamento.k)_tem_aviao_(aviao.k). Nesse estacionamento, temos esse avião. É a variável booleana que diz isso: no estacionamento 1, tem o avião 1. Se tiver, é true, se não tiver, é false.

Mas como falamos "se tiver, é true, se não tiver, é false"? Fazemos um pouco o contrário: vamos adicionar para o modelo uma restrição nova. Diremos que se a variável aviao_esta_nesse_estacionamento for true, então o estacionamento.variavel tem que ser igual aviao.k.

O modelo matemático vai ter o raciocínio dele, mas podemos pensar assim: o que ele tenta fazer é colocar um true ou false. Ele tenta colocar um true, digamos que o avião 5 esteja no estacionamento 3. Já que ele colocou um true na variável em modelo.NewBoolVar(), então, a variável estacionamento 3 tem que ter o valor 5.

E se por acaso esse avião é um avião sem controle e um estacionamento com controle, o que vai acontecer? Vai ser acrescentada a penalidade de 1000. Lembre-se de que precisamos da restrição contrária. modelo.Add().OnlyEnforceIf. Se aviao_nesse_estacionamento.not, ou seja, ele não está nesse estacionamento, o modelo tentou colocar um false para ver se resolve o nosso problema.

Já que ele tentou colocar, o que ele vai fazer? estacionamento.variavel tem que ser diferente desse avião. Obrigamos a ser diferente. Não quer dizer que ele vai tentar, ele vai olhar essas regras, vai otimizar e vai fazer buscas para tornar esse processo o melhor possível. Essa é a ideia.

Com isso, temos as variáveis que queremos. O que faltou é somar todos essas penalidades. Então, na parte de cima do código, criaremos penalidades, uma lista. E aí, para cada um deles, fazemos penalidades.append(penalidade). E no final, retornamos penalidades. Então, a função prefere_avioes_com_controle_de_passaporte vai devolver as penalidades.

def prefere_avioes_com_controle_de_passaporte(modelo, estacionamentos, avioes):
    estacionamentos_com_controle = [estacionamento for estacionamento in estacionamentos if estacionamento.tem_controle_de_passaporte]
    avioes_com_controle = [aviao for aviao in avioes if aviao.requer_controle_de_passaporte]
    avioes_sem_controle = [aviao for aviao in avioes if not aviao.requer_controle_de_passaporte]
    for estacionamento in estacionamentos_com_controle:
        for aviao in avioes_sem_controle:
            penalidade = modelo.NewIntVar(0, 1000, f'penalidade_{estacionamento.k}_{aviao.k}')
            
                        aviao_esta_nesse_estacionamento = modelo.NewBoolVar(f'estacionamento_{estacionamento.k}_tem_aviao_{aviao.k}')
            modelo.Add(estacionamento.variavel == aviao.k).OnlyEnforceIf(aviao_esta_nesse_estacionamento)
            modelo.Add(estacionamento.variavel != aviao.k).OnlyEnforceIf(aviao_esta_nesse_estacionamento.Not())
            
            modelo.Add(penalidade == 1000).OnlyEnforceIf(aviao_esta_nesse_estacionamento)
            modelo.Add(penalidade == 0).OnlyEnforceIf(aviao_esta_nesse_estacionamento.Not())
            
            modelo.Add(penalidade == 1000).OnlyEnforceIf(aviao_esta_nesse_estacionamento)
            modelo.Add(penalidade == 0).OnlyEnforceIf(aviao_esta_nesse_estacionamento.Not())
            penalidades.append(penalidade)
return penalidades

Chamaremos essa função no fim do modelo, com prefere_avioes_com_controle_de_passaporte(modelo, estacionamentos, avioes). Ela devolve para nós as penalidades, pois vamos precisar delas. E agora, o que queremos fazer? Quando formos resolver o problema, quero passar essas penalidades para o solucionador: resolve(solucionador, modelo, estacionamentos, avioes, penalidades).

Subiremos de novo até o resolve para incluir as penalidades dentre os parâmetros. Antes de resolver, escreveremos modelo.Minimize(sum(penalidades)). Estamos pedindo para minimizar a soma dessas penalidades. Aí, você fala "mas pode fazer sum em penalidades?". Pode, porque são variáveis inteiras.

Então, a função objetivo é a soma das penalidades. E é ela que queremos minimizar. Se for infeasible, não teve solução. Agora, já que tem solução, queremos imprimir qual foi o valor total das penalidades. No nosso caso, vamos colocar a função objetivo ou "Valor objetivo". O valor mínimo que ela encontrou será o solucionador.ObjectiveValue().

// trecho de código suprimido

print(f"Valor objetivo = solucionador.ObjectiveValue()")

Vamos salvar, executar e esperar não ter cometido nenhum erro. Se tudo estiver correto, veremos o resultado esperado. O valor objetivo, nesse caso, é zero. Não se esqueça de passar penalidades como parâmetro para resolve em todos os casos. De qualquer forma, encontramos uma solução para todos os casos anteriores, então a solução foi zero. Se não tem solução, não há o que fazer.

No terceiro caso, ele retornou INFEASIBLE porque são dois aviões que requerem passaporte. Nesse caso, não podemos deixar passar. Quando há um avião exigindo passaporte e dois que não exigem, enquanto temos um portão com passaporte e dois sem. Nesse caso, o custo é zero. No próximo, um avião com controle de passaporte e dois sem também funciona com custo zero. Em seguida, outro caso que funcionava a custo zero.

Agora, o caso mais simples de todos é aquele com dois aviões: um que requer e outro que não requer passaporte. Vamos mudar para dois aviões que não requerem passaporte, com apenas um estacionamento que não requer. Nesse caso, será necessário pegar qualquer um dos dois aviões e pousá-lo no estacionamento com controle de passaporte. Neste caso, o custo tem que ser mil.

avioes = [Aviao(1, False, False),
          Aviao(2, False, True)]
modelo = cp_model.CpModel()
total_de_avioes = len(avioes)

estacionamentos = [Estacionamento(1, total_de_avioes, False, modelo, True),
                   Estacionamento(2, total_de_avioes, False, modelo, False)]

avioes_distintos(estacionamentos, modelo)
todo_aviao_tem_que_estacionar(total_de_avioes, estacionamentos, modelo)
limita_vizinhos(modelo, estacionamentos, avioes)
limita_aviao_grande_para_estacionamento_grande(modelo, estacionamentos, avioes)
limitar_avioes_que_requerem_passaporte(modelo, estacionamentos, avioes)
penalidades= prefere_avioes_com_controle_de_passaporte(modelo, estacionamentos, avioes)


solucionador = cp_model.CpSolver()
resolve(solucionador, modelo, estacionamentos, avioes, penalidades)

Após rodar o código, receberemos o valor de 1000 como penalidade. Podemos copiar o código e colá-lo logo em seguida para torná-lo mais complexo: inseriremos mais um avião, que não requer passaporte. Além disso, incluiremos mais um estacionamento que requer o controle de passaporte. Nesse caso, a penalidade precisa ser de 2 mil.

avioes = [Aviao(1, False, False),
          Aviao(2, False, False),
          Aviao(3, False, False)]
modelo = cp_model.CpModel()
total_de_avioes = len(avioes)

estacionamentos = [Estacionamento(1, total_de_avioes, False, modelo, True),
                   Estacionamento(2, total_de_avioes, False, modelo, False),
                   Estacionamento(3, total_de_avioes, False, modelo, True)]

avioes_distintos(estacionamentos, modelo)
todo_aviao_tem_que_estacionar(total_de_avioes, estacionamentos, modelo)
limita_vizinhos(modelo, estacionamentos, avioes)
limita_aviao_grande_para_estacionamento_grande(modelo, estacionamentos, avioes)
limitar_avioes_que_requerem_passaporte(modelo, estacionamentos, avioes)
penalidades= prefere_avioes_com_controle_de_passaporte(modelo, estacionamentos, avioes)

solucionador = cp_model.CpSolver()
resolve(solucionador, modelo, estacionamentos, avioes, penalidades)

Ao executar o código, obtemos exatamente a penalidade de 2000. Isso acontece porque dois aviões estão indo onde não gostaríamos que eles fossem. Se inserirmos um quarto avião que precisa do controle de passaporte, ficando assim com três aviões sem controle e um com controle. Além disso, se editarmos os estacionamentos para ficarem com três sem controle e um com controle, o custo deve ser zero.

No próximo vídeo, vamos dar uma olhada nas variáveis de penalidade na planilha. Até mais!

Sobre o curso IA aumentada: aprimorando técnicas de otimização em um problema prático

O curso IA aumentada: aprimorando técnicas de otimização em um problema prático possui 103 minutos de vídeos, em um total de 34 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:

• Adicionando restrições ao modelo
• Minimizando as penalidades
• Trabalhando com matrizes
• Minimizando os custos