Überblick

Wir verwenden in der Lehrveranstaltung das Python-Paket PuLP. PuLP ist ein Open-Source-Projekt und frei verfügbar. PuLP ist eine algebraische Modellierungssprache zur benutzerfreundlichen Formulierung von mathematischen Optimierungsproblemen. Zum Lösen eines mit PuLP formulierten Optimierungsproblems wird ein Solver benötigt. PuLP beinhaltet den Open Source Solver CbC und unterstützt eine Vielzahl von weiteren Open-Source sowie kommerziellen Solvern, die aber zusätzlich installiert werden müssen.

Alternativen

In diesem Abschnitt geben wir einen Überblick über andere High-Level Software zur Formulierung von Optimierungsproblemen, weil:

  • Die Links führen Sie zu vielen, oft sehr guten Tutorials inkl. Code-Beispielen.
  • In Realprojekten ist es wichtig, das passende Software-Setting unter Berücksichtigung folgender Punkte auszuwählen: kommerziell versus open source, Schnittstellen zu Programmiersprachen, Benutzerfreundlichkeit, Performance etc.. Dafür sollte man seinen Überblick über die LP-Software aktuell halten.

Liste von bekannten Algebraischen Modellierungssprachen:

Für Python gibt es unter anderem folgende Modellierungs- und Entwicklungsumgebungen für (MI)LPs:

Solver

Liste der bekanntesten Solver:

  • CBC: open source solver
  • HiGHs: open source solver
  • GLPK: open source solver
  • SCIP Optimization Suite: non-commercial solver for mixed integer programming (MIP) and mixed integer nonlinear programming (MINLP)
  • lp_solve: open source solver
  • Gurobi: commercial solver, academic license available
  • Cplex: commercial solver and interface, academic license available
  • Xpress: commercial solver
  • Ipopt: open source software package fo large-scale nonlinear optimization, documentation

Installation

  • In Anaconda und Miniconda: conda install -c conda-forge pulp
  • Allgemein mit pip: pip install pulp

Beispiel

Der folgende Code implementiert das blending problem mit PuLP und löst es mit dem CBC-Solver.

Problemstellung

Whiskas wants to make their cat food out of just two ingredients: chicken and beef. The company wants to meet certain nutritional requirements, and do so at a minimum cost. The table below shows the nutritional content of each ingredient per gram .

Nutrient Chicken Beef
Protein 0.100 0.200
Fat 0.080 0.100
Fibre 0.001 0.005
Salt 0.002 0.005

The price of chicken is 0.013 USD per gram, and the price of beef is 0.008 USD per gram. The company has the following nutritional requirements for the cat food:

  • at least 8.0 % protein
  • at least 6.0 % fat
  • at most 2.0 % fibre
  • at most 0.4 % salt

LP-Formulierung

Decision variables:

  • \(x_1\): percentage of chicken in the cat food
  • \(x_2\): percentage of beef in the cat food

\[ \begin{aligned} \min \; 0.013x_1 + 0.008x_2 & \\ \text{s. t.} \; x_1 + x_2 & = 100 \\ 0.100x_1 + 0.200x_2 & \geq 8.0 \\ 0.080x_1 + 0.100x_2 & \geq 6.0 \\ 0.001x_1 + 0.005x_2 & \leq 2.0 \\ 0.002x_1 + 0.005x_2 & \leq 0.4 \\ x_1, x_2 & \geq 0 \end{aligned} \]

Ausführliche Implementierung

Zuerst importieren wir das Paket pulp, und dann modellieren wir das Problem in einer ausführlichen Form:

Code 
import pulp

# Create the 'prob' object to contain the problem data:
prob = pulp.LpProblem("Whiskas_problem", pulp.LpMinimize) 
# Note: no space in the name!

# Create variables for beef and chicken with a lower limit of zero: 
# help(pulp.LpVariable)  # check the documentation!
x1 = pulp.LpVariable("chicken_percent", 
    lowBound=0, upBound=None, cat='Continuous')
x2 = pulp.LpVariable("beef_percent", 
    lowBound=0, upBound=None, cat='Continuous')

# The objective function is added to 'prob' first!
obj = 0.013*x1 + 0.008*x2
prob += (obj, "total cost of ingredients per 100 gram")

# The five constraints are added to 'prob' as tupes with two elements: 
# the constraint and a string with a name for the constraint.
c1 = x1 + x2 == 100
prob += (c1, "percentages sum")
c2 = 0.100*x1 + 0.200*x2 >= 8.0
prob += (c2, "protein requirement")
c3 = 0.080*x1 + 0.100*x2 >= 6.0
prob += (c3, "fat requirement")
c4 = 0.001*x1 + 0.005*x2 <= 2.0
prob += (c4, "fibre requirement")
c5 = 0.002*x1 + 0.005*x2 <= 0.4
prob += (c5, "salt requirement")
print(prob)
Whiskas_problem:
MINIMIZE
0.008*beef_percent + 0.013*chicken_percent + 0.0
SUBJECT TO
percentages_sum: beef_percent + chicken_percent = 100

