Pythonová knižnica PuLP

Domovská stránka knižnice PuLP: https://coin-or.github.io/pulp/.

Inštalácia

Pythonový balíček PuLP si vieš nainštalovať pomocou inštalátora pip (z príkazového riadku pip install pulp, resp. vo Windows py -m pip install pulp).

Niektoré distribúcie Linuxu ho majú aj ako samostatný balíček vo svojom package manageri a nainštalovať ho môžeš aj odtiaľ (napr. apt install python3-pulp).

Inštalácia PuLPu by mala priamo v sebe obsahovať jeden decentný ILP solver, takže priamo po inštalácii by sme ho mali vedieť použiť na riešenie. PuLP však vie komunikovať s veľa rôznymi solvermi a môžeme si tak priamo v našom Pythonovom programe vybrať, ktorý z nich má použiť.

Po inštalácii PuLPu si môžeme z Pythonu nasledovne skontrolovať, že sa nainštaloval, a zistiť, ktoré solvery pozná a ktoré z nich aj vidí nainštalované a vie priamo použiť. (Viac o tom, ako PuLP presvedčiť, aby použil iný ako defaultný solver, je v dokumentácii.)

import pulp
print( pulp.listSolvers() ) # tieto solvery vie tvoja verzia PuLPu použiť
print( pulp.listSolvers(onlyAvailable = True) ) # tieto má naozaj dostupné

Príklad použitia: kuracie nugetky

Nasledovný dokumentovaný program v Pythone ukazuje, ako vieme priamo z Pythonu vyriešiť príkladovú úlohu s nugetkami.

import pulp

# vyrobíme si nový optimalizačný problém, v ktorom chceme maximalizovať

problem = pulp.LpProblem('Nugetky', pulp.LpMaximize)

# zadefinujeme si premenné, ktoré chceme používať
# cat ("category") je typ premennej, my budeme používať 'Integer' a 'Binary'

x1 = pulp.LpVariable('x1', cat='Integer', lowBound=0)
x2 = pulp.LpVariable('x2', cat='Integer', lowBound=0)
x3 = pulp.LpVariable('x3', cat='Integer', lowBound=0)

# do problému vieme pridávať nové informácie pomocou +=
# ak takto pridáme lineárny výraz z premenných a konštánt, pochopí ho ako cieľ
# ak pridáme podmienku, pochopí ju ako obmedzenie

problem += 6*x1 + 9*x2 + 20*x3 # cieľ

problem += 200*x1 + 290*x2 + 610*x3 <= 3200 # obmedzenie

# ak chceme, môžeme si problém dať vypísať a skontrolovať si ho
# print(problem)

# ak chceme, môžeme si problém dať uložiť do súboru vo formáte, ktorému rozumie viacero solverov
# problem.writeMPS('nugetky.mps')

# spustíme solver

status = problem.solve()

# alternatíva: použitie iného solveru
# status = problem.solve( pulp.GLPK_CMD(msg=False) ) # msg=False vypne tomuto solveru výstup na stdout

# skontrolujeme, že solver našiel optimálne riešenie

assert pulp.LpStatus[status] == 'Optimal'

# vypíšeme si hodnotu riešenia a následne hodnoty jednotlivých premenných

# pulp nám interne vráti floaty, my vieme, že naše odpovede sú celé čísla, pre istotu ich pri konverzii zaokrúhlime

def to_int(x): return int(round(x))

# pulp.value nám vypočíta hodnotu výrazu obsahujúceho premenné, napr. cieľu, ktorý sme optimalizovali

print( 'optimálny počet nugetiek:', to_int( pulp.value( problem.objective ) ) )

# premenné aj samé poznajú svoju hodnotu, ale rovnako sme mohli použiť pulp.value(premenna)

for premenna in [x1, x2, x3]: print( premenna.name, '=', to_int(premenna.varValue) )