Modelagem e resolução de problemas de otimização em Python

A Pesquisa Operacional (P.O.) envolve experimentos com modelos de otimização. O objetivo é encontrar o melhor design, plano ou decisão para um sistema ou ser humano. Consequentemente, esses modelos consistem em objetivos e restrições. No entanto, a maioria dos pacotes ou software disponíveis para OR não são de código aberto. Assim, o ritmo de transferência de conhecimento ou mesmo reprodutibilidade dos resultados gerados pelos modelos de otimização foi reduzido. Além disso, os pacotes de otimização ou software disponíveis não fornecem o mesmo nível de flexibilidade que conhecemos, por exemplo. Uma linguagem de programação como Python. Além disso, a maioria dos softwares ou pacotes disponíveis não são fáceis de usar.

No geral, construir sobre resultados anteriores em OR sempre foi difícil e demorado, em comparação com outros campos da ciência da computação, como aprendizado de máquina (ML) e simulação (SM). Da mesma forma, neste blog, estamos motivados a apresentar e revisar interfaces de alto nível populares para modelagem de problemas de otimização em Python. Como resultado, os analistas de SCM e OR podem aproveitar ferramentas melhores e mais flexíveis.

Notavelmente, nos concentramos em pacotes que podem modelar e resolver programas lineares de número inteiro misto. Uma linguagem de programação de alto nível, como Python, é usada para formular um problema. O problema é então resolvido por otimizadores (solucionadores) escritos em linguagens de baixo nível.

Diferença entre interfaces de modelagem e solucionadores em Python

A princípio, a diferença entre interfaces de modelagem (linguagens de modelagem) e solucionadores de problemas de otimização deve ser enfatizada e explicada:

  • Uma interface:
    • Compreende uma linguagem específica para comandos (sintaxe).
    • Depende da linguagem de programação.
    • Retorna um arquivo intermediário que um solver lê como sua entrada (por exemplo, nos formatos .mps, .lp, .nl, .osil, .gms).
    • Pode selecionar um dos vários solucionadores ao resolver um problema.
    • Está disponível gratuitamente para qualquer linguagem de programação.
    • Fornece ferramentas de construção de modelos e estruturas de dados básicos.
    • Define os parâmetros do solucionador.
  • Um solucionador:
    • Pode ser comercial (é melhor) ou de código aberto (pode ser inferior na solução de problemas de otimização em larga escala).
    • Pode ter uma interface específica para si mesmo.
    • Fornece bibliotecas que as linguagens de programação entendem.
    • Faz fatoração, análise de arquivos, análise de parâmetros, pré solução, matriz esparsa, armazenamento de matrizes, gerenciamento de memória e tempo.
    • Retorna informações descrevendo a solução e o status do problema de otimização.

Um problema de teste

Consideremos o seguinte modelo de otimização:

O espaço de solução (região viável) (como x é uma variável de decisão discreta e y é uma variável de decisão contínua) pode ser derivada graficamente como segue:

De acordo com o gradiente do objetivo (a seta vermelha) e a direção da otimização (maximização), o ponto verde é a solução ótima, na qual x=1 x=1, y=1 y=1 e o valor ótimo do objetivo é 7. Resolvemos este modelo simples de programação linear inteira mista com sete pacotes de interface em Python e analisamos sua sintaxe e semelhanças.

1. Otimização com MIP em Python

Python-MIP:

  • Linguagem de modelagem para programação linear e programação linear inteira mista em Python.
  • Solventes suportados: CLP, CBC, Gurobi.

O seguinte código comentado visa resolver o modelo proposto de programação linear mista com “mip” (o nome do pacote) em Python:

# Instalação (Retire o comentário da linha)
#!pip instalar mip

# Pacote de importação
import mip as op

# Definir ambiente
prob = op.Model("MyOptProblem")

# Definir variáveis de decisão
x = [prob.add_var(var_type=op.INTEGER) for i in range(1)]
y = [prob.add_var() for i in range(1)]

# Adicionar função objetiva ao meio ambiente
prob.objective = op.maximize(2*x[0]+5*y[0])

# Adicionar restrições ao meio ambiente
prob += 5*x[0]+3*y[0]<=10
prob += 2*x[0]+7*y[0]<=9

# O status da solução
print(prob.optimize())

# Para exibir as variáveis de decisão ideais
print('x: ',  x[0].x)
print('y: ',  y[0].x)

# Para exibir o valor ideal da função objetiva
print("Optimal Value of Objective Is = ",prob.objective_value)

2. Otimização com PuLP em Python

