Utilização do OpenSolver com VBA

Introdução

O OpenSolver é um suplemento poderoso do Excel, para problemas de otimização combinatória.

Foi desenvolvido por Andrew Mason e equipe, da Universidade de Auckland (Nova Zelândia) e pode ser encontrado em: https://opensolver.org.

A ideia básica é que o Solver comum, do Excel, tem um limite de utilização (apenas 200 variáveis). Para problemas maiores do que isso, é necessário adquirir uma licença junto à Frontline, empresa desenvolvedora do Solver.

Já o OpenSolver pode utilizar solver open-source, como o CBC. Ou utilizar ferramentas (pagas) ainda mais poderosas, como o Gurobi ou o CPLEX. Dessa forma, abrimos uma gama de aplicações muito maior do que apenas o Solver da Frontline.

O OpenSolver tem um menu de utilização bastante similar ao Solver comum.

Este tutorial mostra como utilizar VBA para acessar e manipular o OpenSolver.

Qual a vantagem de utilizar o VBA? É ter uma flexibilidade maior na formulação, e com isso poder transformar a planilha numa ferramenta – para o usuário leigo, é só clicar num botão e resolver.

O Problema da Mochila

O Problema da Mochila é um clássico da otimização combinatória. Vamos utilizar como exemplo.

Vou fazer uma viagem, e tenho uma mochila. Há diversos itens que posso escolher para levar. Cada item tem um peso e um valor.

Quais itens devo levar?

Quero maximizar o valor que estou levando na mochila, restrito ao peso máximo que consigo carregar.

No Excel, o peso máximo da mochila e os valores e pesos por item devem ser dados de entrada do problema.

O campo “Solução” deve conter 0 ou 1 (indicando não levar ou levar o item). O Peso Total é a soma do peso dos itens escolhidos, e a Função Objetivo é a soma dos valores dos itens escolhidos.

Baixe o arquivo Excel em Knapsack_OpenSolver.xlsm

Primeiro passo: adicionar o OpenSolver nas referências do VBA

Como adicionar o OpenSolver nas referências do VBA?

Ir em Ferramentas -> Referências

Adicionar o OpenSolver e clicar em OK.

Como modelar um problema no OpenSolver com VBA

Vamos utilizar o OpenSolver via VBA, para resolver o problema da mochila.

É importante notar que todo comando que fazemos manualmente tem o equivalente via VBA.

A referência para os comandos pode ser consultada em https://opensolver.org/opensolver-api-reference. Outra forma é consultando direto o código VBA do OpenSolver, ele detalha bem a forma de utilização.

Função Objetivo

No painel do OpenSolver, tem um campo para definir a célula com a função objetivo, e a direção: maximizar, minimizar, ou valor alvo.

O equivalente no VBA é a função SetObjectiveFunctionCell:

SetObjectiveFunctionCell Range(“i5”)

Para minimizar ou maximizar, SetObjectiveSense:

SetObjectiveSense MaximiseObjective

O próprio código, via autocompletar, vai dar as dicas das opções de preenchimento.

Definição de Variáveis

A seguir, podemos definir as variáveis, utilizando o painel do OpenSolver.

O equivalente, via código, é:

SetDecisionVariables Range(“i8:i470”)

E é nesse ponto que o código começa a ficar poderoso. Ao invés do range ser fixo e ser mudado a cada novo cenário, como no exemplo, podemos estabelecer o range de acordo com o tamanho do problema modelado via código.

Definição de Restrições

Para o caso em questão, o primeiro ponto a notar é que as variáveis de decisão devem ser binárias.

E a segunda restrição é a de que o valor carregado deve ser menor do que a capacidade máxima da mochila.

O equivalente VBA é bastante similar, com a utilização do comando AddConstraint:

AddConstraint Range(“i8:i470”), RelationBIN 

AddConstraint Range(“i4”), RelationLE, Range(“c5”)

