Mit Hilfe von Lower und Upper Bounds, die in der deutschsprachigen Literatur auch als untere und obere Schranken bezeichnet werden,1last sich der Wertebereich des (unbekannten) optimalen Zielwerts einer Probleminstanz einschranken. Dabei bestimmen Lower bzw. Upper Bounds Werte, die nicht groser bzw. nicht kleiner als der optimale Zielwert sind.2, 3 Bounds spielen aus mehreren Grunden, vor allem bei NP-schweren Problemstellungen, eine wichtige Rolle: Bounds werden als Ersatzgrose zur Beurteilung der Losungsqualitat von durch Heuristiken ermittelten Losungen eingesetzt, weil optimale Zielwerte von Instanzen NP- schwerer Probleme i. d. R. nicht bekannt sind.4 Dabei erfolgt die Beurteilung der Losungsqualitat anhand von Bounds sowohl fur einzelne Probleminstanzen als auch in bezug auf das allgemeine Losungsverhalten von Heuristiken. Hierzu wird bei Minimie- rungsproblemen meistens auf Lower Bounds zuruckgegriffen. Aber auch Upper Bounds lassen sich zur Beurteilung der Losungsqualitat einsetzen, beispielsweise beim direkten Vergleich der von unterschiedlichen Heuristiken ermittelten Zielwerte, da alle durch heuristische Losungsverfahren bestimmten Zielwerte gleichzeitig Upper Bounds darstellen.5 Innerhalb von Losungsverfahren werden mit Hilfe von Bounds die Konsequenzen bestimmter (Teil-) Zuordnungen in Hinblick auf die Losungsqualitat beurteilt. Vor allem bei exakten Losungsansatzen (z. B. bei Branch and Bound-Verfahren) werden Bounds zur Abschatzung der Losungsqualitat von Teilmengen des Losungsraums eingesetzt, weil die Berechnung aller einzelnen Zielwerte i. d. R. sehr aufwendig ist und im Laufe des Verfahrens entsprechende Berechnungen wiederholt durchzufuhren sind. Erst die durch den Einsatz von Bounds erzielte Reduktion des Zeitbedarfs ermoglicht haufig den Einsatz von exakten Losungsverfahren.6 Durch den Einsatz von Bounds last sich der Ablauf von Losungsverfahren steuern. So wird durch die Berechnung von Lower und Upper Bounds das Intervall vorgegeben, innerhalb dessen systematisch, beispielsweise anhand einer binaren Suche, nach einem (optimalen) Zielwert zu suchen ist.7 Zudem konnen Lower Bounds auch bei Abbruchkriterien einzelner Losungsverfahren eingesetzt werden.8 Fur den Einsatz der Bounds ist es erforderlich, das sie die optimalen Zielwerte moglichst gut und effizient abschatzen. Bei zu grosen Abweichungen sind kaum Ruckschlusse auf die optimalen Zielwerte moglich, wodurch die Losungsqualitat der Verfahren falsch eingeschatzt werden kann bzw. sich der Ablauf von ubergeordneten Verfahren nicht gezielt verbessern last. Dabei darf die Berechnung der Bounds nicht selbst einen hohen Rechenaufwand, beispielsweise durch das Losen von Instanzen NP-schwerer Problemstellungen, erfordern.9