Technik zur Zurückführung eines Optimierungsproblems auf mehrere kleinere Teilprobleme, sofern dies die spezielle Struktur des Ausgangsproblems zuläßt.

Wichtiges Beispiel einer derartigen Strukur stellen Probleme dar, bei denen die Zielfunktion und Nebenbedingungen additiv zerlegt werden können; man betrachte eine Zielfunktion \begin{eqnarray}f(\mathop{x}\limits_{\_}):=f({\mathop{x}\limits_{\_}}_{1},\ldots, {\mathop{x}\limits_{\_}}_{s});=\displaystyle \sum _{i=1}^{s}{f}_{i}({\mathop{x}\limits_{\_}}_{i})\end{eqnarray} unter Nebenbedingungen \(\displaystyle {\sum }_{i=1}^{s}{g}_{ij}({\mathop{x}\limits_{\_}}_{i})\ge 0,1\le j\le m\); \({h}_{i}({\mathop{x}\limits_{\_}}_{i})\ge 0,1,\le i\le s.\)

Hierbei sind die \({\mathop{x}\limits_{\_}}_{i}\) Variablenblöcke gewisser Dimensionen n_i und die f_i, g_ij sowie h_i Funktionen von ℝⁿi nach ℝ.

Bei der sogenannten Ressourcenzerlegung unterteilt man jede der m Nebenbedingungen \({\sum }_{i=1}^{s}{g}_{ij}({\mathop{x}\limits_{\_}}_{i})\ge 0\), \(1\le j\le m\), in s weitere Nebenbedingungen g_ij ≥ b_ij, 1 ≤ i ≤ s, wobei zusätzlich \({\sum }_{i=1}^{s}{b}_{ij}=0\) verlangt wird.

Für jeden Variablenblock \({\mathop{x}\limits_{\_}}_{i}\) erhält man somit eine eigene zulässige Menge \begin{eqnarray}{M}_{i}:=\{{\mathop{x}\limits_{\_}}_{i}|{g}_{ij}({\mathop{x}\limits_{\_}}_{i})|\ge {b}_{ij},1\le j\le m,{h}_{}({\mathop{x}\limits_{\_}}_{i})\ge 0\}\end{eqnarray} sowie eine Funktion \begin{eqnarray}{\psi }_{i}({b}_{i1},\ldots, {b}_{im});=\inf \{f({\mathop{x}\limits_{\_}}_{i}),{\mathop{x}\limits_{\_}}_{i}\in {M}_{i}\}{\mathop{x}\limits_{\_}}_{i}\end{eqnarray}

(und ψ_i(b_i1, …, b_im) := ∞ falls M_i = ∅).

Schließlich optimiert man die Summe \({\sum }_{i=1}^{s}\psi ({b}_{i1},\ldots, {b}_{im})\) unter den m Nebenbedingungen \({\sum }_{i=1}^{s}{b}_{ij}=0,1\le j\le m.\). Letzteres führt i.allg. auf ein nichtglattes Optimierungsproblem. Bei der Anwendung von Iterationsmethoden sind dann in jedem Schritt die Teilprobleme der Form inf{\(\{{f}_{i}({\mathop{x}\limits_{\_}}_{i}),{\mathop{x}\limits_{\_}}_{i}\in {M}_{i}\}\)} zu lösen.

Die Ressourcenzerlegung wird auch als ein primales Dekompositionsverfahren bezeichnet. Analog gibt es duale Dekompositionsverfahren; bei diesen werden alle f_i und die (gewichteten) g_ij in einer Funktion \begin{eqnarray}\displaystyle \sum _{i-1}^{s}({f}_{i}({\mathop{x}\limits_{\_}}_{i})+\displaystyle \sum _{j=1}^{m}{\lambda }_{j}.{g}_{ij}({\mathop{x}\limits_{\_}}_{i}))\end{eqnarray} zusammengefaßt, die dann weiter untersucht wird.

Eine andere zur Anwendung von Dekompositionstechniken geeignete Struktur liegt vor, wenn es lediglich einen Variablenblock \(\mathop{y}\limits_{\_}}\) gibt, der mit den anderen Blöcken \({\mathop{x}\limits_{\_}}_{i}\) in den Nebenbedingungen gekoppelt ist. Es handelt sich dann um ein Problem der Gestalt: Minimiere \begin{eqnarray}\displaystyle \sum _{i-1}^{s}({f}_{i}({\mathop{x}\limits_{\_}}_{i})+{f}_{s}+1(\mathop{y}\limits_{\_}))\end{eqnarray} unter Nebenbedingungen \({g}_{i}({\mathop{x}\limits_{\_}}_{i},\mathop{y}\limits_{\_})\ge 0,1\le i\le s\).

Ausgangspunkt von Lösungstechniken (darunter u. a. das Verfahren von Benders) ist die Idee, bei festem Wert von \(\mathop{y}\limits_{\_}\) unabhängige Teilprobleme in den \({\mathop{x}\limits_{\_}}_{i}\) zu erhalten. Erforderlich ist daran anschließend die Analyse des Zusammenhangs zwischen den erhaltenen Lösungen und dem Ausgangsproblem.