Herzlich willkommen. Mein Name ist Alexander Martin und Nicole Nowak, die wir beide werden die Vorlesung, das geht die Optimierung betreuen. Ich möchte vielleicht erst mal kurz mich selber vorstellen. Ich habe vor 25 Jahren, glaube ich, Größenordnung selber Mathematik studiert,

Wirtschaftsmathematik genauer gesagt, weil mir die Kombinationsspaß gemacht hat, Informatik, Wirtschaftswissenschaft und Mathematik in Kombination. Das in Augsburg damals. Ich habe dann angefangen zu promovieren. In der Zeit

hat mein Doktorvater, als ich promoviert habe, mittendrin gesagt, er geht jetzt nach Berlin. Gut ist mir nichts anderes übrig geblieben, als auch als Bayer mit nach Berlin zu gehen sozusagen, aber ich habe das nicht bereut. Ich war dann acht Jahre in Berlin, habe dort promoviert, habilitiert, bis mich dann der Ruf hierher nach Darmstadt ereilt hat.

Das war dann 2000, also ich bin jetzt etwas mehr als acht Jahre an dieser Universität. Mein Steckenpferd in der Mathematik ist genau die diskrete Optimierung, also genau das, was wir uns jetzt in dieser Vorlesung die Grundlagen anschauen wollen. Was genau diskrete Optimierung ist und was wir so alles machen, das werde ich vielleicht dann gleich noch ein bisschen erzählen.

Bevor wir das tun, wollen wir erst noch ein paar organisatorische Dinge klären. Ich fange mal einfach mit dem Englischsprachigen an. Es vergab das Anliegen sozusagen, dass ich die Vorlesung auf Englisch halte.

Weiß ich nicht, ob das jetzt wirklich von allen gewollt ist. Unser Vorschlag wäre eigentlich eher ein Kompromiss, weil insbesondere das Skript, da werde ich dann auch gleich noch etwas zu sagen. Und Sie sehen auch gerade, dass hier wird aufgezeichnet sogar die Vorlesung. Wäre es uns eigentlich lieber, das in Deutsch zu behalten. Allerdings, dass wir eine englischsprachige Übung anbieten, dass diejenigen, die sozusagen das Englische praktizieren möchten,

ist dann sowieso, denke ich, in der aktiven Rolle deutlich besser als nur in der passiven. Für diejenigen, die mich gefragt haben, sind im Moment auch noch gar nicht da, glaube ich. Von daher hat es sich vielleicht auch schon wieder erledigt.

Also es ist eine Handvoll. Also je nachdem, wie gesagt, die Personen, die mich gefragt haben, sind noch gar nicht da. Vielleicht haben sie sich das auch wieder anders überlegt. Ich habe gesagt, wir klären das in der ersten Vorlesung. Und wenn dann sich eine Mehrheit dafür findet, dann bieten wir sicherlich wenigstens die eine Übung Englischsprache an.

Wenn jetzt alle hier geschrieben hätten, alles auf Englisch, auch die Vorlesung zu machen, hätten wir auch das tun können. Aber ich glaube, so wie die Begeisterung hier ist, scheint es nicht ganz so der Fall zu sein. Deswegen Vorschlag erst mal, wir machen die eine, wir machen Vorlesung Deutsch.

Wir haben drei oder vier Übungen und die vierte dann auf Englisch. Sollte sich jetzt wirklich niemand richtig dafür begeistern, von uns kann ja jeder Deutsch mindestens so gut wie Englisch, dann switchen wir einfach wieder auf Deutsch.

Dann von was die Übungen selber betrifft, Nicole Nowak gleich noch was dazu sagen, vielleicht zur Vorlesung selber noch. Es gibt ein Skript, es gibt sogar ein Stück weit mehr als ein Skript. Es gibt so ein halbfertiges Buch, weil ich wurde vor Jahren schon mal darauf angesprochen, ob ich nicht aus

den Vorlesungen, die ich gehalten habe, die Einführung in die Optimierung, die hat damals noch ein bisschen anders ausgesehen. Da werde ich gleich noch mal drauf kommen. Und diese Vorlesung nicht ein Buch machen möchte. Ich wollte das nie tun, aber Springer Verlag hat gemeint, das ist ein vernünftiges Konzept, was ich hier versuche, Ihnen beizubringen. Da könnte man ein Buch draus machen. Ich hatte das denen vor drei oder vier Jahren versprochen zu tun und habe dann auch daran gearbeitet.

Dann bin ich Dekan geworden. Ich habe gesagt, wenn ich Dekan zu Ende bin, dann schreibe ich das Buch fertig. Dann bin ich jetzt leider Vizepräsident geworden und die Aufgaben werden immer mehr. Und ich habe jetzt versprochen, nachdem ich Vizepräsident zu Ende bin, dann habe ich ein Forschungssemester und dann schreibe ich das Buch zu Ende.

Auf der anderen Seite ist natürlich jetzt eine sehr gute Gelegenheit, dieses Buch noch mal gemeinsam durchzuarbeiten. Und da möchte ich Sie einfach bitten, laden Sie sich das Buch, wenn es geht, runter oder immer nur Teile,

weil wir sind ständig am Aktualisieren und Benjamin Asaf ist hier, der sich bereit erklärt hat, auch immer sozusagen das, was ich an Nebenbemerkungen mache oder an Skizzen dann auch immer gleich mit einzustellen in das Skript, sodass es durchaus Sinn macht, sich immer nur Teile runterzuladen. Also es hat eben zwischen 330 Seiten schon das Buch, also das jedes Mal runterzuladen auszudrücken,

ist vielleicht weniger sinnvoll, insbesondere weil sich vieles daran tut. Aber mir wäre es natürlich recht, wenn Sie wirklich auch nach diesem Buch ein Stück weit arbeiten, weil sozusagen je mehr das Lesen, je mehr das Kontrollelesen, umso besser wird es natürlich am Ende. Ich werde auch immer wieder die Hinweise machen, wo wir gerade aus dem Buch was machen.

Also wir werden es nicht genau eins zu eins machen, weil die Einführung ein bisschen anders ausgesehen hat, als es in dem Buch dargelegt ist. Da ist der gesamte nicht lineare Optimierung, spielt da keine Rolle. Das Buch soll diskrete Optimierung heißen. Und deshalb haben wir da die Schwerpunkte leicht verschoben. Das heißt, wir müssen hier noch ein bisschen was nachholen, was in dem Buch sozusagen weiter vorne im Kapitel ist.

Aber an sich, die Inhalte sind alle da. Sie werden auch auf der Internetseite dann das ursprüngliche Skript finden, was ich zuletzt 2006 gelesen habe, was mehr oder weniger dem Verlauf entspricht, so wie wir es uns in der Vorlesung anschauen wollen.

Also fühlen Sie sich frei, beide anzugucken, was Anmerkungen, Verbesserungen, Rechtschreibfehler, inhaltliche Fehler betrifft. Wäre es mir ganz lieb, wenn Sie sich an dem Buch orientieren, weil das ist das, was weiter aktualisiert wird, und das ist das, was auch ständig verbessert werden soll. Und dann haben wir ein Thema, weiß ich nicht, wer von Ihnen noch im Diplom wer im Masterbereich ist,

weil je nachdem, wie wir unterschiedliche Dinge anbieten. Deswegen erstmal vielleicht die Frage, wer ist im Master oder im Master sind? Eine Handvoll Bachelor, ist auch jemand noch ein Bachelor?

Also das heißt, Sie brauchen ja wahrscheinlich am Ende eine Prüfung zu dieser Vorlesung, aber solange es eine Handvoll ist, ist mein Vorschlag, die machen wir mündlich. Die meisten nicken eher positiv, also ich denke auch mündlich ist die angenehmere Prüfung. Vermutlich dann, wenn es jetzt über 20, 30 gewesen wären, dann hätten wir überlegt, die schriftlich zu machen.

Also dann würde ich sagen, wenn es nicht signifikant mehr wäre, oder sich das noch überlegen, so eine Prüfung zu wollen, dann machen wir die mündlich, und mündlich heißt halt dann, wann immer Sie Lust dazu haben sozusagen,

müssen wir halt nur rechtzeitig einen Termin ausmachen. Gut, zur Organisation von Übungen übergebe ich vielleicht einfach mal an Nicole, dass sie ein paar Worte dazu sagt.

Nein, ist es nicht.

Voraussetzung ist es, wenn Sie in der Optimierung Master oder Diplomarbeit schreiben wollen, weil wir relativ viele Anfragen haben, was Diplomarbeiten betrifft, und dann sagen wir, das Minimum ist, dass Sie wenigstens eine dieser drei Hauptvorlesungen, Optimierung 1 bis 3, erfolgreich mitgemacht haben,

