Implementierungen
Fix and Optimize mit abstrakten Unfixierern
Ausgangslage
In diesem Artikel entwerfe ich ein simples Fix-and-Optimize Framework mit Hilfe der Google OR-Tools und abstrakten Fixier-Klassen.
Fix-and-Optimize
Egal welches Problem mit Fix-and-Optimize gelöst werden soll, der Ansatz ist immer sehr ähnlich:
Die Variablen (i.d.R. die binären- und/oder ganzzahligen Variablen) eines mathematischen Optimierungsmodells werden in zwei Teilmengen aufgeteilt:
- Eine Menge von Variablen deren Werte fixiert sind (z.B. auf 0 oder 1) und die vom Solver nicht verändert werden dürfen
- Eine kleine Menge von Variablen, deren Wert nicht fixiert sind und deren Werte (unter berücksichtigung der fixierten Variablen) vom Solver bestimmt werden sollen.
Vorteil: Es muss nur eine kleine Anzahl von Entscheidungen durch den Solver getroffen werden. Das korrespondierende mathematische Optimierungsmodell kann meist sehr schnell gelöst werden.
Nachteil: Die Lösungen sind nicht zwingend optimal.
Schematischer Ablauf
erzeuge Startlösung
while Abbruchkriterium nicht erfüllt:
löse die Fixierung einiger Variablen (gemäß eines Musters)
löse das resultierende MIP
if Lösung ist besser als beste Bekannte:
aktualisiere beste Lösung
fixiere alle Variablen auf ggf. neue WerteWir müssen also sicherstellen, dass drei zentrale Konzepte implementiert werden:
- Ein mathematisches Optimierungsmodell
- Eine Fixierungsroutine, die die Werte von Variablen fixiert (Fix)
- Eine Routine, die gemäß einer Logik Variablenwerte für den Solver veränderbar macht (Optimize)
- Ein iteratives Vorgehen, das fixiert und löst und Lösungen updated. (Fix and Optimize)
Die konkreten Ausprägungen der beiden Konzepte sind stark problemspezifisch. So fixieren wir in eine Standortplanungsproblem eher eröffnete Standorte, während in einem Losgrößenplanungsproblem Rüstperioden fixiert werden.
(Abstraktes) Mathematisches Optimierungsmodell
Jede Fix-and-Optimize Heuristik benötigt ein mathematisches Optimierungsmodell. Unabhängig davon, welches Modell gewählt wird, sind für das Verfahren zwei Funktionen relevant:
- das Anstoßen des Lösungsvorgangs
- das Abrufen des Zielfunktionswerts
Deswegen wird die abstrakte Modellklasse unter Verwendung der Google ORTools wie folgt entworfen:
Wir importieren die notwendigen Packages, erstellen eine abstrake MIP Klasse und eine Hilfsklasse, die später genutzt wird.
from ortools.linear_solver import pywraplp # OR Tools Solver Framework
from abc import ABC # Abstrakte Klassen
class MipModel(ABC):
def __init__(self,name="mip") -> None:
self.solver = pywraplp.Solver(name,pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)
def solve(self):
# Anstoßen des Lösungsvorgangs
self.solver.Solve()
def objective(self):
# Rückgabe des Zielfunktionswerts
return self.solver.Objective().Value()
# Speichert Variablenwerte zwischen
@dataclass
class VarValueStorage:
variable : object
value : floatBeispielimplementierung: MIP SLULSP
Nachfolgend eine Beispielimplementierung für das SLULSP
class Slulsp(MipModel):
def __init__(self, d, s, l):
# Initialisiert die Init Funktion aus der abstrakten Klassen
super().__init__("SLULSP")
T = len(d) # Perioden
M = sum(d) # Big-M als Summe der Nachfragen
# Variablen: Lager (L), Menge (x), Rüsten (y)
self.L = [self.solver.NumVar(0, self.solver.infinity(), f"L{t}") for t in range(T)]
self.x = [self.solver.NumVar(0, self.solver.infinity(), f"x{t}") for t in range(T)]
self.y = [self.solver.BoolVar(f"y{t}") for t in range(T)]
# Nebenbedingungen
for t in range(T):
# Lagerbilanz: L[t-1] + x[t] - d[t] = L[t] (L[-1] ist 0)
prev_L = self.L[t-1] if t > 0 else 0
self.solver.Add(prev_L + self.x[t] - d[t] == self.L[t])
# Setup-Bedingung
self.solver.Add(self.x[t] <= M * self.y[t])
# Zielfunktion
self.solver.Minimize(self.solver.Sum(l * self.L[t] + s * self.y[t] for t in range(T)))Fixierung und unfixierung von Variablen: Generelle Idee
Wenn die Heuristik von vornherein einigermaßen effizient implementiert werden soll, dann betrachten wir in jeder Iteration nur die Variablen, die wir wieder veränderbar (optimierbar) machen lassen wollen. Alle anderen Variablen des Modells lassen wir unangetastet. Bei diesem Ansatz stellen wir das Modell einmalig auf und lösen es mehrfach.
Wir gehen wir folgt vor:
-
Variablen fixieren: Dies gelingt, indem wir festlegen, dass die Lowerbound einer Variable der Upperbound entspricht. Wollen wir beispielsweise festlegen, dass eine Binärvariable
variableauf 0 fixiert werden soll, dann nutzen wirvariable.SetBounds(0,0), um die Lowerbound (erste 0) und Upperbounds (zweite 0) auf Null zu setzen. Soll die Variable auf 1 fixiert werden, schreiben wirvariable.SetBounds(1,1). -
Variablen veränderbar machen: Hier legen wir fest, dass die Lowerbound nicht mehr der Upperbound entsprechen muss, d.h. wir rufen
variable.SetBounds(0,1)auf, so dass die Variable wieder die Werte 0 oder 1 annehmen kann.
Problem
Sobald die Lower- bzw. Upperbound irgendeiner Variable im Modell verändert wird, werden alle aktuellen Lösungswerte, die die Variablen haben zurückgesetzt.
Dieser Umstand wird dann problematisch, wenn wir nacheinander die Bounds einer Variable auf den Wert einer aktuellen Lösung fixieren wollen. Denn mit er Fixierung der ersten Variable, sind die weiteren Werte nicht mehr abrufbar.
Lösung
- Wir speichern die Variablenwerte einer Lösung in der Hilfsklasse
VarValueStoragezwischen - Nach dem speichern aller gewünschten Variablenwerte fixieren wir die Variablen anschließeund in der Fixierungsroutine.
Beispiel anhand von SLULSP (crasht)
# Initialsiert
d= [10,20,30,10]
s = 10
l = 5
mip = Slulsp(d,s,l)
mip.solve()
for y in mip.y:
# Crasht ab der 2. Iteration
wert = y.solution_value()
# Fixiert y auf den Wert der letzten gefundenen Lösung
y.SetBounds(wert,wert)Beispiel anhand von SLULSP (crasht nicht mehr)
mip = Slulsp(d,s,l)
mip.solve()
zwischenspeicher = []
# Schritt 1) Erst alle Werte speichern
for y in mip.y:
wert = y.solution_value()
zwischenspeicher.append(VarValueStorage(y, wert))
# Schritt 2) Dann alle Werte fixieren
for zw_speicher in zwischenspeicher:
zw_speicher.variable.SetBounds(zw_speicher.value, zw_speicher.value)Abstrakte Unfixer/Fixer Klasse
Mit dem zuvor dargestellten Ansatz entwerfen wir jetzt ein Unfixer Klasse. Hier werden je nach Problemstellung unterschiedliche Ansätze implementiert, um Variablen wieder veränderbar zu machen:
Ablauf
- Wir wählen in
select_variables_to_unfix()Variablen gemäß einer Logik aus, deren Werte wieder 0 oder 1 sein können. - Anschließend setzen wir deren Bounds auf 0 oder 1
- Das Modell wird dann annahmegemäß gelöst, ein Lösungslauf wird angestoßen
- Abschließend fixieren (siehe
refix()) wir die Variablen wieder auf die neuen gefundenen Werte
class Unfixer(ABC):
def __init__(self) -> None:
self.variables_to_unfix = []
@abstractmethod
def unfix(self,model : MipModel):
"""
Entfernt die Fixierung von Variablen.
Welche Variablen konkret ausgewählt werden, hängt von der Implementierung ab.
Dies wird in select_variables_to_unfix implementiert
"""
self.variables_to_unfix = []
self.select_variables_to_unfix(model) # Auswahl
# Setzen der Bounds --> Veränderbar machen
for var in self.variables_to_unfix:
var.variable.SetBounds(0,1)
def select_variables_to_unfix(self, model : MipModel):
"""
Wählt die Variablen aus, die wieder zur Optimierung freigegeben werden sollen.
Welche Variablen konkret ausgewählt werden, hängt von der Implementierung ab.
"""
pass
def refix(self):
""" Fixiert die Variablen auf die Werte, die sie vor der Unfixierung hatten """
# Speichert erstmal die Variablenwerte der zuvoroptimierten Variablen
for stored_var in self.variables_to_unfix:
new_value = stored_var.variable.solution_value()
stored_var.value = new_value
# Fixiert die Variablen
for stored_var in self.variables_to_unfix:
prev_value = stored_var.value
stored_var.variable.SetBounds(prev_value,prev_value)Fix-and-Optimize Framework
Das Komplette Framework ist dann das folgende. Man übergibt einen Unfixer (den man sich überlegen muss), definiert ob minimiert oder maximiert werden soll und muss nurnoch solve() aufrufen.
class FixAndOptimize:
def __init__(self,model : MipModel, unfixer : Unfixer, minimize:bool, iterations=100) -> None:
self.model = model
self.unfixer = unfixer
self.iterations = iterations
self.minimize = minimize
def __is_better(self,val_a : float, val_b : float):
if self.minimize:
return val_a < val_b
return val_a > val_b
def solve(self):
""" Setzt voraus, dass eine initiale Lösung gegeben und fixiert ist."""
# Speichere Startzielfunktionswert als Besten
self.bestObjective = self.model.objective()
# Fix and Optimize für eine gegebene Anzahl Iterationen
for i in range(self.iterations):
# Erlaubt die Variablen gemäß Unfixer wieder zu optimieren
self.unfixer.unfix(self.model)
# Optimiert
self.model.solve()
# Updatet die beste bekannte Lösung, falls zutreffend
if self.__is_better(self.model.objective(), self.bestObjective):
self.bestObjective = self.model.objective()
# Fixiert die zuvor gelösten und reoptimierten Variablen erneut
self.unfixer.refix()Beispielimplementierung: Unfixer für SLULSP
Nachfolgend wollen wir rollierend immer lookahead aufeinanderfolgende Rüstperioden für den Solver optimierbar machen. Wenn wir über den Planungshorizont hinaus lappen, beginnen wir vorne.
Bei 5 Perioden und zwei Lookahead Perioden, optimieren wir also zunächst die Perioden 1 und 2, dann 2 und 3, 3 und 4, 4 und 5, 5 und 1, 1 und 2 usw.
Da SlulspUnfixer die abstrakte Klasse Unfixer implementiert, brauchen wir uns über update_fix_values und refix keine Sorgen machen. Diese sind direkt verfügbar.
Hier zeigt sich der Charme der Implementierung: Man muss nur Variablen gemäß irgendeiner Logik auswählen und in das Framework stecken. Der Rest läuft automatisch.
class SlulspUnfixer(Unfixer):
def __init__(self, lookahead : int) -> None:
super().__init__()
self.t_now = 0
self.lookahead = lookahead
def select_variables_to_unfix(self, model: Slulsp):
for pseudo_t in range(self.t_now,self.t_now+self.lookahead):
t = pseudo_t % len(model.y)
stor = VarValueStorage(model.y[t], model.y[t].lb())
self.variables_to_unfix.append(stor)
self.t_now = self.t_now + 1 % len(model.y)Kompletter Code und Beispiel
from ortools.linear_solver import pywraplp # OR Tools Solver Framework
from abc import ABC # Abstrakte Klassen
class MipModel(ABC):
def __init__(self,name="mip") -> None:
self.solver = pywraplp.Solver(name,pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)
def solve(self):
# Anstoßen des Lösungsvorgangs
self.solver.Solve()
def objective(self):
# Rückgabe des Zielfunktionswerts
return self.solver.Objective().Value()
# Speichert Variablenwerte zwischen
@dataclass
class VarValueStorage:
variable : object
value : float
class Unfixer(ABC):
def __init__(self) -> None:
self.variables_to_unfix = []
@abstractmethod
def unfix(self,model : MipModel):
"""
Entfernt die Fixierung von Variablen.
Welche Variablen konkret ausgewählt werden, hängt von der Implementierung ab.
Dies wird in select_variables_to_unfix implementiert
"""
self.variables_to_unfix = []
self.select_variables_to_unfix(model) # Auswahl
# Setzen der Bounds --> Veränderbar machen
for var in self.variables_to_unfix:
var.variable.SetBounds(0,1)
def select_variables_to_unfix(self, model : MipModel):
"""
Wählt die Variablen aus, die wieder zur Optimierung freigegeben werden sollen.
Welche Variablen konkret ausgewählt werden, hängt von der Implementierung ab.
"""
pass
def refix(self):
""" Fixiert die Variablen auf die Werte, die sie vor der Unfixierung hatten """
# Speichert erstmal die Variablenwerte der zuvoroptimierten Variablen
for stored_var in self.variables_to_unfix:
new_value = stored_var.variable.solution_value()
stored_var.value = new_value
# Fixiert die Variablen
for stored_var in self.variables_to_unfix:
prev_value = stored_var.value
stored_var.variable.SetBounds(prev_value,prev_value)
class FixAndOptimize:
def __init__(self,model : MipModel, unfixer : Unfixer, minimize:bool, iterations=100) -> None:
self.model = model
self.unfixer = unfixer
self.iterations = iterations
self.minimize = minimize
def __is_better(self,val_a : float, val_b : float):
if self.minimize:
return val_a < val_b
return val_a > val_b
def solve(self):
""" Setzt voraus, dass eine initiale Lösung gegeben und fixiert ist."""
# Speichere Startzielfunktionswert als Besten
self.bestObjective = self.model.objective()
# Fix and Optimize für eine gegebene Anzahl Iterationen
for i in range(self.iterations):
# Erlaubt die Variablen gemäß Unfixer wieder zu optimieren
self.unfixer.unfix(self.model)
# Optimiert
self.model.solve()
# Updatet die beste bekannte Lösung, falls zutreffend
if self.__is_better(self.model.objective(), self.bestObjective):
self.bestObjective = self.model.objective()
# Fixiert die zuvor gelösten und reoptimierten Variablen erneut
self.unfixer.refix()
## ===== Konkrete Klassen ==== #
class Slulsp(MipModel):
def __init__(self, d, s, l):
# Initialisiert die Init Funktion aus der abstrakten Klassen
super().__init__("SLULSP")
T = len(d) # Perioden
M = sum(d) # Big-M als Summe der Nachfragen
# Variablen: Lager (L), Menge (x), Rüsten (y)
self.L = [self.solver.NumVar(0, self.solver.infinity(), f"L{t}") for t in range(T)]
self.x = [self.solver.NumVar(0, self.solver.infinity(), f"x{t}") for t in range(T)]
self.y = [self.solver.BoolVar(f"y{t}") for t in range(T)]
# Nebenbedingungen
for t in range(T):
# Lagerbilanz: L[t-1] + x[t] - d[t] = L[t] (L[-1] ist 0)
prev_L = self.L[t-1] if t > 0 else 0
self.solver.Add(prev_L + self.x[t] - d[t] == self.L[t])
# Setup-Bedingung
self.solver.Add(self.x[t] <= M * self.y[t])
# Zielfunktion
self.solver.Minimize(self.solver.Sum(l * self.L[t] + s * self.y[t] for t in range(T)))
class SlulspUnfixer(Unfixer):
def __init__(self, lookahead : int) -> None:
super().__init__()
self.t_now = 0
self.lookahead = lookahead
def select_variables_to_unfix(self, model: Slulsp):
for pseudo_t in range(self.t_now,self.t_now+self.lookahead):
t = pseudo_t % len(model.y)
stor = VarValueStorage(model.y[t], model.y[t].lb())
self.variables_to_unfix.append(stor)
self.t_now = self.t_now + 1 % len(model.y)
# ==========================================================
# ==========MAIN============================================
# Nachfrage der Perioden
d = [50,30,20,10,5,50,10,30]
# Rüstkostensatz
s = 50
# Lagerkostensatz
l = 1
# Startlösung bei der in jeder Periode gerüstet wird
mip = Slulsp(d,s,l)
for v in mip.y:
v.SetBounds(1,1)
mip.solve()
# Unfixer mit zwei aufeinanderfolgenden Perioden
unfixer = SlulspUnfixer(lookahead=2)
f_and_o = FixAndOptimize(mip, unfixer,True)
f_and_o.solve()