Die Verwendung von Constraints eröffnet neuartige Möglichkeiten für die Repräsentation kombinatorischer Optimierungsprobleme und ihre Lösung. Dabei besteht die Idee darin, die alle Variablen des kombinatorischen Problems betreffende Zielfunktion durch Constraints zu repräsentieren, die jeweils nur Belegungen eines Teils der Variablen bewerten. Mit dem Auftreten von Constraints in Problemrepräsentationen ist die Verwendung spezieller Verfahren aus einer Constraintbibliothek in Suchalgorithmen verbunden, so dass die verwendeten Suchalgorithmen anhand der Problemrepräsentation an die aktuelle Problemstellung angepasst werden. Diese Arbeit fußt auf der Entwicklung einer Constraintbibliothek für ein kommerziell eingesetztes System zur Personaleinsatzplanung. So genannte weiche Constraints repräsentieren scharfe oder unscharfe Bedingungen, Kostenmaße, Konfidenzen und Kosten. Sie werden mithilfe einer Bibliothek vordefinierter Bausteine spezifiziert, um dann flexibel zu komplexen Zielfunktionen kombiniert werden zu können. Die Problemlösung kann dann durch allgemein anwendbare Suchverfahren erfolgen. Zur Unterstützung dieser Suche führt diese Arbeit eine neuartige Form der Propagierung weicher Constraints ein. Des Weiteren wird eine Abstraktion des Constraint-Problems zur Herleitung von Kontrollstrategien verwendet.