und das messen wir sozusagen an einer erfolgreichen Beteiligung an den Übungen.

Gut, eine Anmerkung, vielleicht haben Sie ja gesehen, hier laufen zwei Kameras,

also die Vorlesung wird auch aufgezeichnet und auch online gestellt. Also wenn Sie dann Interesse haben oder dann mal nicht da sein können, können Sie sich die auch jederzeit noch im Internet runterladen. Es wird aber allerdings, habe ich verstanden, Größenordnung ein, zwei Wochen dauern, bis sozusagen der aktuelle Mitschnitt sozusagen dann im Internet zur Verfügung steht.

Es ist auch ein Stück weit Experiment, weil die Mathematiker machen ja gerne Tafelvorträge und das scheint eine Herausforderung zu sein für Videoaufzeichnungen, den Tafelmitschrift sozusagen einigermaßen vernünftig wiedergeben zu können.

Deswegen bedarf das noch einer gewissen Nachbearbeitung. Sonst, wenn es im klassischen Sinne, wenn es mit Powerpoint Vorträgen in der Vorlesung oder so, kennen Sie vielleicht aus der Informatik oder so, dann wäre das Ganze ein Stück weit einfacher. Also wir versuchen mal, die Tafel zu digitalisieren, sodass die Mathematiker auch in diese Online-Welt sozusagen Einlass bekommen. Und deswegen ist es ein Stück weit Versuch.

Ich habe dieses Ding, merken Sie, das Mikro funktioniert nur für die Kameras, damit Sie auch trotzdem nebenbei noch reden können und trotzdem meine Stimme auf dem Tape dann am Ende drauf ist. Gut, ansonsten habe ich von meiner Seite erstmal organisatorisch nichts mehr.

Haben Sie noch Fragen, Anmerkungen, bevor wir ins Inhaltliche einsteigen? Gut, wenn dem nicht so ist, dann würde ich einfach gerne erstmal ein bisschen anfangen, was Discrete optimieren. Wir fangen vielleicht auch gleich dann mit ein paar Beispielen an.

Aus meiner Wahrnehmung, wie gesagt, das ist mein Steckenquart. Von daher erzähle ich natürlich auch mal ein Stück weit mit einer gewissen Begeisterung davon. Aber ich glaube, die Begeisterung hat vielseitige Ursachen. Wenn Sie mal schauen, was Sie in der Einführung bislang gehört haben, in der ersten Vorlesung, so haben Sie sich im Großteil mit linearer Optimierung beschäftigt.

Das heißt, Sie haben ein System von linearen Nebenbedingungen, Ungleichungssystem. Sie haben eine lineare Zielfunktion und Sie möchten jetzt über diesen linearen Ungleichung sozusagen eine Optimallösung bestimmen, wobei alle Variablen kontinuierlich sein dürfen.

Was wir jetzt fordern wollen, ist, dass einige oder alle dieser Variablen Ganzzahligkeitsanforderungen haben. Also wir ersetzen x aus r hoch n durch x aus z hoch n. Jetzt mag man erst mal überlegen, denken, das ist ja einfacher, weil ich habe ja viel weniger Möglichkeiten.

x aus r hoch n sind potenziell viel mehr Lösungen als x aus z hoch n. Dem ist aber nicht so. Das Problem, auch im Sinne der Komplexitätstheorie, wird damit ein schweres Problem. Wir werden noch genau identifizieren, was das heißt. Also in dem sind polynomiale Algorithmen, so wie lineare Programme ja sind

und wie Sie auch in der Vorlesung kennengelernt haben in der Ellipsidmethode, gibt es für ganzzahlige Programme nicht. Das heißt, wir müssen uns was überlegen, was wir anstatt dessen tun können, um solche Probleme überhaupt lösen zu können. Jetzt kann man sich natürlich fragen, warum machen wir das überhaupt? Ist das überhaupt sinnvoll, sozusagen diese zusätzliche Forderung x aus z hoch n?

Und ja, die ist es, weil man kann damit wahnsinnig viele Probleme aus der Realität modellieren. Sobald Sie x aus z hoch n haben, können Sie Entscheidungen modellieren. Ja, nein, Entscheidungen. Sie fordern, treffe ich die Entscheidung, setzten Sie eine Variable auf 1, treffen Sie sie nicht, setzten Sie sie auf 0.

Damit haben Sie eine Variable aus 0,1 sogar. Das ist der häufige Fall, der in der Anwendung vorkommt. Das heißt, Sie müssen letztendlich diskrete oder ganzteilige Optimierungsprobleme sind. So kann man es auch ein Stück weit sehen. Die meisten davon sind entscheidungsbasierte Optimierungsprobleme. Sie müssen Entscheidungen treffen unter Randbedingungen.

Und wenn Sie mal überlegen, wie oft das in der Realität vorkommt, in der Praxis, selbst im täglichen Leben treffen Sie ständig Entscheidungen unter irgendwelchen Randbedingungen und haben im Kopf, sagen wir auch, irgendein Zielfunktional, was Sie erreichen wollen, in kürzester Zeit Ihr Studium zum Beispiel zu beenden. Und da treffen Sie Entscheidungen, die oder die Vorlesung oder wie auch immer. Oder auch selbst im täglichen Leben, wann stehe ich auf, wann mache ich was usw.

Also ständig treffen Sie solche Entscheidungen. Und interessanterweise ist auch, dass viele diese Bedingungen, die aus der Realität kommen, sich als lineare Randbedingungen formulieren lassen. Man kann jetzt darüber philosophieren, warum dem so ist. Häufig ist es einfach so, dass der Mensch an sich, ich nenne es immer sehr einfach,

gerne linear denkt. Also sozusagen jemandem als Beispiel beizubringen, wie stark eine Exponentialfunktion wächst, ist er für viele gar nicht so richtig begreifbar. Wenn Sie mal schauen, kennen Sie sicherlich das Beispiel mit dem Schachfeld, wo man auf das erste Feld ein Reißkorn legt, auf das zweite zwei, auf das dritte vier

und immer verdoppelt, wie viele Reißkörner man dann am Ende hat. Und dann kommt irgendwie sowas raus, 100 Quadratkilometer Fläche, 100 Meter Höhe. Das ist so eine Zahl, die kann man irgendwie nicht fassbar machen, so hoch 64. Klingt jetzt gar nicht so allzu viel, aber plötzlich, wenn man sozusagen bildlich darstellt,

ist es sehr viel. Das heißt, meine Auffassung ist wirklich, und das sieht man auch häufig in Diskussionen, sozusagen die Phänomene, die man versucht zu beschreiben, oder die Randbedingungen, sind sehr häufig linearer Natur. Wenn es natürlich in die Physik geht, dann treten nicht Linearitäten auf. Wenn Sie physikalische Phänomene beschreiben wollen, wie Flüsse oder Fluss eines Gases

durch Leitungssysteme dergleichen oder irgendwelche Strömungsmechanikaspekte, wie zum Beispiel wie ein Flugzeug fliegt oder dergleichen. Da kommen dann, aber die kommen aus der Physik oder aus der Natur, diese Prozesse, die dann diese Nicht-Linearitäten enthalten.

Wir wollen uns jetzt in der Vorlesung primär um diese Diskreten, also wir haben die Ganzheitsbedingungen und die linearen Bedingungen dabei. Unser Ziel wird immer sein, Lösungsmethoden zu finden, die global optimal Lösungen finden.

In der linearen Welt konnten wir das immer noch. Wir werden aber sehen, dass dieser Aspekt wegfällt. Er fällt sowohl jetzt weg in der diskreten Optimierung einerseits, aber auch wenn Sie dann noch Interesse haben an der nicht-linearen Optimierung, fällt er ebenso weg. In beiden Fällen schafft man es nicht mehr mit den gängigen Methoden, globale Optimallösungen zu finden,

sondern in der Regel nur lokale. In der Diskreten können wir ein Stück weiter gehen und auch Methoden bereitstellen, die letztendlich beweisbar gute, wenn nicht sogar optimal Lösungen finden, die aber dann im Worst Case exponentielle Laufzeit haben. Und genau in diesem Spannungsfeld werden wir uns bewegen und uns auch verschiedene Methoden anschauen,

verschiedene Modellierungsaspekte. Wir werden auch in den Übungen viel modellieren. Denn es ist wichtig, wenn man später Anwendungen lösen will, dass man ein richtiges Modell aufstellt. Das ist gar nicht so einfach, ein gutes Modell aufzustellen. Das ist auch etwas, was bislang so ein Stück weit in der Mathematik

