Abstract: In diesem Vortrag geht es um die Lösung allgemeiner gemischt- ganzzahliger linearer Programme, d.h. um das Problem, eine bzgl. einer linearer Zielfunktion gemischt-ganzzahlige optimale Lösung unter linearen Nebenbedingungen zu finden.
Die derzeit wohl erfolgreichste Methode zur Lösung gemischt- ganzzahliger Programme sind LP-basierte Branch-and-Bound Verfahren, wobei die Ausgangsformulierung möglicherweise durch Schnittebenen verschärft wird. Sowohl die wichtigsten kommerziellen als auch wissenschaftlichen Softwarepakete verwenden diese Methode.
Ausgehend von zwei praktischen Anwendungen aus der Telekommunikation und dem VLSI-Design werden wir die wesentlichen Komponenten dieser Methode vorstellen. Wir werden dabei auch auf verschiedene "Kniffe" und "Tricks" bei der Implementierung hinweisen und aufzeigen, wo die derzeitigen Grenzen dieser allgemeinen Verfahren liegen.
Abstract: The Penrose polynomial of a plane graph is strongly related to the 4-Color Theorem. There is also a strong relationship between the Penrose polynomial and the Tutte polynomial. The Penrose polynomial is related to links in R3. We present an interpretation of the valuation of the Penrose polynomial of a plane graph on negative values of its indeterminate. We construct a Hopf algebra A of graphs and a Hopf algebra map P from A to a Hopf algebra of polynomials in one indeterminate. When G is a plane graph P(G) coincides with the Penrose polynomial of G.