A notar o parâmetro “RelationLE”, que significa “menor igual”. Há parâmetros para “maior igual”, “igual”, etc, basta consultar as opções no próprio código ou no link de referência dado acima.

Rodar o modelo

Com o modelo formulado, o próximo passo é rodar. Manualmente, isso equivale a clicar no ícone correspondente.

Em código, é utilizar o comando RunOpenSolver:

Dim result As OpenSolverresult

result = RunOpenSolver

O valor retornado será 0, no caso de rodar corretamente, e códigos outros conforme instruções abaixo.

Enum OpenSolverResult
Pending = -4 ‘ Used for solvers that asynchronously and are yet to run
AbortedThruUserAction = -3 ‘ Used to indicate that a non-linearity check was made (losing the solution)
ErrorOccurred = -2 ‘ Indicate an error occured and has been reported to the user
Unsolved = -1 ‘ Indicates a model not yet solved
Optimal = 0
Unbounded = 4 ‘ objective can be made infinitely good
Infeasible = 5 ‘ There is no solution that satisifies all the constraints
LimitedSubOptimal = 10 ‘ CBC stopped before finding an optimal/feasible/integer solution because of CBC errors or time/iteration limits
NotLinear = 7 ‘ Report non-linearity so that it can be picked up in silent mode
End Enum

Uma última dica é resetar o modelo antes do início da macro:

ResetModel

Senão for feito isso, as restrições antigas vão continuar existindo sobrepondo com as novas, o que pode fazer o modelo ficar incorreto.

Conclusão

O OpenSolver é uma ferramenta poderosa. Aliada ao VBA, pode permitir um grau de automação enorme, e resolver uma gama de problemas de Pesquisa Operacional nas empresas e na vida real.

Há diversas outras opções mais avançadas, a fim de permitir modelos complexos. A ideia do tutorial foi fazer o exemplo mais simples e didático possível.

O OpenSolver, em geral, é recomendado para problemas de tamanho médio. Para problemas muito grandes, começa a ter lentidão demasiada na leitura de dados e formulação do problema, pela forma com que este foi construído (fortemente baseada em Excel).

Exemplo prático: um trabalho de otimização de silvicultura, com cerca de 100 mil variáveis, demorava 6 horas para resolver com OpenSolver puro. Migrando para Python (Pyomo) + CBC, o tempo caiu para 40 min, para resposta de mesma qualidade. Com Python  (Pyomo) + Gurobi, o tempo caiu para 4 minutos, para a mesma resposta.

De qualquer forma, cabe ao projetista escolher a melhor ferramenta para o processo em questão, dadas as restrições (custo, tempo de processamento, maturidade do processo). E o OpenSolver figura como um excelente candidato a resolver problemas difíceis, de forma rápida e flexível.

Referências:

https://opensolver.org/

https://opensolver.org/opensolver-api-reference/

https://en.wikipedia.org/wiki/Knapsack_problem

Sobre DNA, AlphaFold e um pequeno exercício

Se um computador tem a codificação em zeros e uns, um ser humano é codificado com 4 moléculas: Adenina, Guanina, Citosina e Timina. É o livro de códigos conhecido como DNA.

Assim como um código de computador, tem instruções específicas para começar, parar e identificar o que deve ser feito.

Esse código DNA vira uma proteína no final das contas, que vira algo útil para o ser humano, como um anticorpo.

Hoje em dia, sequenciar DNA é um problema fácil. Porém, prever a estrutura final da proteína é um problema muito difícil — é uma estrutura em 3D, onde cada moleculazinha interfere em todas as outras.

Por ser um problema muito difícil e importante, é um prato cheio para as empresas de IA mais avançadas do mundo.

A empresa DeepMind, da Google, desenvolveu um algoritmo chamado AlphaFold, que prevê o dobramento da proteína a partir do sequenciamento. A DeepMind desenvolve o que há de mais avançado em IA no mundo. Só para ter uma ideia, para treinar um algoritmo desses é na ordem de alguns milhões de dólares.

