Einführung Spatial Branch-and-Bound Verfahren zur Lösung nichtkonvexer MINLPs

Einführung Spatial Branch-and-Bound Verfahren zur Lösung nichtkonvexer MINLPs

Wir beschränken uns dabei auf Faktorisierbare Funktionen, welche sich mit Expression Trees ausdrücken lassen. Ein MINLP mit solchen Funktionen kann in ein äquivalentes Problem mit folgender Form umgewandelt werden:

$$\begin{array}{ll}{\min }_{x,y,z}& y_q\\ \text{ s.t. }& y_k={\vartheta }_k(x,y,z),k\in \{1,\dots ,q\}\\ & l_x\le x\le u_x\\ & l_y\le y\le u_y\\ & l_z\le z\le u_z\\ & (x,y,z)\in P\\ & x\in {\mathbb{R}}^n,y\in {\mathbb{R}}^q,z\in {\mathbb{Z}}^m\end{array}$$

mit $P\subseteq {\mathbb{R}}^{n+q+m}$ ein Polytop und $l_x,u_x\in {\mathbb{R}}^n,l_y,u_y\in {\mathbb{R}}^q,l_z,u_z\in {\mathbb{R}}^m$ und $\vartheta \in \mathcal{T}$ für alle $k\in \{1,...,q\}$.

Nun reicht es aus die einzelnen Faktoren der Funktion konkav zu überschätzen und konvex zu unterschätzen um alle Nichtkonvexitäten zu ersetzen. Dabei kann man zusätzlich entscheiden ob man Ganzzahligkeit relaxiert und ob man nur LP-Relaxierung oder auch NLP-Relaxierung zulässt. Je nach Wahl erhält man ein konvexes MINLP, konvexes NLP, MIP oder LP.

Die Überlegungen führen uns zum Spatial Branch-and-Bound Verfahren.