bislang auch etwas vernachlässigt wurde. Wie finde ich ein richtiges Modell? Häufig hat man Modelle entwickelt, die nicht gut zur Anwendung gepasst haben oder gut zur Anwendung, aber dafür gab es dann keine Methoden. Und genau dieser Dreiklang Anwendung, Modell, Methoden, das muss passen, um wirklich dann auch Probleme in der Realität lösen zu können.

Und da werden wir später sehen, wenn Sie als Mathematiker fertig sind und Sie gehen dann irgendwo raus. Die Anwendungsfelder sind sehr vielfältig. Sie sind im Energiebereich, sie sind im Transport, im Verkehr, in der Logistik, in der Finanzwirtschaft und, und, und. Also die treten überall auf. Allein wir haben zum Beispiel, unsere Gruppe allein hat schon Projekte

mit der Deutschen Börse, mit Lufthansa, mit EON-Gastransport. Also aus den unterschiedlichen Bereichen treten diese Probleme auf. Aber sie treten dann dort auf, wo sozusagen die Spezialisten vor Ort häufig Ingenieure sind, anderes Hintergrundwissen haben,

mit anderen Methoden rangehen, als wir das vielleicht als Mathematiker gewohnt sind und als Mathematiker lernen wollen. Wo wir auch, ich hoffe auch, dass ich Sie in der Vorlesung dann überzeugen kann, dass das vernünftige Methoden sind, um die Probleme auf die Art und Weise anzugehen. Ja, und was wir jetzt sozusagen in dieser Vorlesung machen, ist sozusagen ein Gefühl zu kriegen, ah, für diese Modellierung solcher Anwendungen,

aber auch sozusagen, was sind die richtigen Methoden, wann kann ich denn welche Methoden sinnvollerweise verwenden, um solche Probleme lösen zu können. Gut, dann fangen wir, würde ich sagen, fangen wir einfach, gehen wir sozusagen in medias res. Also das erste ist sozusagen, ich fange einfach an mit, mit Einführung, machen wir erstmal Definitionen,

ein paar klassische Beispiele, klassische diskrete Optimierungsprobleme und dann werden wir einen kleinen Einschub machen gegenüber dem, was in dem Buch steht, nämlich wir müssen uns noch ein bisschen intensiver mit Polyedern beschäftigen. Ja, wir haben in der Einführung schon ein bisschen Polyeder kennengelernt,

was ein Polyeder ist, was eine Seitenfläche ist, was eine Facette ist, was eine Ecke ist, wie man über Polyeder optimiert. Das haben wir alle schon kennengelernt. Das wird uns für die diskrete Welt alleine nicht reichen. Da brauchen wir noch ein paar Eigenschaften und auch Methoden, was man mit Polyedern alles machen kann. Deswegen diesen Exkurs fügen wir hier an dieser Stelle noch ein,

bevor wir dann wirklich in die Theorie der ganzzahligen Optimierung einsteigen. Also fangen wir an mit Kapitel 1.

Einführung. Und wir fangen gleich an mit der ersten Definition im Buch. Deswegen, ich mache immer die Kapitel dazu, damit Sie wissen, wo das im Buch ist. Im Buch ist das sozusagen Kapitel 7.

Ja, und die Definition 7.1, weil dort gibt es natürlich vorher die Einführung in die Optimierung, die die ersten sechs Kapitel sind. Und da das dort fortlaufend nummeriert ist, fängt es sozusagen mit der Nummerierung 7 an. Also, Gemisch-Ganzzahlige Definition eines gemisch-Ganzzahligen Programmes.

Also meistens spricht man nur von, übernimmt man die englischen Bezeichnungen,

mixed integer program, oder kurz MIP. Also im Deutschen spricht man meistens von einem MIP sozusagen. Also was haben wir?

Wir haben ein Vektor C aus dem R hoch N. Wir haben eine Matrix aus dem R hoch M Kreuz N. Wir haben eine rechte Seite B aus dem R hoch M. Und wir haben eine Zahl P, die liegt zwischen 0 und N.

Dann heißt, maximiere C T x A x kleiner gleich B

und x aus Z hoch P Kreuz R hoch N minus P gemisch-Ganzzahliges Programm.

Gemisch-Ganzzahliges, ich schreibe es mal noch hier hin, lineares.

Deshalb, weil wir hier ein lineares Ungleichungssystem haben, man kann sich später noch überlegen, hier auch nicht-lineare Bedingungen zu erlauben. Dann wird es ein gemisch-Ganzzahliges nicht-lineares Optimierungsproblem oder mixed integer non-linear program. Das ist gerade sehr aktuelles Forschungsgebiet,

wie man solche gemisch-Ganzzahligen nicht-linearen Probleme löst. Weil man vereint sozusagen die Methoden der nicht-linearen Optimierung, diese, wenn Sie die Vorlesung noch hören, nicht in der nicht-linearen Optimierung kennenlernen, mit den Methoden, die wir hier jetzt im Rahmen der gemisch-Ganzzahligen linearen Programmierung kennenlernen wollen.

Da haben wir natürlich ein paar Spezialfälle drin. Die sehen wir auch. Wenn wir das P auf Null setzen, dann fällt der Z-Teil weg. Dann sind wir in der Welt der Einführung. Dann haben wir hier ein klassisches lineares Programm stehen. Und wenn wir das P auf N setzen, dann ist der kontinuierliche Teil weg.

Dann haben wir ein rein ganzzahliges lineares Programm. So wie sieht denn das geometrisch aus an dieser Stelle? Das wissen wir hoffentlich noch aus der Einführung. So ein a x kleiner gleich b beschreibt immer ein Polyeder.

Das typische Polyeder hat meistens fünf Ecken, was man so an die Tafeln malt. Jedes a x kleiner gleich b beschreibt einen Durchschnitt endlich vieler Halbräume. Das ist dieser Bereich.

Für was wir uns jetzt interessieren, sind ganzzahlige Punkte hier drin. Wenn ich das mal nach diesem Gitternetz anschaue, sind das die einzigen ganzzahligen Punkte, die da drin sind. Wir haben wieder unsere Zielfunktion.

Die maximieren wir in diese Richtung. Hier ist unser C. Und in diese Richtung optimieren wir unser Problem. Da sehen wir jetzt schon ein paar Schwierigkeiten, die allein durch diese Ganzzahligkeit auftreten. Vorher, als wir diese Ganzzahligkeit nicht hatten,

waren wir in der linearen Welt. Dann wusste man zum Beispiel Aussage, die Optimallösung wird immer an einer Ecke angenommen. Das war einer der ersten Aussagen, die auch relativ offensichtlich ist. Wir haben eine konvexen Menge. Wir optimieren eine lineare Funktion über eine konvexen Menge. Das muss am Rand angenommen werden. Das kann man iterativ machen. Die Optimallösung muss immer eine Ecke geben, die auch Optimallösung ist.

Sobald wir jetzt Ganzzahligkeit dazu nehmen, haben wir schon verloren. Die Optimallösung in dem Fall ist dieser Punkt. Der liegt im Inneren von diesem Polyeder.

Das heißt, diese Methode, die wir vorher kennengelernt haben in der Einführung, einfach mal den Rand entlang laufen, funktioniert nicht mehr. Wir müssen uns wirklich etwas Neues überlegen. Wir sehen auch noch eine Eigenschaft, die es auch noch schwierig macht. Das Problem ist nicht mehr konvex. Wenn Sie hier einen zulässigen Punkt haben und hier einen zulässigen Punkt,

dann ist die Verbindungsgerade nicht zulässig. Jeder Punkt hier dazwischen ist nicht zulässig. Das heißt, wir haben plötzlich ein nicht konvexes Optimierungsproblem. In der Einführung haben wir schon gesehen, Konvexität ist eine sehr nette Eigenschaft, die man natürlich gerne haben will, wenn man optimiert, aber die hier schon mal verloren geht, allein durch diese Randbedingungen.

Noch ein zweites Problem, was sehr ähnlich zu dem Gemisch Ganzzahligen ist, sind kombinatorische Optimierungsprobleme. Häufig wird so eine Vorlesung wie diese hier auch kombinatorische Optimierung genannt,

weil die Verwandtschaft zur Gemisch Ganzzahligen sehr nahe ist. Wir werden aber sehen, dass das noch ein bisschen allgemein ist als kombinatorische Optimierungsprobleme selber. Also wie sehen die aus? Das ist die Definition 1, 2.

Also auch hier lineares kombinatorisches Optimierungsproblem.

