Konstruktion symmetrischer Designs

In dieser Arbeit werden zehn neue symmetrische (176,50,14) Designs und ein neues symmetrisches (144,66,30) Design durch Vorgabe von nichtauflösbaren Automorphismengruppen konstruiert. Im Jahre 1969 entdeckte G. Higman ein symmetrisches (176,50,14) Design, dessen volle Automorphismengruppe die sporadische einfache Gruppe HS der Ordnung 44.352.000 ist. Hier wurden nun Designs gesucht, die eine Untergruppe von HS zulassen. Folgende Untergruppen wurden betrachtet: die transitive und die intransitive Erweiterung einer elementarabelschen Gruppe der Ordnung 16 durch Alt(5), AGL(3,2), das direkte Produkt einer zyklischen Gruppe der Ordnung 5 mit Alt(5) und PSL(2,11). Die transitive Erweiterung von E(16) durch Alt(5) lieferte zwei neue Designs mit Automorphismengruppen der Ordnungen 960 bzw. 11.520; letzteres konnte auch mit der transitiven Erweiterung erhalten werden. Die Gruppe PSL(2,11) operiert auf den Punkten des Higman-Designs in drei Bahnen; sucht man nach symmetrischen (176,50,14) Designs, auf denen diese Gruppe in zwei Bahnen operiert, so erhält man acht neue Designs. Die übrigen Gruppen lieferten keine neuen Designs. Schließlich konnte ein neues symmetrisches (144,66,30) Design unter Verwendung der sporadischen Mathieu-Gruppe M(12) konstruiert werden. Dies war zu diesem Zeitpunkt außer dem Higman-Design das einzige bekannte symmetrische Design, dessen volle Automorphismengruppe im Wesentlichen eine sporadische einfache Gruppe ist.

Contributions to exact approaches in combinatorial optimization

The focus of this thesis is to contribute to the development of new, exact solution approaches to different combinatorial optimization problems. In particular, we derive dedicated algorithms for a special class of Traveling Tournament Problems (TTPs), the Dial-A-Ride Problem (DARP), and the Vehicle Routing Problem with Time Windows and Temporal Synchronized Pickup and Delivery (VRPTWTSPD). Furthermore, we extend the concept of using dual-optimal inequalities for stabilized Column Generation (CG) and detail its application to improved CG algorithms for the cutting stock problem, the bin packing problem, the vertex coloring problem, and the bin packing problem with conflicts. In all approaches, we make use of some knowledge about the structure of the problem at hand to individualize and enhance existing algorithms. Specifically, we utilize knowledge about the input data (TTP), problem-specific constraints (DARP and VRPTWTSPD), and the dual solution space (stabilized CG). Extensive computational results proving the usefulness of the proposed methods are reported.