Komplexität von MINLPs
Diophantische Gleichung → MINLPs sind unentscheidbar
Haben alle ganzzahligen Variablen endliche Schranken, dann gilt MINLP in NPC. Da MINLP als zulässige Menge ein Polytop hat ist MINLP in NPC.
Trotzdem ist MINLP oft sehr schwer zu lösen weswegen häufig Heuristiken und Relaxierungen angewandt werden um sie zu lösen.
Für MINLPs gibt es eine besondere Form der Relaxierung, die NLP-Relaxierung. Mit der NLP-Relaxierung lässt sich auch das Branch-and-Bound Verfahren analog auf MINLPs übertragen.
Die zulässige Menge der NLP-Relaxierung eines konvexen MINLP ist konvex und kompakt.