Wir haben gegeben eine Grundmenge E. Gegeben Grundmenge E. E soll endlich sein.

Also bei uns ist in der Regel immer alles endlich. In der diskreten Welt ist alles endlich. Was viele auch sagen, ist ja alles langweilig, weil wenn alles endlich ist, dann braucht man nur abzählen. Und eben das Beste, da kommen wir noch drauf, warum das Abzählen in der Regel nicht ganz so einfach ist. Ein Beispiel Reiskörner, die alle zu zählen,

ist vielleicht ein bisschen aufwendig. Dann haben wir eine Teilmenge I. Der Potenzmenge von E. Also wir bilden die Potenzmenge von E

und nehmen daraus eine Menge von Teilmengen raus. Die Elemente in I heißen zulässige Punkte oder heißen zulässige Mengen oder Lösungen.

Und wir haben eine Zielfunktion gegeben. Und eine Funktion C, die geht von der Grundmenge nach R.

Wir definieren C von F. Von der beliebigen Teilmenge ist nichts anders als die Summe der Einzel-Elemente E aus F. C von E für F.

Das ist dieser lineare Anteil. Daher dieses Wort linear, dass sich die Kosten für eine Teilmenge ergeben sich einfach durch Aufsummieren der Einzel-Elemente. Wenn man diese Eigenschaft nicht hat, kann man auch ganz schwer optimieren. Wir nehmen hier diese Potenzmenge

und wir geben jeder Teilmenge ein individuelles Gewicht. Wir wollen jetzt optimieren über diese Menge dieser zulässigen Teilmengen. Und wenn da kein funktioneller Zusammenhang zwischen den Teilmengen besteht, bleibt uns wirklich nichts anderes übrig, als jedes einzelne Element anzugucken.

Was ist das für ein Zielfunktionswert? Und dann den besten zu nehmen. Deswegen macht diese Voraussetzung, dass die Kosten sich linear bestimmen lassen

aus den Einzel-Elementen durchaus Sinn und ist auch in der Realität häufig so gegeben. Gut, dann das Problem. Jetzt kann man wieder maximieren. C von i, i aus der Menge der zulässigen Lösungen.

Beziehungsweise, nachdem man das natürlich auch als Minimum schreiben kann, Minimum C von i, i aus der Menge der zulässigen Lösungen heißt lineares kombinatorisches Optimierungsproblem.

Heißt lineares kombinatorisches. So, wie ist der Zusammenhang zwischen diesen beiden Welten?

Es zeigt sich, was man hier häufig machen kann, da werden wir nachher noch Beispiele sehen, diese als ganzzeige Programme formulieren. Was sie nämlich tun müssen, ist, sie müssen diese Menge i modellieren.

Und was sie entscheiden müssen, ist, welche Elemente dieser Grundmenge E sind Teil ihrer Lösung. Was man typischerweise macht, ist, zu sagen, ich führ eine Variable ein, xe, die sagt dies 1, wenn sozusagen das Element Kleine E aus der Grundmenge in der Lösung enthalten ist

und 0 sonst. Und häufig kann man diese Skript i Menge, die Menge der zulässigen Lösungen, über lineare Ungleichungen beschreiben. Da werden wir dann gleich noch Beispiele sehen. Und dann sind wir genau in dieser Welt. Nur haben wir dann eben aus dem z hoch b 0, 1 hoch p bzw. meistens dann 0, 1 hoch n gemacht,

wenn n die Kardinalität dieser Grundmenge E ist. Man kann sogar noch einen Schritt weitergehen und diese Probleme auch als lineare Programme auffassen. Dann schauen wir uns mal an, wie das funktioniert.

Und dann kann man sich überlegen, lineare Programme können wir ja lösen. Also wo liegt das Problem? Aber schauen wir uns das vielleicht mal an, wie das geht. Also jedes, wenn man als Bemerkung formuliert,

kombinatorische Optimierungsprobleme können als lineare Programme modelliert werden.

So wie machen wir das? Wir machen aus jeder Lösung, also hier, ich schreibe mal hier noch eine Abkürzung hin.

Man kürzt das gerne ab mit der Grundmenge I, die Menge der zulässigen Lösungen und der Zielfunktion C. Das sind genau die drei Tipps, das Trippel bestimmt eindeutig ein kombinatorisches Optimierungsproblem. Die Grundmenge, die Menge der zulässigen Lösungen und die Zielfunktion.

Wenn wir so einen Trippel haben, dann machen wir Folgendes. Dann führen wir den sogenannten Inzidenzvektor ein. Nämlich Chi für eine Teilmenge aus I.

Das machen wir einfach so. Chi E von F setzen wir auf 1, falls das E aus F ist. Und 0, falls E nicht in F ist. Aus jeder zulässigen Menge macht man 0,1 Vektor im R hoch N.

Das ist nichts anderes, als was wir hier machen. Und jetzt übersetzt sich unser Problem hier. Das ist eigentlich nichts anderes. Jetzt können wir einfach setzen, eine zulässige Menge Groß X ist einfach die Menge aller zulässigen Inzidenzvektoren.

Jetzt leben wir hier im R hoch N. Das ist eine Teilmenge des R hoch N. Das ist die Menge unserer zulässigen Punkte.

Das heißt unser Optimierungsproblem maximiere C von I. I aus diesem Skript I übersetzt sich jetzt ganz einfach in die Welle des R hoch N als maximiere C T X.

X aus X. Da haben wir jetzt eigentlich nur ummodelliert. Jetzt können wir noch eine nette Eigenschaft hier ausnutzen.

Nämlich was haben wir denn? Wir haben jetzt hier eine Menge von Punkten. Wir wissen sogar, das X ist endlich. Weil wir haben ja maximal Potenzmengen vieler solcher zulässiger Punkte. Das heißt das X selber ist endlich.

Und jetzt kommt eine Eigenschaft, die wir uns nachher noch anschauen werden, die wir bislang noch nicht bewiesen haben, ist, dass wenn ich die konvexe Hülle endlich vieler Punkte nehme, kommt wieder ein Polyeder raus. Also Conf von X ist ein Polyeder.

Das wird uns noch ein bisschen Mühe kosten, das zu tun. Das ist zwar in der Einführung glaube ich schon erwähnt worden, dass man für Polyeder unterschiedliche Darstellungen gibt. Einmal über die äußere Beschreibung, also in Form von Durchschnitt endlich vieler Halbräume. Aber es gibt auch die andere, die innere Beschreibung,

als Konvexkombination endlich vieler Punkte plus konische Kombination endlich vieler Vektoren. Und diese Eigenschaft, die müssen wir uns nachher noch herleiten, dass die auch tatsächlich immer gilt, weil wir werden öfters zwischen diesen beiden Darstellungen springen. Und manchmal ist die eine sinnvoller,

manchmal ist die andere sinnvoller. So das heißt, jetzt kommt die nächste Eigenschaft, die wir haben. Unsere Zielfunktion ist linear. Das Ding hier ist konvex. Das heißt, wenn ich eine lineare Zielfunktion habe, dann wird das Optimum, das wissen wir aus der letzten Vorlesung,

immer am Rand angenommen. Das heißt, dieses Ding, dieses Ding können wir jetzt auch schreiben, als irgendein Polyeder PAB. Und wir können hier weiterschreiben, das ist nichts anderes als konv, als maxx aus konv,

von x, ctx. Und das wiederum ist nichts anderes, als maximiere ctxx aus diesem Polyeder PAB. Nur zur Erinnerung, PAB war die Menge aller x aus r hoch n a x kleiner gleich b.

Und damit sind wir genau in der linearen Welt. Das heißt, jedes kombinatorische Optimierungsproblem können wir als ein lineares Problem darstellen. Den selben Trick können wir übrigens hier oben auch machen.

Wenn wir uns nochmal dieses Bild hier anschauen, also auch in diesem allgemeinen Fall,

nehmen wir mal der Einfachheit an, unser Polyeder hier ist beschränkt, ist also tatsächlich ein Polytop, so wie in diesem Bild, sind die Menge der ganzzahligen Punkte, die hier drin liegen, auch nur endlich viele. Das Einzige, was wir hier ausgenutzt haben bei dieser Transformation, ist, dass wir Endlichkeit haben der Anzahl Lösungen.

Das heißt, wenn wir das haben, können wir auch Konvexelhülle bilden. Und wenn wir das tun, dann kriegen wir hier auch so ein Teil wie hier. Und das Gelbe ist offensichtlich wieder ein Polyeder.

