Standardisierungsproblem
Standardisierungsproblem

== Komplexität des Standardisierungsproblems ==
Bei dem Standardisierungsproblem handelt es sich um ein Kombinatorisches Optimierungsproblem, bei dem sich die Komplexität im Trade-off zwischen den knotenbezogenen Standardisierungskosten und den kantenbezogenen Informationskosten begründet. Das Problem lässt sich mit Hilfe der linearen ganzzahligen Programmierung lösen. Dieses Lösungsverfahren wird insbesondere bei Erweiterungen des Standardisierungsproblems problematisch, da dann die Rechenzeiten stark ansteigen. Bei einer Erweiterung des Standardisierungsproblems um die Auswahl zwischen  alternativen Standards und  Perioden existieren bereits  Lösungsmöglichkeiten, während das dargestellte einfache Standardisierungsproblem lediglich zu einer Komplexität von  Handlungsalternativen führt.
Aufgrund dieser Komplexität haben sich Wissenschaftler aus dem Gebiet des Operations Research mit dem Standardisierungsproblem beschäftigt und alternative Verfahren zur Ermittlung von Lösungen entwickelt. Kimms konzipiert einen Minimum-Cut-Ansatz, der dem ursprünglich entwickelten Branch-and-Bound-Verfahren in Bezug auf die Rechenzeit deutlich überlegen ist. Domschke/Wagner entwickeln weitere Lösungsverfahren und zeigen dabei, dass Probleme mit einem oder zwei Standards noch mit polynomialem Aufwand zu lösen sind. Probleme mit drei oder mehr Standards sind jedoch np-schwer.