Resolvendo o Set Cover com OpenSolver e Pyomo

A ideia deste exercício é resolver o problema da cobertura de conjuntos, utilizando o Pyomo (http://www.pyomo.org/) e o OpenSolver (www.opensolver.org).

Link para download: https://github.com/asgunzi/SetCover.

O Set cover é o problema de cobertura de conjuntos.

Tenho uma quantidade de elementos, digamos 50.

E tenho uma quantidade de conjuntos, digamos 15.

Cada conjunto tem um preço (abaixo está como peso), e cada conjunto contém os elementos.

Algumas aplicações: imagine que há várias doenças, e uma série de vacinas. Cada vacina cobre um conjunto diferente de doenças, e cada vacina tem um custo. Minimizar o custo total, cobrindo todas as doenças.

Open Solver:

Variável de decisão binária: utilizo ou não o conjunto.

Função objetivo: se utilizo o conjunto, é o preço deste.

Restrição: devo cobrir todos os elementos.

Resultado: FO de 223 e as escolhas pintadas em rosa.

Formulação Pyomo:

Leitura de dados utilizando o módulo pandas.

    df1 = pd.read_excel(io=’SetCover_Instancia01.xlsm’, sheet_name=’Base’, usecols = “B:P”, skiprows = 1, nrows = 1,header = None)

    df2 = pd.read_excel(io=’SetCover_Instancia01.xlsm’, sheet_name=’Base’, usecols = “B:P”, skiprows = 7, header = None)

    Nsets =  len(df1.columns)

    Nelementos =  len(df2)

Crio o model com o primeiro comando abaixo. Defino os índices (conjuntos e elementos).

   #—————- Modelo Pyomo ————#     

    model = ConcreteModel()

    model.S = list(range(0,Nsets)) #Num sets

    model.E = list(range(0,Nelementos)) #Num elementos

Defino a variável de decisão com o comando Var. O nome da variável é AtivaSet, ela é binária e inicializa com o valor zero.

    model.AtivaSet = Var(model.S, within=Binary, initialize=0)

Função objetivo.

Soma do produto entre a variável de decisão e o peso de cada conjunto.

def obj_rule(model):

        return sum(model.AtivaSet[s]*pesos[s] for s in model.S)

model.obj = Objective(rule = obj_rule, sense=minimize)

Restrição.

Para cada elemento, ele deve pertencer a um conjunto, ou seja, a soma do produto da matriz de alocação e a variável de decisão devem ser maior do que 1.

    def constrAlocacao(model, e):

        return sum(model.AtivaSet[s]*Malocacao[e][s] for s in model.S) >= 1

    model.restr1 = Constraint(model.E, rule = constrAlocacao)      

Algumas configurações do solver, e depois mando resolver

    SOLVER_NAME = ‘cbc’

    TIME_LIMIT = 60*1   #Em segundos

    solver = SolverFactory(SOLVER_NAME)

    solver.options[‘seconds’] = TIME_LIMIT

    results  = solver.solve(model)

    results.write() #para mostrar o status da solucao

O resultado obtido foi o mesmo do OpenSolver.

Além do CBC, outro solver free é o GLPK.

Todos os outros são pagos. O Pyomo pode chamar CPLEX, Gurobi, se tiver a licença destes.

Toda a manipulação de entrada de dados, matrizes, e saída de dados, é Python puro.

Vantagens: é free, e muito melhor que o Open Solver para manipular grande quantidade de dados.

Desvantagens: requer um grau maior de conhecimento que o OpenSolver. Não é tão fácil de manipular ou tão poderoso quanto um AIMMS + CPLEX.

Finalistas do Edelman 2020

Parabéns aos finalistas do Prêmio Edelman 2020, promovido pela Informs!

São eles Amazon, Carnival PLC (maior empresa de cruzeiros do mundo), Deutsche Bahn (empresa de ferrovias alemã), IBM, Intel e Walmart. Só gigantes!

As linguagens do Analytics

No último fórum da Informs (a mais importante associação americana de Operations Research), em Chicago, citaram Pythons umas 6 vezes, Excel também umas 6 vezes, Java uma vez (de um fornecedor que disse que estava mudando para Python), R nenhuma mênção.

Isto mostra a força do Python como a língua franca do Analytics da atualidade.

O pessoal que citou Excel o fez metade das vezes para falar mal, outra metade para dizer que o usuário final utiliza. Isto mostra a resiliência do Excel, que apesar de todas as críticas, continua firme e forte nas grandes corporações – por seu poder e facilidade de uso. Há até uma piada que diz: “Todo o sistema financeiro mundial é baseado em Excel”.

Um último comentário: no final das contas, não interessa muito a linguagem, e sim ter uma base teórica forte e capacidade de execução. Linguagens e ferramentas vêm e vão. Até hoje tem gente utilizando Fortran muito bem, por exemplo.

https://ideiasesquecidas.com/

Shadow price

The excel solver has a feature of sensibility analysis.

For example, we want to maximize a linear programming like this.

Run solver, and select the reports you want to see:

The sensibility will be in another spreadsheet.

What does a shadow price means?

For example, the shadow price for constraint2 is equal to 4.

It means that if I increase the right hand size of constraint2 in one unit, the objective function will increase 4 units.

Lets test it:

If I increase constraint2, from 166 to 167, and run solver again, the results will be as below.

The FO was previously 709. Now, it is 713, because the shadow price for this constraint is 4.

If shadow price is zero, it means this constraint is not restricting the problem.

One detail. If I increase too much the value of the RHS of the restriction, it can give another optimal solution.

The maximum I can increase is 14, according to the column “Permitido aumentar” in the Excel report.

Take a look in the file.

Open solver

A tip of a great tool.

Open solver is an Excel addin. It is very similar to the MS solver. The difference is that the default solver has a limit of around 5000 variables. Above this, the user has to purchase the Frontline solver (the name of the company).

Page: https://opensolver.org

To use opensolver, just download, unpack and add it to the Excel supplements.

A good evolution of openSolver is solverStudio, from the same developer. It allows a formulation of the problem using formulas, supports more optimization languages and is faster. But it is also a bit more complex to deal with.

Solver studio https://solverstudio.org

Both of these tools are able to use any solver. The package comes with CBC, the great open source solver from COIN-OR. https://www.coin-or.org/

Frontline solver:

https://www.solver.com/

Ideias técnicas com uma pitada de filosofia

https://ideiasesquecidas.com/