Gemischt-ganzzahliges nichtlineares Optimierungsproblem

Im Vergleich zu MIPs kann bei MINLPs die Zielfunktion und die Nebenbedingungen auch nicht linear sein.

Beispiel: Pooling-Problem

Allgemeine Form

min⁡x,zf(x,z) s.t. ci(x,z)≤0,i∈I(x,z)∈Pl≤z≤ux∈Rn,z∈Zm\begin{array}{cl} \min _{x, z} & f(x, z) \\ \text { s.t. } & c_{i}(x, z) \leq 0, \quad i \in \mathcal{I} \\ & (x, z) \in P \\ & l \leq z \leq u \\ & x \in \mathbb{R}^{n}, z \in \mathbb{Z}^{m} \end{array}
  • ff ist möglicherweise nichtlinear
  • I\mathcal{I} ist eine endliche Indexmenge
  • cic_i möglicherweise nichtlinear
  • PP ist Polytop
  • l,ul,u mit l≤ul\le u → also alle ganzzahligen Variablen sind nach oben und unten beschränkt

Konvexität

Man unterscheidet zwischen konvexen und nicht konvexen MINLPs wobei hierbei zu beachten ist, dass damit nur gemeint ist, dass das Problem ohne Ganzzahligkeitsbedinung konvex ist. Das ist der Fall, wenn die Funktionen ff und cic_i konvex sind.

Die Zielfunktion und Nebenbedingungen können durch Konvexe Relaxierung konvexifiziert werden.

Schnittebenenverfahren

Kann das Schnittebenenverfahren auf MINLPs angewendet werden?

Ja, aber nur wenn die Zielfunktion linear ist. Eine nichtlineare Zielfunktion lässt sich aber wie folgt umformulieren:

min⁡x,z,ηη s.t. η≥f(x,z),ci(x,z)≤0,(x,z)∈Pl≤z≤ux∈Rn,z∈Zm,η∈R.\begin{array}{ll} \min _{x, z, \eta} & \eta \\ \text { s.t. } & \eta \geq f(x, z), \\ & c_{i}(x, z) \leq 0, \\ & (x, z) \in P \\ & l \leq z \leq u \\ & x \in \mathbb{R}^{n}, z \in \mathbb{Z}^{m}, \eta \in \mathbb{R} . \end{array}