Das ist das, was wir noch beweisen müssen, aber zumindest mal schon mal am Bild stimmt. Das heißt, das Gelbe ist wieder ein Polyeder und wir haben die nette Eigenschaft, die Ecken hier sind ganzzahlige Punkte. Und wenn wir das wissen, jetzt haben wir ein klassisches lineares Programm.

Jetzt können wir alles, was wir in der Einführung gelernt haben, verwenden und Simplex- oder Ellipsoid-Methode oder innere Punkte-Methoden verwenden, um dieses lineare Programm zu lösen. Und dann landen wir natürlich, jetzt können wir am Rand laufen, dann landen wir sozusagen an dieser optimalen Ecke, aber die ist jetzt ja glücklicherweise ganzzahlig, weil wir nur die Konvexelhülle

der ganzzahligen Ecken hier genommen haben. Okay, so fertig. Das war es mit der Vorlesung. Lineare Programme können wir lösen. Die ganzzahligen haben wir jetzt auf die linearen reduziert und damit ist alles erledigt.

Oder könnte es da irgendwo einen Haken geben oder habe ich falsch argumentiert?

Also eine Sache, die natürlich offen bleibt erst mal, ist jetzt schon schnell hingemalt im R2 und diesem netten kleinen Beispiel, aber die Frage, die sich natürlich stellt, wie finde ich denn diese gelben Überebenen?

Also wenn ich mir hier das so anschaue, wie finde ich denn die? Und dann werden wir sehen, dass dieses Finden, das haben wir ja ein Stück weit auch in der Optimierung, in der Einführung schon zumindest angedeutet,

dass das Finden von solchen Ungleichungen, das Separierungsproblem, ist genauso schwer wie das genaue Optimierungsproblem. Das heißt, wenn das hier schwer war, ist auch das Finden von diesen Gelben schwer. Und das Zweite, was auch noch hinzukommen kann, ist, dass nicht nur das Finden schwer ist,

sondern es kann exponentiell viele oder eigentlich doppelt exponentiell viele in manchen Fällen sogar geben von diesen Dingen. Also sozusagen die Anzahl derer, die man braucht, kann manchmal drastisch hoch sein. Die Frage ist halt, wie sehen solche Polyeder in hohen Dimensionen aus?

Ist es eher so etwas wie so ein Kristall mit sehr wenigen glatten Flächen? Oder sieht es eher aus wie eine Diskokugel mit ganz vielen kleinen Fassettchen? Und häufig sieht es halt eher aus wie so eine Diskokugel. Das heißt, man braucht ganz viele von diesen kleinen Fassettchen,

um überhaupt annähernd gut diese Polyeder sozusagen zu beschreiben. Also hier sieht es leicht aus, aber da ist ein weiter Weg dorthin. Aber trotzdem ist es ein interessanter Weg, den wir dann auch gehen werden, wie findet man dieses gelbe Polyeder? Weil wenn wir das Gelbe haben, dann ist die Welt wieder einfach.

Dann haben wir die Methoden zur Verfügung, die wir brauchen. Und wir werden Methoden kennenlernen, die uns versuchen, zumindest einen Teil von diesem Gelben zu beschreiben. Wir müssen es ja vielleicht nicht vollständig beschreiben. Es reicht ja sozusagen, um diese optimale Ecke herum gut genug zu kennen.

Und wenn wir aus der Linie eine Ecke beschreiben, brauchen wir nur n viele Bedingungen in Dimension n. Also wenn wir die richtigen n finden, würde ja schon reichen. Aber diese richtigen n finden, werden wir sehen, es kann horrendschwer sein. Gut, schauen wir uns vielleicht noch ein paar,

bevor wir sozusagen einsteigen, ein Stück weit in diese Geschichte hiermit, dass das Konf ein Polyeder ist und wie man von dieser einen Darstellung in die andere kommt. Das wollen wir uns dann anschauen. Vielleicht noch ein paar klassische Beispiele aus dieser Welt erganz zeigen und kombinatorische Optimierungen,

die uns immer wieder begegnen werden. Jetzt haben wir nur ein Problem, dass wir eigentlich keinen Abzieher haben. Jetzt müssen wir mal gucken, wie das einigermaßen geht.

Also ein paar Beispiele.

Das Zuordnungsproblem.

Also nehmen wir mal an, wir sind eine Firma, wir haben n Mitarbeiter, wir haben n Jobs zu verteilen. Die Frage ist, wer macht welchen Job? Oder müssen wir nicht mal eine Firma sein? Das ist, wenn wir uns als kleine Gruppe treffen, Party vorbereiten oder sonst was.

Genau das gleiche Problem. Es gibt eine Menge von Aufgaben zu erfüllen. Jeder soll was machen und jeder hat unterschiedliche Präferenzen was zu machen. Die Frage ist, wie mache ich die optimale Zuordnung? Also wir machen es jetzt erstmal hier einfacher sozusagen, aber man kann sich das beliebig kompliziert vorstellen. Also Firma hat n Mitarbeiter und n Jobs.

Jeder, jede Person kann genau einen Job ausführen.

Kann genau einen Job ausführen. Und je nachdem, wie man sehen will, aus Firmen sich die Kosten sozusagen, wenn Mitarbeiter i Job j ausführt,

sein die Kosten sein. C j falls Person i Job j ausführt.

So, wie setzen wir kostengünstig unsere Mitarbeiter ein? Wie setzen wir kostengünstig die Mitarbeiter ein?

So, da haben wir jetzt ein vereinfachtes Szenario, aber an sich, vom Grundproblem her, schon eins, wie es in der Realität auftreten kann. Normalerweise haben wir vielleicht nicht genau so viele Jobs wie Mitarbeiter. In der Regel haben wir viel mehr Jobs als Mitarbeiter.

Man hat hier vielleicht dann noch zusätzliche Randbedingungen, dass jeder Mitarbeiter gleich viel zu tun haben soll. Gewisse Anforderungen, dass ein Mitarbeiter einen Job aus gewissen Gründen nicht durchführen kann, und dergleich mehr. Aber das Grundproblem ist genau dieses Zuordnungsproblem.

Wie modellieren wir das? Ist das ein ganz zeitiges Programm? Was müssen wir dazu tun, wenn wir das modellieren wollen? Wir haben einen Vorschlag.

Typischerweise fängt man an, bei der Modellierung überlegt sich die Variablen, also die Entscheidungen, die es zu treffen gilt. So, was sind hier die Entscheidungen, die wir treffen müssen?

Also, wie weise ich Mitarbeiter i Job j zu? Also, führe ich solche Variablen ein der Form xij. xij setzt sich auf 1, falls Person i Job j ausführt und 0 sonst.

Das ist genau die Entscheidung, die wir treffen wollen.

So, wie sieht jetzt das Modell aus? Wie sieht die Zielfunktion aus? Ein bisschen müde heute, oder wie? Indigiere. Summe der cij xij. Wir summieren hier über alle i,

über alle Mitarbeiter nennen wir mal die i aus 1 bis n und j aus 1 bis n. So, was sind die Randbedingungen?

Wir haben hier die Bedingungen, jede Person kann genau einen Job ausführen. Das heißt, wenn ich über die Jobs summiere, ich schaue mal einen Mitarbeiter an, dann darf der genau einen Job nur machen.

Also, wenn ich mal einen festen Mitarbeiter i anschaue und ich summiere über alle Jobs, dann darf der genau einen machen. Genauso habe ich natürlich noch die zweite Bedingung aus Jobsicht. Jeder Job sollte natürlich auch nur von einem gemacht werden. Also habe ich hier, wenn ich umgekehrt summiere,

über alle i xij ebenfalls ein gleich 1 stehen. Ist das das ganze Modell? Es fehlt noch etwas.

Genau, also xij, das muss man auch dazuschreiben. Aus 0, 1.

Und da haben wir jetzt so ein klassisches, diskretes Optimierungsproblem, wo wir also, wenn wir uns das mal anschauen, eine sehr einfache Struktur von Randbedingungen, alles nur, wenn wir die Matrix angucken, stehen nur 0 und 1 drin. Und man hat nur Gleichheitsbedingungen, und rechte Seite nur gleich 1.

Das ist ein klassisches kombinatorisches Optimierungsproblem. Wir werden später sehen, dass wir diese Bedingungen uns sogar hätten schenken können. Das ist eins von den Problemen, wo wir automatisch Ganzzahligkeit kriegen. Eines der wenigen, wo wir automatisch Ganzzahligkeit kriegen. Wir werden später analysieren, woran das liegt.

Das liegt nämlich genau an dieser Struktur von dieser Matrix. Es gibt ganz wenige Ausnahmen von Matrizen, die automatisch eine Ganzzahligkeit liefern. Das ist eine solche. Das heißt, solche klassischen Zuordnungsprobleme sind einfach lösbar. Das werden wir später noch genau anschauen,