Agora o DeepMind anunciou que vai tornar todo esse conhecimento público.

DeepMind vai liberar estruturas de todas as proteínas conhecidasEm dezembro de 2020, a DeepMind, braço de inteligência artificial do Google, pegou o mundo da biologia de surpresa ao…www.tecmundo.com.br

“Até agora, o banco de dados consiste em 350.000 novas estruturas de proteínas. A DeepMind diz que vai prever e liberar as estruturas de mais de 100 milhões delas nos próximos meses — mais ou menos todas as proteínas conhecidas pela ciência.” — Trecho da matéria.

Aplicações potenciais: desenvolver novos remédios, conhecer melhor moléculas do corpo humano, etc.

Exercício simples com o genoma da COVID

O genoma da COVID pode ser baixado no site a seguir.
https://www.ncbi.nlm.nih.gov/sars-cov-2/

Esse compartilhamento de informações é o que possibilitou o desenvolvimento de vacinas num tempo tão curto.

São informações como a seguinte. Peguei um pequeno trecho, a base toda tem centenas de megabytes de tamanho.

Exercício: dada uma sequência genética como a seguinte,

MEQDRDIYFMQLAIEEAKKAEEMQEVPIGAVIVLDGEVISVAHNLRETEQRSIAHAELLAIDEACKKLGTWRLEDATLYVTLEPCPMCAGGIVLSRVKRVVYGASDPKGGCAGTLMNLLTDERFNHQCEVVTGVLEEECGTLLTNFFRELRKKRKAIKKLEKSNEN

Encontre o trecho a seguir. Está em qual posição?

LEDATL

Dica: No Excel, é só usar a função “Localizar”.

Agora, para pensar. Digamos que haja uma pequena mutação em uma das posições.

LADATL

O match perfeito agora não vai dar certo. Como encontrar o match mais similar possível?

Só para saber, o match similar é um problema bem mais difícil e há vários algoritmos propostos para tal.

Ideias analíticas avançadas:

https://medium.com/ideias-anal%C3%ADticas-avan%C3%A7adas

Ideias Analíticas Avançadas

