Im Sinne der Komplexitätstheorie gehören nichtlineare gemischt-ganzzahlige Programme zu den schwersten Problemen der Optimierung: Sie sind mindestens so schwer wie die rein ganzzahligen bzw. kontinuierlichen Varianten, außerdem ist es nicht ohne weiteres möglich, gegebene Verfahren der ganzzahligen mit Verfahren der kontinuierlichen Optimierung zu kombinieren.

So ist es naheliegend, zunächst einige klassische Komplexitätsresultate (im ganzzahligen sowie kontinuierlichen Fall) zu studieren: Ein Theorem von Matiyasevich besagt beispielsweise, dass allgemeine nichtlineare ganzzahlige Probleme unlösbar sind - sogar wenn wir uns auf das Minimieren eines Polynomes in 10 ganzzahligen Variablen beschränken.

Im Anschluss betrachten wir Verfahren, die geeignete Subklassen gemischt-ganzzahliger nichtlinearer Probleme "lösen" können. Allerdings liefern die Algorithmen häufig keine exakten Lösungen, sondern Approximationen. Dazu stellen wir einige übliche Approximationsbegriffe vor.