woran es liegt. Allerdings, sobald wir eine zusätzliche Randbedingung dazu nehmen, zerstört das diese Einfachheit. Wenn wir unser Bild dann noch mal anschauen, dieses Einfach hat sich ja darin manifestiert, dass wir hier automatisch diese Ecken ganzzahlig hatten,

von dem Bild, was wir vorher hatten. Sobald ich jetzt eine zusätzliche Randbedingung reinnehme, dann zerstört es mir diese Eigenschaft. Weil plötzlich kriege ich dann an diesen Stellen neue Ecklösungen rein, die nicht mehr automatisch ganzzahlig sind.

Und wann sozusagen hinzunehmend von solchen Randbedingungen die Ganzzahligkeit nicht zerstört, das schauen wir uns auch noch an. Aber in der Regel, das sieht man schon in den Bilden, in der Regel wird die zerstört. Gut, ein zweites klassisches vielleicht, ich mache noch zwei klassische,

ist das Rucksackproblem, das wir noch haben. Im Übrigen, diese Art Zuordnungsprobleme, die treten auch heute noch in den Firmen auf. Wir haben schon mit zwei unterschiedlichen Firmen

praktisch so ein Projekt laufen. Zum Beispiel Servicetechniker. Wenn Sie Linde anschauen, hier diese Gaszylinder, die überall rumstehen, auch im Mathebau, hinter Mathebau steht so ein Gaszylinder. Diese Gaszylinder werden von Linde Gas betreut. Die haben Servicetechniker, die regelmäßig sozusagen hier vorbei fahren

und gucken, ob das alles noch in Ordnung ist oder das Gas wieder beliefern. Und die Frage ist, welcher Servicetechniker kümmert sich um welchen Kunden. Allein für so eine Region München, die haben fünf oder sieben Servicetechniker, die haben knapp tausend Kunden. Die Frage ist, welcher Techniker bedient welchen Kunden.

In die Kosten kommt wirklich die Fahrtkosten rein. Also was kostet es, dort hinzufahren, die Zeit vor Ort, die Rückfahrt und alles. Es geht alles in dieses C.J. ein. Da haben wir schon so ein klassisches Problem. Nur in der Realität, da kommen noch andere Bedingungen dazu. Weil da kommt zum Beispiel die Bedingung rein, alle sollen ungefähr gleich viel zu tun haben.

Das macht sofort das Ding kaputt, so wie hier oben. Dass jeder gleiche Auslastung hat, führt genau zu so einer Bedingung, wo mitten durch so ein Polyeder schneidet. Und was dann auch die Algorithmen, die man dazu braucht, schwer macht. Dann kann man sogar überlegen,

was sie auch überlegt haben, dass die Standorte der Mitarbeiter gar nicht fest sind. Bislang hatten die das so gemacht, dass alle Techniker morgens in München in der Stadtmitte beginnen und dann rausfahren, nach Augsburg, nach Rosenheim, nach was weiß ich wohin. Und wenn einer das halbe Jahr morgens nach München reinfährt

und dann gleich wieder nach Rosenheim raus, warum zieht einer gleich nach Rosenheim? Das kann durchaus Sinn machen, für so eine Firma Mitarbeiter umzuziehen und alles zu bezahlen, inklusive Eigenheim. Kann günstiger sein, als wenn der täglich erst nach München reinfährt und dann wieder da raus. Also auch solche Überlegungen,

dann kommen Entscheidungen, Standortprobleme rein. Wo ist denn ein idealer Standort, um Kunden zu bedienen? Auch Entscheidungsvariablen, also auch wieder eine Erweiterung von diesen Zuordnungsproblemen, auch wieder ein diskretes Problem. Schauen wir uns das zweite klassische an,

das ist das Rucksackproblem. Nehmen wir an, wir haben wieder eine Firma, und diesmal haben wir ein Budget.

Die Firma hat ein Budget B und will in N Produkte investieren.

Jedes Produkt I kostet A I Einheiten

und erzielt Gewinn C I. In welche Produkte soll die Firma investieren?

In welche soll die Firma sowas machen?

Wieder, wenn wir modellieren wollen. Erstens, was sind unsere Variablen? Das ist in dem Fall ähnlich wie oben. Wir wollen entscheiden, investiere ich in ein Produkt I,

ja oder nein? Also haben wir Variablen X I eins, falls Investition in ein Produkt I und null sonst.

Wir wollen unseren Gewinn maximieren, d.h. wir maximieren Summe C I X I I gleich 1 bis N, das ist unsere Zielfunktion. Und die einzige Restriktion, die wir haben, ist, dass wir unser Budget einhalten müssen,

also Summe A I X I kleiner gleich B I gleich 1 bis N, das ist unsere einzige Nebenbedingung. So unnatürlich, was wir nicht vergessen dürfen, auch hier wieder.

alle Variablen sind nur 0 oder 1 wertig. Das nennt sich das klassische Rucksackproblem. Wenn man jetzt überlegt, es sieht eigentlich überhaupt nicht schwer aus, das Problem. Wir haben nur eine Randbedingung. Wenn wir das mal in der linearen Welt vergleichen,

ich weiß nicht, ob Sie das in der Übung gemacht haben, in der Einführung, eine Nebenbedingung, da können Sie die Optimallösung ablesen. Mit simplen Sortieren können Sie sofort die Optimallösung angeben in der linearen Welt. In der Ganzzeitung ist es leider nicht so. Das Problem ist ein schweres Problem im Sinne von Komplexitätstheorie.

Haben alle schon etwas von mp-vollständig oder mp-schwer gehört? Wem sagt denn der Begriff mp-vollständigkeit noch nichts? Einer, zweieinhalb. Gut, also werde ich dann später mal vielleicht so einen kleinen Exkurs machen,

was mp-vollständig und mp-schwer heißt. Also letztendlich heißt, vereinfacht gesagt, für die gibt es bislang oder sind bislang keine gutartigen Algorithmen bekannt. Und unter gutartigen Algorithmen versteht man einen, der polynomialer Laufzeit hat.

Also in der Länge der Eingabe sozusagen polynomial. Und sollten Sie einen finden, so einen Algorithmus, oder zeigen, dass es keinen solchen gibt, genau für dieses Problem zum Beispiel. Also das gehört zum Problem der mp-schweren Probleme.

Sollte Ihnen ein Algorithmus für das Problem einfallen, der polynomialer Laufzeit hat, dann kriegen Sie wahrscheinlich Doktortitel, Professorentitel und eine Million Dollar auch noch, weil das gehört zu diesen sieben Problemen, die im Jahr 2000 ausgekürt wurden als die Hauptfragestellung in der Mathematik

in dem nächsten Jahrhundert sozusagen. Oder Sie weisen nach, dass wir dieses Problem keinen geben kann. Und die Vermutung ist, dass es vermutlich keinen gibt, weil jetzt schon seit 30 oder 40 Jahren Leute versuchen einen zu finden und keinem ist bislang einer eingefallen. Aber das muss ja nichts bedeuten.

Im Vermaatzsatz haben auch 350 Jahre die Leute rumgeknobelt, bis sie das eigentlich bewiesen haben, dass es nicht geht. Meine Schwierigkeit ist immer, nachzuweisen, dass was nicht geht. Das ist in der Regel immer deutlich schwerer als zu zeigen, ja es geht was, weil dann muss ich es ja nur zeigen und machen.

Während das, was nicht geht, ist da immer deutlich schwieriger. Und deswegen ist momentan schon das Gefühl an der Stelle, es geht vermutlich nicht. Es gibt keinen gutartigen Algorithmus für diese Art von Probleme. Aber dieses Problem taucht praktisch überall auch auf. In meinen Budgetfragen haben Sie immer zu wenig Geld.

Das heißt, diese Randbedingungen, dass es irgendwelche Knappheiten gibt an Ressourcen, sei es jetzt Geld, sei es an Materialien, an Rohstoffen oder was auch immer, die ist praktisch immer gegeben. Und wenn Sie Entscheidungen treffen, haben Sie es immer unter knappen Ressourcen. Sonst brauchen Sie ja nichts zu entscheiden. Wenn Sie eh alles machen können, weil Sie genug Kohle oder sonst was haben,

dann machen Sie einfach alles. Das heißt, sobald Sie ein interessantes Optimierungsproblem haben, tauchen solche Art von Bedingungen auf. Und wenn Sie an die ursprüngliche Definition von Gemischkanzleinprogrammen denken, letztendlich stecken die auch schon drin. Weil jede einzelne Zeile einer Matrix, wenn Sie die A x kleiner gleich B anschauen

