Como esta é uma dúvida frequente, destaco neste post.
Se o solver não estiver habilitado, ir em Arquivos -> Opções -> Suplementos
Ir… em Suplementos do Excel, e habilitar o Solver.
O Solver estará na aba Dados do Excel.
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 é 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
Como adicionar o OpenSolver nas referências do VBA?
Ir em Ferramentas -> Referências
Adicionar o OpenSolver e clicar em OK.
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.
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.
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.
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.
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.
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:
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.
“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:
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:
Fica já o convite, quem quiser escrever sobre alguns dos temas e divulgar ali.
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?
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).
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
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
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
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/
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.
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 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/
Ferramentas em Excel-Vba 
Você precisa fazer login para comentar.