Integrating Concepts fromConstraint Programming andOperations Research AlgorithmsDissertationvonTorsten FahleSchriftliche Arbeit zur Erlangung des Gradeseines Doktors der NaturwissenschaftenFakultät für Elektrotechnik, Informatik und Mathematikder Universität Paderborn.Paderborn, Dezember 2002When you have eliminated the impossible,whatever remains, however improbable, must be the truth.Sir Arthur Conan Doyle (1859–1930)Sherlock Holmes to Dr. Watsonin The Sign of Four [68].But we all know the world is nonlinear.Harold Hotelling, (1910–1975)to George Dantzig, 1947 [59].1Jede Lösung eines Problems ist ein neues Problem.Johann Wolfgang von Goethe (1749–1832)to chancellor von Müller, 1821 [95].1Every solution of a problem is a new problem. (non-authorized translation)iiiivAcknowledgmentResearch is seldom a one-person project and many individuals have contributed to the resultspresented in this thesis. The first to mention here is my supervisor Prof. Dr. Burkhard Monienfor his support during the last few years and for providing an excellent working environmentin his group.2I am very indebted to my colleagues in the research group and in the PC for provid-ing a good working atmosphere. I would especially like to thank Rainer Feldmann, SilviaGötz, Sven Grothklags, Georg Kliewer, Jürgen Schulze, Norbert Sensen, Ulf-Peter Schroederand Meinolf Sellmann for interesting discussions on optimization topics.