Estou lançando uma publicação na plataforma Medium: a Ideias Analíticas Avançadas (https://medium.com/ideias-anal%C3%ADticas-avan%C3%A7adas).

Os objetivos são:

• Escrever sobre Analytics Hard: Otimização, Matemática, Python, Computação Quântica, com código e tudo
• Convidar outros autores a publicar sobre o tema.

Fica já o convite, quem quiser escrever sobre alguns dos temas e divulgar ali.

O problema da mochila

1. (Fácil)

Digamos que eu vá fazer uma viagem para a Europa. Tenho 6 itens, cada um com um peso e um valor.

Consigo carregar no máximo 60 kg na minha mochila. Quais os itens a levar, de forma a maximizar o valor na mochila, dentro da restrição?

2. (Difícil) Agora, tenho mais de 30 itens, e consigo carregar 800 Kg. Desenvolver um algoritmo para resolver o problema (o solver do Excel é suficiente).

Solução

Este problema pode ser resolvido utilizando o solver.

Imagine uma variável de decisão binária (0 = não levo o item, 1 = levo o item).

ProblemaMochila_Solucao.xlsx

Queremos maximizar o valor a ser carregado.

A função objetivo será o somarproduto entre a variável binária e o valor de cada item.

A restrição será o somarproduto entre a variável binária e o peso de cada item, que deve ser menor ou igual ao peso máximo.

No solver, definir a função objetivo como a célula que calcula o valor transportado.

O range das variáveis de decisão deve estar em “Alterando células variáveis”.

São duas restrições.

– a variável de decisão deve ser binária

– o peso total (calculado na célula G7) deve ser menor do que a restrição de peso máximo.

O método de solução é LP Simplex, ou seja, um problema de otimização linear simples.

Se o solver não estiver habilitado, ir em Arquivos -> Opções -> Suplementos

Ir… em Suplementos do Excel, e habilitar o Solver.

O Desafio 1 é mais simples, dá para resolver no braço.

O Desafio 2 tem a mesma estrutura, e dá para resolver de forma similar. Vide arquivo ProblemaMochila_Solucao.xlsx.

Qual a aplicação deste tipo de problema no cotidiano?

Na indústria de papel e celulose, o problema do Trim deve ser resolvido todos os dias. Como eu corto o rolo jumbo de papel, nos diversos pedidos dos clientes, de forma a ter o maior aproveitamento possível do mesmo?

O problema da mochila pode ser utilizado de forma auxiliar, a gerar novos cortes, numa técnica chamada de “Geração de colunas”.

Ideias técnicas com uma pitada de filosofia

https://ideiasesquecidas.com/

Metaheurística com 2 variáveis

Essa versão é um pouquinho mais elaborada que a versão com uma variável (https://ferramentasexcelvba.wordpress.com/2021/03/27/exemplo-de-metaheuristica-uma-variavel/)

Serve para resolver o problema linear:

Max 10*x +5*y

Sujeito a:

2*x+4*y <= 50

1*x -6*y <= 15

É semelhante ao anterior, mas agora as variáveis são matrizes.

‘Inicializando coeficientes FO

coefFO(1) = 10

coefFO(2) = 5

‘Inicializando coeficientes Matriz

coefMatriz(1, 1) = 2

coefMatriz(1, 2) = 4

coefMatriz(2, 1) = 1

coefMatriz(2, 2) = -6

‘Inicializando rhs

RHS(1) = 50

RHS(2) = 15

Um parâmetro adicional, restringindo as variáveis a assumir valor máximo 50 e mínimo 0.

For i = 1 To nvar

    varmin(i) = 0 ‘Range Mínimo

    varmax(i) = 50 ‘Range Máximo

Next i

Em linhas gerais:

– Escolhe valores aleatórios no range das variáveis

– Pondera o valor aleatório com a melhor solução até agora

– Lambda controla o mix valor aleatório x melhor solução até agora. No início lambda é pequeno, depois vai aumentando

– Verifica se cumpre todas as restrições

 – função objetivo que avalia a solução

– salva o histórico

‘Algoritmo evolutivo

For iter = 1 To Niteracoes ‘Numero de iteracoes

    lambda = iter / Niteracoes

    ‘Sorteia um valor

    sorteia var, varmin, varmax, varbest, lambda

    ‘Verifica restricoes

    isOk = verificaRestricoes(var, coefMatriz, RHS)

    If isOk Then

        ‘Avalia a função atual

        FOatual = FO(var, coefFO)

        ‘Salva a melhor (maximizando)

        If FOatual > FOBest Then

            FOBest = FOatual

            copiaUni var, varbest

        End If

    End If

    FOhist(iter, 1) = FOBest

Next iter

Usando o solver, as variáveis ótimas são 22,5 e 1,25.

A metaheurística chega a valores próximos ao ótimo, o que mostra que funciona para uma solução suficientemente boa.

Provavelmente, com muitas variáveis e muitas restrições, vai ficar bem mais difícil convergir para uma solução boa.

Uma coisa ruim é todas as equações serem hard coded, mas quem domina código consegue fazer isso fácil.

É possível “tunar” esse algoritmo básico com pré processamento, ou algum chute guiado ao invés de ser basicamente aleatório, mas aí vai depender do problema.

Planilha para download no Github: https://github.com/asgunzi/Metaheuristica-2-var

Exemplo de metaheurística – uma variável

A ideia aqui é escrever uma série de metaheurísticas de dificuldade crescente.

Começando do caso mais simples possível. Variável unidimensional “x”.

Defino um range de valores, no caso, x entre 0 e 100.

varmin = 0 ‘Range Mínimo

varmax = 100 ‘Range Máximo

Seja a função objetivo –x^3 + 20*x^2 + 100, mostrado no gráfico abaixo.

Private Function FO(ByVal var) As Double

    ‘Implementa a função objetivo

    FO = -var ^ 3 + 20 * var ^ 2 + 100

End Function

Este algoritmo vai:

 – escolher um valor aleatório entre 0 e 100

– ponderar o valor aleatório com a melhor solução até agora

– lambda controla o mix valor aleatório x melhor solução até agora. No início lambda é pequeno, depois vai aumentando

– função objetivo que avalia a solução

– salva o histórico

Trecho do código:

For iter = 1 To Niteracoes ‘Numero de iteracoes

    lambda = iter / Niteracoes

    ‘Sorteia um valor

    sorteia var, varmin, varmax, varbest, lambda

    ‘Avalia a função atual

    FOatual = FO(var)

    ‘Salva a melhor (maximizando)

    If FOatual > FOBest Then

        FOBest = FOatual

        varbest = var

    End If

    FOhist(iter, 1) = FOBest

Next iter

Resultado. Em apenas 100 iterações, já chegou num valor excelente: x = 13,3

Você pode mudar a FO, ranges, etc.

Próximo passo é fazer um exemplo multidimensional, etc.

Planilha para download no Github: https://github.com/asgunzi/Metaheuristica-uma-variavel

Metaheurística para o Caixeiro-Viajante

Implementação em VBA de metaheurística para resolução do problema do caixeiro-viajante.

A metaheurística não vai dar o valor ótimo, porém na prática, pode entregar um valor bom o suficiente.

Algumas vantagens: é mais flexível em termos de modelar restrições, é grátis (um solver tem licença que pode custar algumas dezenas de milhares de dólares, no mínimo).

Algumas desvantagens: ter alguém que manje muito de otimização combinatória para adaptar o código corretamente, não garantir a solução ótima.

De qualquer forma, é uma alternativa viável, competitiva e possível de ser utilizada, para problemas de otimização combinatória.

Segue para download no Github.

https://github.com/asgunzi/travelingSalesmanVBA

Ideias técnicas com uma pitada de filosofia
https://ideiasesquecidas.com/

O ponto de parada ótimo

Imagine a seguinte situação. Quero alugar um apartamento num bairro muito concorrido de São Paulo. Vou visitar 20 imóveis, e assim que o fizer, ou eu faço a proposta para alugar na hora, ou decido ver o imóvel seguinte e perco o visitado para sempre (afinal, é um bairro concorrido).

O ordem de visitas é aleatória.

Qual a estratégia que maximiza a escolha?

É um claro tradeoff. Para conseguir informação, devo prospectar, porém, por ser uma prospecção destrutiva, vou descartar bons imóveis e acabar ficando sem opções.

Este problema é conhecido como o “Ponto de parada ótimo”, e a resposta ótima é 37%.

Primeiro, tenho que coletar informações, e a única forma de fazer é visitando os imóveis. Visito 37% dos imóveis, e avalio qual o melhor destes.

A seguir, pego o primeiro imóvel igual ou superior ao score avaliado anteriormente.

Exemplo:

Tenho uma lista de 20 imóveis, com notas aleatórias (quanto maior, melhor).

37% de 20 dá 7, arredondando. Visito os 7 primeiros imóveis, sem escolher nenhum deles, mas anotando qual o melhor.

No caso, o melhor imóvel visitado teve nota 65.

A seguir, continuo fazendo as visitas até encontrar algum igual ou superior a 65. No caso, faço a proposta na hora e fico com o imóvel de nota 77.

Na lista, há dois imóveis com score maior (de 91 e 97), de forma que a estratégia citada escolheu o terceiro melhor da lista (lembrando que, no problema, não teríamos essa informação da nota sem visitar – e descartar – o imóvel)

Desafio em Excel.

Dada uma lista com números aleatórios como o do anexo, escrever fórmulas (ou rotinas ou qualquer outro truque) para implementar o algoritmo de parada ótima descrito. Comparar com a melhor solução.

(Clicar em F9 ou mudar qualquer célula vai alterar os valores).

Segue a minha versão da solução, disponível para download no OneDrive.

PontoParada.xlsx

A ideia é sempre a mesma. Pegar o maior valor dos 37% primeiros, e depois o primeiro maior valor encontrado.

Da literatura, este problema tem vários nomes (como o problema da escolha da secretária).

Em geral, experimentos práticos x teoria mostram que tendemos a ser impacientes, e fechar um negócio mais cedo, sem explorar tanto – e optar por uma solução menos ótima do que poderia ser.

Fica a dica: explorar um pouco mais o mercado, antes de fechar algum negócio.

Recomendação de livro: Algoritmos para viver (https://amzn.to/2NxjGh4)

A little integer problem

A little problem to be solved using integer variables (in excel or aimms);

Suppose we have 5 forest stands, with the volumes given as below:

i	Vol
1	13.576,00
2	11.635,00
3	12.514,00
4	17.755,00
5	19.947,00

The distances to our basis in A or B are given below (these are random numbers).

	j
i	A	B
1	64	73
2	100	79
3	85	81
4	66	99
5	98	81

A and B both need at least 30.000 tons.

30000

30000

Suppose also when you harvest a stand, it’s completely to one of the destinies, A or B – it can’t be fractioned.

I want to minimize distances, subject to the constraints.

What’s the solution of this case?

The data is given below:

The decision variable is reserved in columns K and L.

The sumproduct per destiny must be greater than 30.000.

The distance is calculated multiplying vol*distance*decision variable

The objective function is the sum of distance*decision variable.

In solver, we include the constraints. And we want to minimize distances.

Because this test is very basic, there’s not much possibilities. In general, integer programming is difficult.

Other little detail: if we need necessary to harvest the plantation, the sum of the decision variable must be one. If not, it can be less or equal 1.

This is a simple example of integer optimization using solver.

---

Ideias técnicas com uma pitada de filosofia: https://ideiasesquecidas.com

Ferramentas Excel-VBA: https://ferramentasexcelvba.wordpress.com/

Otimizar Match

Sobre o puzzle de match de um site de relacionamento descrito abaixo, vamos fazer a formulação e resolver no excel – solver.

Fonte: PuzzleOR (http://puzzlor.com/)

A primeira coisa a fazer é transcrever os dados da tabela acima para o Excel.

Via fórmulas, nas colunas de K a Q, contamos o número de coincidências.

Esta fórmula verifica se o conteúdo das células é igual. Deve-se fazer fórmula semelhante para cada critério, e somar o número de pontos de cada match possível.

=SE(DESLOC($C$3;$K4;0) = DESLOC($C$3;$L4;0);1;0)

Transcrevo a tabela de pontos na aba “Formulação”, copiando e colando.

Agora, a formulação para resolver com o solver do Excel.

De C18 a L28, o espaço é reservado às variáveis de decisão.
Na célula C1, a função objetivo, um somarproduto da variável de decisão com os pontos.
=SOMARPRODUTO(C5:L14;C19:L28)

Quero maximizar tal função objetivo.

Quem não tiver o solver instalado, ir em Arquivo – Opções – suplementos do excel – suplementos

Acionar o solver (só é necessário fazer a primeira vez).

Em dados – solver, especificar:

• A função objetivo como a célula C1
• Células variáveis

Restrições:

• variáveis binárias (ou é zero ou 1)
• soma das linhas deve ser <= 1 (só posso fazer o match de uma mulher com um homem)
• soma das colunas deve ser <= 1 (só posso fazer o match de um homem com uma mulher)

O método deve ser LP Simplex (ou seja, é um Linear program que utiliza o método Simplex), e resolver.

A função objetivo vai assumir o valor 33, e os matches serão os valores 1 na tabela.

Com, isso, esperamos casar as pessoas com o maior número de características possíveis.

---

Ideias técnicas com uma pitada de filosofia: https://ideiasesquecidas.com

Ferramentas Excel-VBA: https://ferramentasexcelvba.wordpress.com/