und sich eine Zeile daraus nehmen, dann ist es genau von diesem Typ. Das heißt, jede einzelne Zeile beherbergt sozusagen eine Art Rucksackproblem hier drin. Und damit ist es durchaus legitim zu fragen, verstehe ich denn wenigstens mal eine solcher Randbedingungen.

Und das Witzige ist, man hat bis heute nicht mal dieses Polyeder, was dazu gehört, das ganze Zeige, vollständig verstanden. Es gibt exponentiell, ich glaube sogar doppelt exponentiell, viele solcher Ungleichungen, die allein dieses ganze Zeige Polyeder beschreiben.

Woran liegt das? Ich meine, letztendlich geht hier sehr viel, wenn man genau mal hinschaut. Ich meine, die Schwierigkeit kommt rein, wenn hier krumme Zahlen stehen. Und dann stellt sich schnell die Frage, kann ich mit krummen Zahlen hier ein gewisses Budget oder eine gewisse Zahl gut erreichen? Das geht dann sehr schnell in Fragen der Zahlentheorie.

Wie kann ich sozusagen gewisse Zahlen hier ganz zahlig darstellen? Das ist eine klassische Frage dort. Und wenn Sie jetzt hier ganz krumme Zahlen und große Zahlen nehmen, dann ist das durchaus eine schwierige Fragestellung, sowas beantworten zu können.

Gut, vielleicht noch ein Klassiker am Schluss. Das ist das Setpacking Partitioning oder Covering Problem.

Setpacking, Partitioning und Covering. Also wir haben wieder eine Grundmenge, E, nochmal 1 bis M.

Wir haben wieder eine Liste von Teilmengen, FJ, Teilmenge von E für J gleich 1 bis N. Und mit jedem FJ hat Kosten oder Erträge je nach dem CJ.

So und jetzt müssen wir uns eine Auswahl finden. Finde eine Auswahl an FJs, sodass jedes Grundelement höchstens genau oder mindestens einmal vorkommt.

So dass jedes Grundelement höchstens, dann spricht man von Packing genau,

dann spricht man von Partitioning oder mindestens dann spricht man von Covering

oder mindestens dann spricht man von Covering mindestens einmal vorkommt. Finde eine Auswahl, also dann müssen wir hier die C, die bezüglich C optimal ist.

So wie modellieren wir das?

Wir hatten einen Vorschlag.

Als Grund ist immer das gleiche. Wir müssen immer überlegen, was sind die Entscheidungen, die wir fällen.

Wir müssen entscheiden, welche der FJs nehmen wir mit. Also führen wir eine Variable ein für jedes FJ. Also XJ setzen wir wieder auf 1, falls FJ gewählt und Null sonst.

Das ist das eine. So jetzt führen wir noch zusätzlich eine Matrix ein, die uns sagt, sei A eine Matrix aus 0, 1 hoch M Kreuz N

mit, indem wir einfach an die J-Spalte den Inzidenzvektor des J-Elements hier schreiben.

Also die J-Spalte, kürzen wir so ab, ist Inzidenzvektor von FJ.

So wie sieht dann unser Problem aus? Dann sieht unser Problem so aus, dass wir minimieren. Unsere Zielfunktion ist dann nichts anderes als C transponiert X. Und wie sieht es jetzt aus, höchstens 1 mitzunehmen, das Set Packing,

ist dann nichts anderes als AX kleinergleich dem 1-Vektor. X aus 0, 1 hoch N.

Also dieses kleinergleich ist Packing, gleich ist Partitioning, größergleich ist Covering. Und je nachdem Min oder Max ist ja in der Zielfunktion an sich egal.

Wir können ja mal ein kleines Beispiel dazu anschauen. Also wir haben eine Grundmenge 1, 2, 3, 4. Das sei unser E. Wir nehmen uns mal ein paar Mengen raus.

F1, ich mach sogar noch eins kleiner. Mach mal noch eins kleiner. Ich mach mal F1, 1, 2. F2, 2, 3.

Und F3, 1, 3. Ein bisschen warten, dass man es lesen kann. Das nächste Mal bringe ich einen Wischer mit. So wie sieht unsere Matrix aus? Das ist in dem Fall eine 3 x 3 Matrix.

Hier habe ich sozusagen F1, F2, F3. Ich habe drei Grundelemente. 1, 2, 3. Ich schreibe einfach überall eine Eins hin, wo hier drüben sozusagen die Elemente auftauchen.

Das ist die Matrix. Und damit steht hier das Problem. Wir können das auch nochmal ausführlich schreiben.

Ich maximiere C1 x 1 plus C2 x 2 plus C3 x 3. Unter der Bedingung x 1 plus x 2. Ich mache mal den Kleingleichfall. Kleingleich 1 x 2 plus x 3. Kleingleich 1. Und x 1 plus x 3.

Kleingleich 1. Das war jetzt für das Beispiel. Und das Interessante. Solche Probleme, die lassen sich... viele dieser Probleme kommen, lassen sich in Grafen formulieren.

Wir haben das unnötig an der Stelle schon eh geschrieben, weil es häufig in Grafen Anwendungen hat. Ich weiß nicht, wer von Ihnen algorithmische, diskrete Mathe hat. Ein paar gehört noch niemand. Das gibt es erst seit letztem Sommer. Grafen und Algorithmen.

Wer weiß überhaupt nicht, wer z.B. keinen Deichstrahler Algorithmus kennt. Alle kennen einen. Wunderbar. Dann kennen Sie natürlich auch die Grundkonzepte hier. Die Frage ist, was für ein Problem verbirgt sich hinter dem, was ich hier eigentlich gerade hingeschrieben habe.

Wenn wir das Grafen theoretisch anschauen. Wenn wir mal die Grundmenge hier annehmen, nehmen wir an, das sind Knoten hier. 1, 2, 3. Was sich hier steht, x1 und x2 dürfen nicht gleichzeitig. Wenn immer ich so eine Bedingung habe,

dann mache ich mal eine Kante rein. 1 und 2 dürfen nicht gleichzeitig. 2 und 3 darf ich nicht gleichzeitig wählen. Und 1 und 3 darf ich nicht gleichzeitig wählen. Das heißt, ich muss jetzt hier eine Knotenauswahl finden, sodass diese Bedingungen erfüllt sind. Aber ich darf hier sagen, welche ich nicht gleichzeitig nehmen darf.

Das ist in der Grafentheorie das stabile Mengenproblem. Was als Lösung rauskommt, ist eine stabile Menge. Also eine Teilmenge der Knoten, sodass keine zwei miteinander benachbart sind. Wenn ich hier für jede Kante, die ich hier habe, so eine Bedingung aufschreibe, dann habe ich garantiert, dass keine zwei benachbart sind.

Das heißt, ich darf hier maximal einen Knoten wählen. Oder in größerem Zusammenhängen, wenn hier noch einer wäre, wie auch immer, wenn wir einen vierten da reingenommen hätten, hätten wir den zum Beispiel auch noch nehmen können. Also es ist eine Teilmenge der Knotenmenge, die paarweise nicht miteinander benachbart sind.

Sowas nennt man eine stabile Menge. Hier kann man zum Beispiel das stabile Mengenproblem modellieren. Damit kann man das Färbungsproblem modellieren. Falls ihr das schon mal gehört am Grafen. Also wie farbig, kostengünstig Landkarten ist praktisch hier auch drin versteckt. Das interessante, und hier sehen wir, da haben wir nicht so eine nette Eigenschaft,

die wir bei dem Zuordnungsproblem haben. Weil wenn wir hier das lineare Programm lösen, kommt nicht automatisch eine ganz zeige Lösung raus. Warum nicht? Nehmen wir mal die C raus. Machen wir einfach eins als Zielfunktion. Also wir maximieren einfach x1 plus x2 plus x3.

Sieht jemand eine Lösung, die besser als eins ist, wenn ich gebrochene Werte erlauben?

Alle in halb. Also wenn ich x1 gleich x2 gleich x3 gleich in halb setze, dann kriege ich in der Zielfunktion eineinhalb. Das ist eine offensichtliche Lösung, die nicht erlaubt ist.

Und damit sehen wir sozusagen, das Polyeder, was hier dazu gehört, hat eine gebrochene Ecke. Da fehlt eine Bedingung. Und wie man die findet, das werden wir uns auch im Laufe der Vorlesung mal überlegen. In dem Fall kann man sie vielleicht sogar einfach finden, was die Bedingung ist.

