Graphenzerlegungs-Problem (graph partition problem)
| \(\large (\text{GPP})~~\left\{~~ \begin{align*} & \text{Min.} && \sum_{\{h, i\}\in E}c_{hi}\cdot z_{hi}\\ & \text{u. d. N.} && \sum_{p=1}^s y_{ip} = 1 && (i\in V)\\ & && \sum_{i\in V} y_{ip} \le m' && (p=1, \ldots, s)\\ & && z_{hi} \ge y_{hp}-y_{ip} && (\{h, i\}\in E;~p=1, \ldots, s)\\ & && y_{ip}\in\{0, 1\} && (i\in V;~p=1, \ldots, s)\\ & && z_{hi}\in\{0, 1\} && (\{h, i\}\in E) \end{align*}\right. \) |
| \(c_{hi}\) | Gewicht der Kante \(\{h, i\}\) | |
| \(E\) | Menge der Kanten \(\{h, i\}\) des Graphen | |
| \(m'\) | Maximale Anzahl an Knoten pro Teilmenge \(V_p\) | |
| \(s\) | Vorgegebene Anzahl der Teilmengen in Zerlegung \(\{V_1, \ldots, V_s\}\) der Knotenmenge \(V\) | |
| \(V\) | Menge der Knoten \(i\) des Graphen | |
| \(\ast\) | \(y_{ip}\) | \(=1\), falls Knoten \(i\) der Teilmenge \(V_p\) zugewiesen wird, \(=0\), sonst |
| \(\ast\) | \(z_{hi}\) | \(=1\), falls die Endknoten der Kante \(\{h, i\}\) verschiedenen Teilmengen \(V_p, V_q\) zugewiesen werden, \(=0\), sonst |