PuLP:

  • Linguagem de modelagem para programação linear e programação linear inteira mista em Python.
  • Solventes suportados: GLPK, COIN-OR CLP/CBC, CPLEX, GUROBI, MOSEK, XPRESS, CHOCO, MIPCL, SCIP.

O seguinte código comentado visa resolver o modelo proposto de programação linear inteira mista com “pasta” (o nome do pacote) em Python:

# Instalação (Retire o comentário da linha)
# !pip instalar PuLP

# Pacote de importação
import PuLP as op

# Definir ambiente e direção de otimização
prob = op.LpProblem("MyOptProblem", op.LpMaximize)

# Definir variáveis de decisão
x = op.LpVariable("x", lowBound = 0, upBound = None, cat='Continuous')
y = op.LpVariable("y", lowBound = 0, upBound = None, cat='Integer')

# Adicionar função objetiva ao meio ambiente
prob += 2*x+5*y, "Objective"

# Adicionar restrições ao meio ambiente
prob += 5*x+3*y<=10, "Constraint1"
prob += 2*x+7*y<=9,  "Constraint2"

# Resolver o problema (outros solucionadores: prob.solve(SOLVERNAME()))
prob.solve()

# O status da solução
print("Status:", op.LpStatus[prob.status])

# Para exibir as variáveis de decisão ideais
for variables in prob.variables():
    print(variables.name, "=", variables.varValue)

# Para exibir o valor ideal da função objetiva
print("Optimal Value of Objective Is = ", op.value(prob.objective))

3. Otimização com Pyomo em Python

Pyomo:

  • Linguagem de modelagem para programação linear, programação quadrática, programação não linear, programação linear inteira mista, programação quadrática inteira mista, programação não linear inteira mista, programação estocástica, programação disjuntiva generalizada, equações algébricas diferenciais, programação de dois níveis e programas matemáticos com restrições de equilíbrio em Python.
  • Solucionadores com suporte: Visite este link.

O seguinte código comentado visa resolver o modelo proposto de programação linear inteira mista com “pyomo” (o nome do pacote) em Python:

# Instalação (Retire o comentário da linha)
# !pip instalar pyomo

# Pacote de importação
import pyomo.environ as op

# Definir ambiente
prob = op.ConcreteModel("MyOptProblem")

# Definir variáveis de decisão
prob.x = op.Var([1],domain=op.NonNegativeReals)
prob.y = op.Var([1],domain=op.PositiveIntegers)

# Adicionar função objetiva ao meio ambiente
prob.OBJ = op.Objective(expr=2*prob.x[1]+5*prob.y[1])

# Adicionar restrições ao meio ambiente
prob.Constraint1 = op.Constraint(expr=5*prob.x[1]+3*prob.y[1]<=10)
prob.Constraint2 = op.Constraint(expr=2*prob.x[1]+7*prob.y[1]<=9)

# Resolva o problema
solver = op.SolverFactory('SOLVERNAME')
results = solver.solve(prob)

# Para exibir resultados
print(results)

4. Otimização com Google OR-Tools em Python

Google OR-Tools:

  • Linguagem de modelagem para programação restrita, programação linear, e programação linear mista.
  • Solventes suportados: Gurobi, CPLEX, SCIP, GLPK, GLOP, CP-SAT.

O seguinte código comentado visa resolver o modelo proposto de programação linear mista com “ortools” (o nome do pacote) em Python:

# Instalação (Retire o comentário da linha)
# !pip instala ortoferramentas

# Pacote de importação
from ortools.linear_solver import pywraplp

# Definir ambiente
def prob():

#(Outros solvers: pywraplp.Solver.Solver.CreateSolver('SOLVERNAME'))
    op = pywraplp.Solver.CreateSolver('SCIP')
 
# Definir variáveis de decisão   
    x = op.NumVar(0.0, op.infinity(), 'x')
    y = op.IntVar(0.0, op.infinity(), 'y')

# Adicionar função objetiva ao meio ambiente
    op.Maximize(2*x+5*y)

# Adicionar restrições ao meio ambiente
    op.Add(5*x+3*y<=10)
    op.Add(2*x+7*y<=9)

# Resolva o problema
    status = op.Solve()

# O status da solução
    if status == pywraplp.Solver.OPTIMAL:
        print('Solution:')
        print('Objective value =', op.Objective().Value())
        print('x =', x.solution_value())
        print('y =', y.solution_value())
    else:
        print('The problem does not have an optimal solution.')

if __name__ == '__main__':
    prob()

5. com Pymoo em Python