protein_requirement: 0.2 beef_percent + 0.1 chicken_percent >= 8

fat_requirement: 0.1 beef_percent + 0.08 chicken_percent >= 6

fibre_requirement: 0.005 beef_percent + 0.001 chicken_percent <= 2

salt_requirement: 0.005 beef_percent + 0.002 chicken_percent <= 0.4

VARIABLES
beef_percent Continuous
chicken_percent Continuous

Nun lösen wir das Problem mit einem Solver und geben die Ergebnisse aus:

Code 
# Solve using PuLP's COIN-CBC-Solver or some other installed solver:
# If you set the msg argument to True, then the solver will 
# print output as it solves the problem.
prob.solve(pulp.COIN(msg=True))  # CBC is the default solver included in PuLP
# prob.solve(pulp.COIN(msg=False)) 
# prob.solve(pulp.HiGHS_CMD(msg=False)) # HiGHs is another open source solver
# prob.solve(pulp.GLPK(msg=False))      # GLPK is another open source solver
# prob.solve(pulp.GUROBI(msg=False))    # Gurobi is a commercial solver

# status of the solution:
print(f"status: {pulp.LpStatus[prob.status]}")

# optimal values of the variables:
print("optimal decisions:")
for v in prob.variables():
    print(f"  {v.name} = {v.varValue:.2f} %")

# optimal value:
print(f"optimal cost = {pulp.value(prob.objective):.2f} USD per 100 g")
Welcome to the CBC MILP Solver 
Version: 2.10.11 
Build Date: Oct 26 2023 

command line - cbc /tmp/331944b35e5240f68af14afa11ab2435-pulp.mps -timeMode elapsed -branch -printingOptions all -solution /tmp/331944b35e5240f68af14afa11ab2435-pulp.sol (default strategy 1)
At line 2 NAME          MODEL
At line 3 ROWS
At line 10 COLUMNS
At line 23 RHS
At line 29 BOUNDS
At line 30 ENDATA
Problem MODEL has 5 rows, 2 columns and 10 elements
Coin0008I MODEL read with 0 errors
Option for timeMode changed from cpu to elapsed
Presolve 0 (-5) rows, 0 (-2) columns and 0 (-10) elements
Empty problem - 0 rows, 0 columns and 0 elements
Optimal - objective value 0.96666667
After Postsolve, objective 0.96666667, infeasibilities - dual 0 (0), primal 0 (0)
Optimal objective 0.9666666667 - 0 iterations time 0.002, Presolve 0.00
Option for printingOptions changed from normal to all
Total time (CPU seconds):       0.00   (Wallclock seconds):       0.00

status: Optimal
optimal decisions:
  beef_percent = 66.67 %
  chicken_percent = 33.33 %
optimal cost = 0.97 USD per 100 g

Kompakte Implementierung

Nun das selbe in einer kompakteren Form:

Code 
prob = pulp.LpProblem("Whiskas_problem", pulp.LpMinimize)
x1 = pulp.LpVariable("x1", 0, None, "Continuous")
x2 = pulp.LpVariable("x2", 0, None, "Continuous")
prob += 0.013*x1 + 0.008*x2
prob += x1 + x2 == 100
prob += 0.100*x1 + 0.200*x2 >= 8.0
prob += 0.080*x1 + 0.100*x2 >= 6.0
prob += 0.001*x1 + 0.005*x2 <= 2.0
prob += 0.002*x1 + 0.005*x2 <= 0.4
print(prob)

prob.solve(pulp.COIN(msg=False))
print(f"status: {pulp.LpStatus[prob.status]}")
print(f"optimal cost = {pulp.value(prob.objective):.2f} USD per 100 g")
print(f"{x1.value() = :.2f} %")
print(f"{x2.value() = :.2f} %")
Whiskas_problem:
MINIMIZE
0.013*x1 + 0.008*x2 + 0.0
SUBJECT TO
_C1: x1 + x2 = 100

_C2: 0.1 x1 + 0.2 x2 >= 8

_C3: 0.08 x1 + 0.1 x2 >= 6

_C4: 0.001 x1 + 0.005 x2 <= 2

_C5: 0.002 x1 + 0.005 x2 <= 0.4

VARIABLES
x1 Continuous
x2 Continuous

status: Optimal
optimal cost = 0.97 USD per 100 g
x1.value() = 33.33 %
x2.value() = 66.67 %