Das Abschneiden können Sie mal überlegen. Aber an sich sonst, diese Art Anwendung wird sehr häufig verwendet, auch in der Modellierung. Gerade wenn man Randbedingungen hat, die sehr schwer modellierbar sind. Also typischerweise zum Beispiel, wo das erstmalig angewendet wurde, ist beim Airline Cruise Scheduling. Also wenn Sie Ihre Airlines haben,

die Crews, die immer auf den Fliegern sind, die machen immer solche Rundtrips. Die fliegen von mir aus Frankfurt, New York, Frankfurt, Frankfurt, Madrid, Madrid, Athen, Athen, Frankfurt. Und das ist so ein Schedule einer Crew. Und jetzt haben Sie sozusagen jede Spalte, dieser Matrix ist eine Flugroute einer solchen Crew.

Die Anzahl Zeilen sind alle Flüge, die die Lufthansa anzubieten hat. Und jetzt müssen Sie einfach Ihre Crews auf diese Flüge verteilen, sodass natürlich, in dem Fall haben Sie diesen Gleichheit oder größer Gleich auf jedem Flug mindestens eine Crew ist.

Manchmal lässt sich es nicht vermeiden, dass eine zweite da ist, aber die ist dann außer Dienst auf dem Flieger. Also typischerweise modellieren Sie das dann als ein AX gleich B. Die Zeilen sind Ihre Flüge. Jeder Flug muss genau einmal abgedeckt sein und die Rundreisen der Crews müssen so organisiert sein, dass genau auf jedem Flug einer ist.

Da kriegen Sie Probleme mit mehreren Millionen Spalten, d.h. mehrere Millionen 01 Bedingungen mit ein paar Hundert Zeilen. Diese Probleme waren vor 20 Jahren noch sehr schwer zu lösen, bis gar nicht lösbar. Heute sind die Methoden inzwischen so weit, dass man die praktisch sagen kann,

die sind einfach lösbar. Also auch nur mal ein bisschen einen Hinweis zu geben, wie weit sich die Algorithmen und die Methoden in den letzten 20, 30 Jahren verbessert haben, um auch solche Art von Probleme zu lösen mit mehreren Millionen von 01 Variablen. Gut, so weit vielleicht der Einführung.

Das sind so drei Klassiker, wir werden später noch ein paar andere kennenlernen. Wir werden auch uns ein paar richtige Anwendungen dann irgendwann mal angucken, wie man die vielleicht modelliert und auch lösen kann. Aber jetzt wollen wir uns ein bisschen heranarbeiten, wie wir denn solche Probleme lösen können.

Und dazu müssen wir Polyeder besser verstehen, als wir sie vielleicht schon verstehen. Weil ohne die geht es nicht,

das haben wir an den Beispielen schon gesehen.

Also Grundlagen der Polyedertheorie ist das Kapitel 1, 2.

Im Buch ist das Kapitel 5, 5. Also Kapitel 5, 5 in dem Buch. Also ein ganz wichtiges Konzept wird sein und das wollen wir uns als erstes arbeiten,

ist Projektion. Projektion haben Sie sicherlich auch schon mal in der Analyse und auch in der linearen Algebra gesehen. Was wir hier uns jetzt erarbeiten wollen, wie projiziert man Ungleichungssysteme und was kommt dann wieder raus. Und wenn man das Ganze wiederholt, was kommt dann wieder raus und so weiter. Und wir werden sehen,

dass Projektion die Polyedereigenschaft erhält. Wenn Sie ein Polyeder haben, das irgendwo hinprojiziert, kommt wieder ein Polyeder raus. Macht intuitiv auch irgendwo Sinn, wenn Sie so eine Disko-Kugel hier an die Wand projizieren, dann ist der Schatten wieder ein Vielegg. Es kommt wieder ein Polyeder raus.

Und eine nette Eigenschaft, die man natürlich mit Projektion auch hat. Und da wären wir jetzt eine Alternative zum Fahrkastlämmer. Das erinnert sich ein oder andere noch an das Fahrkastlämmer. Wir haben hier eine Alternative unser Arbeiten. Nämlich, wie kann ich denn feststellen, ob ein Ungleichungssystem einen zulässigen Punkt hat oder nicht? Das ist Fahrkastlämmer.

Entweder das existierte A x kleiner gleich b oder alternativ ein anderes Ungleichungssystem hat eine Lösung. Also ich kann sozusagen sehr einfach feststellen, ob ein Ungleichungssystem unzulässig ist oder nicht. Das kann ich auch mit diesen Projektionsgedanken machen. Warum?

Also ein Ungleichungssystem, zulässiger Punkt heißt, er hat das zugehörige Polyeder einen zulässigen Punkt, ja oder nein. Was ist die Idee, die wir verfolgen wollen? Naja, ich habe hier dieses Objekt, wo ich nicht weiß, ist leer oder nicht, dann projiziere ich es mal an die Wand. Wenn es nicht leer war, muss es einen Schatten geworfen haben. Also muss auch der Schatten nicht leer sein.

So, und das wiederhole ich, jetzt bin ich an der Wand, jetzt projiziere ich es an die Kante. Und wieder das gleiche Argument, wenn vorher da ein Schatten war, ist auch an der Kante ein Schatten. Und das reduziere ich bis auf den singulären Punkt runter. Und wenn es vorher einen zulässigen Punkt hatte,

muss auch nachher an diesem singulären Punkt der da gewesen sein. Und wenn nicht, dann kann ich das an der Stelle entscheiden. Also sozusagen Unzulässigkeiten projizieren sich auf die Dimension runter. Und wie man das macht, wie man das ausrechnet, da werden wir ein Verfahren entwickeln, diese Fourier-Modzkin-Elimination,

die uns auch genau diesen Projektionsvorgang beschreibt, nicht nur beschreibt, sondern sogar einen Algorithmus dafür angibt, wie man projiziert. Und das ist das, was wir uns jetzt erarbeiten wollen, das ist das 1-2-1-Projektion von Polyedern.

Also wir schauen uns die erste Definition an. 1, 9. Wir machen das erstmal sehr allgemein für zwei

Mengen aus dem R hoch N. C sei die Projektionsrichtung, sei nicht der Nullvektor, sondern heißt die Menge aller X in H. Es existiert ein Lander aus R mit

X plus Lander C aus S Projektion von S auf H

entlang C. Eine Besonderheit noch, also ist H von der Bauart,

also genau eine Hüberebene, die dann spricht man von einer orthogonalen Projektion. So heißt die Projektion.

So wie sieht das aus? Schauen wir uns vielleicht mal ein Bild an. Also hier habe ich irgendwo meine Menge S.

Hier habe ich meine Menge H. Jetzt will ich projizieren entlang Richtung C. So ich will diese Menge S

auf das H projizieren. Wie mache ich das? Ich muss einfach gucken, anschauen, schauen wir mal in die Definition. Es ist immer eine Teilmenge, was wir hier sehen, Projektion ist

eine Teilmenge von H. Also das heißt, ich schaue mir einen Punkt an, X in dem H und jetzt muss ich in Richtung den C laufen, in die oder in die Richtung, und muss das S treffen. Also wenn ich es für diesen Punkt mache und ich laufe in Richtung C,

und wenn ich den geeignet skaliere, dann komme ich tatsächlich in dem S an. Wenn ich es für diesen Punkt mache und ich laufe in Richtung C, dann komme ich nie in den S an. Also die Projektion von dem S auf das H, in diesem Fall wäre genau dieses kleine Eck da unten.

Und wenn wir den besonderen Fall nehmen, dass wir hier das S haben irgendwo und das H ist jetzt eine Hüberebene, das wäre unser H, wo genau in die Richtung

von dem C schaut. Also wenn das die Projektionsrichtung ist und wir schauen uns diesen Fall hier an, dann ist das ja der normalen Vektor, das C. Das heißt, es zeigt genau in diese Richtung. Dann kriegen wir genau

diesen Bereich hier. Das ist die Projektion. Und das ist das, was wir dann machen wollen. Wir wollen es nicht nachher für allgemeine Mengen S und H, sondern wir wollen es für solche Hüberebenen machen und wir wollen es hier für Polyeda machen. Wir sehen schon sozusagen,

letztendlich ist es so eine Art Schattenalgorithmus. Wie projiziere ich sozusagen solche Mengen auf jeder Dimensionale Objekte und wie kann ich, wenn ich das hier kenne und das hier kenne, wie kann ich diese gelbe Menge beschreiben? Die kann man im Fall von Polyedern tatsächlich explizit beschreiben

und auch explizit ausrechnen. Aber das schauen wir uns dann nächste Woche an. Vielen Dank.