$Title Graphen-Zerlegung
$Ontext

Vorlesung: Modellierung und Planung von Logistiksystemen
Abschnitt: 3.3 Konfigurationsplanung bei Zentrenfertigung
Problemstellung: Zerlegung eines Graphen in vorgegebene Anzahl an Teilgraphen so, dass Summe der Kantengewichte zwischen Teilgraphen minimal

 - Model -

Author: Christoph Schwindt
Date: 15/12/2019

$Offtext

$eolcom//

$include graph-partition_data.gms

variables
   gewicht  Gesamtgewicht der Kanten zwischen Teilgraphen (Zielfunktion)
   y(i,p)   gleich 1 falls Knoten i Teilgraphen p zugewiesen wird
   z(h,i)   gleich 1 falls die Endknoten der Kante hi verschiedenen Teilmengen p und q zugewiesen werden ;

binary variables y, z ;

equations
   def_gewicht          Definition des Gesamtgewichts
   knoten_teilgraph(i)  Zuweisung des Knotens i zu einem Teilgraphen
   anz_knoten_max(p)    Beschraenkung der Knotenzahl des Teilgraphen p
   kopplung(h,i,p)      Kopplung der y- und z-Variablen ;

   def_gewicht..             gewicht =e= sum((h,i)$c(h,i), c(h,i)*z(h,i)) ;
   knoten_teilgraph(i)..     sum(p, y(i,p)) =e= 1 ;
   anz_knoten_max(p)..       sum(i, y(i,p)) =l= mPrime ;
   kopplung(h,i,p)$c(h,i)..  z(h,i) =g= y(h,p)-y(i,p) ;

model graph_partiton / all / ;

options mip = cplex
        optcr = 0
        reslim = 60 ;

solve graph_partiton minimzing gewicht using mip ;

display gewicht.l, y.l, z.l ;