pymoo:

  • Linguagem de modelagem para todos os tipos de problemas de otimização de um e vários objetivos, sem restrições e com restrições.
  • Solventes suportados: Algoritmos meta-heurísticos que são introduzidos neste link.

O seguinte código comentado visa resolver o modelo proposto de programação linear inteira mista com “pymoo” (o nome do pacote) em Python:

# Instalação (Retire o comentário da linha)
#!pip instalar pymoo

# Importar pacotes
import numpy as np
from pymoo.core.problem import Problem
from pymoo.algorithms.moo.nsga2 import NSGA2
from pymoo.factory import get_sampling, get_crossover, get_mutation
from pymoo.factory import get_termination
from pymoo.optimize import minimize

termination = get_termination("n_gen", 40)

# Solucionador do problema
algorithm = NSGA2(
    pop_size=400,
    n_offsprings=10,
    sampling=get_sampling("real_random"),
    crossover=get_crossover("real_sbx", prob=0.9, eta=15),
    mutation=get_mutation("real_pm", eta=20),
    eliminate_duplicates=True
)

# Definir ambiente
class MyOptProblem(Problem):
    def __init__(self):

# Definir variáveis de decisão
        largenumber = 10^10
        super().__init__(n_var=2,
                         n_obj=1,
                         n_constr=2,
                         xl=np.array([0,0]),
                         xu=np.array([largenumber,largenumber]))

    def _evaluate(self, x, out, *args, **kwargs):
        
# Adicionar função objetiva ao meio ambiente
        f1 = -2*x[:,0] + -5*np.round(x[:,1])
        out["F"] = np.column_stack([f1])
        
# Adicionar restrições ao meio ambiente
        g1 = 5*x[:,0] + 3*np.round(x[:,1]) - 10
        g2 = 2*x[:,0] + 7*np.round(x[:,1]) - 9
        out["G"] = np.column_stack([g1, g2])
       
prob = MyOptProblem()

# Resolva o problema 
res = minimize(prob,
               algorithm,
               termination,
               seed=2,
               save_history=True,
               verbose=False)

# Mostrar resultados
print("Optimal Value of Objective Is = ", -res.F[0])

6. Otimização com GEKKO em Python

GEKKO:

  • Linguagem de modelagem para programação linear, quadrática, não linear e mista de números inteiros em larga escala.
  • Solventes suportados: APOPT, BPOPT, IPOPT, SNOPT, MINOS.

O seguinte código comentado visa resolver o modelo proposto de programação linear mista com “gekko” (o nome do pacote) em Python:

# Instalação (Retire o comentário da linha)
#!pip instalar gekko

# Importar pacotes
from gekko import GEKKO

# Definir ambiente
prob = GEKKO(remote=False)

# Definir variáveis de decisão
x = prob.Var(lb=0,ub=None,integer=True)
y = prob.Var(lb=0,ub=None)

# Adicionar função objetiva ao meio ambiente
prob.Obj(-(2*x+5*y)) # Objective

# Adicionar restrições ao meio ambiente
prob.Equation(5*x+3*y<=10)
prob.Equation(2*x+7*y<=9)

# Resolver o problema (1: MINLP solver, 2,3: Outros Solucionadores)
prob.options.SOLVER=1  
prob.solve(disp=False) 

# Mostrar resultados
print('Results')
print('x: ' + str(x.value))
print('y: ' + str(y.value))
print('Optimal Value of Objective Is = ' + str(-prob.options.objfcnval))

7. Otimização com PICOS em Python

PICOS:

  • Linguagem de modelagem para vários problemas de programação cônica e inteira.
  • Solventes suportados: Visite este link.

O seguinte código comentado visa resolver o modelo proposto de programação linear inteira mista com “picos” (o nome do pacote) em Python:

# Instalação (Retire o comentário da linha)
# !pip instalar picos

# Pacote de importação
import picos as op

# Definir ambiente
prob = op.Problem("MyOptProblem")

# Definir variáveis de decisão
x = op.RealVariable("x", lower = 0)
y = op.IntegerVariable("y", lower = 0)

# Adicionar função objetiva ao meio ambiente
prob.set_objective('max', 2*x+5*y)

# Adicionar restrições ao meio ambiente
prob += 5*x+3*y<=10
prob += 2*x+7*y<=9

# Resolva o problema
prob.solve(solver='glpk')

# Para exibir resultados
print('x: ',  x.value)
print('y: ',  y.value)
print("Optimal Value of Objective Is = ", prob.obj_value())

Leave a Reply

Deixe um comentário

O seu endereço de e-mail não será publicado.

Esse site utiliza o Akismet para reduzir spam. Aprenda como seus dados de comentários são processados.

Close

Meta