Descision-Based Approaches - Branch-and-Bound
This is a modal window.
The media could not be loaded, either because the server or network failed or because the format is not supported.
Formal Metadata
| Title |
| |
| Title of Series | ||
| Part Number | 8 | |
| Number of Parts | 12 | |
| Author | ||
| License | CC Attribution - NonCommercial - ShareAlike 3.0 Germany: You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor and the work or content is shared also in adapted form only under the conditions of this | |
| Identifiers | 10.5446/21467 (DOI) | |
| Publisher | ||
| Release Date | ||
| Language |
Content Metadata
| Subject Area | ||
| Genre | ||
| Abstract |
|
12
00:00
IntegerLinear mapComputer programmingVariable (mathematics)Binary fileSubsetMaxima and minimaKonvexes PolygonZusammenhang <Mathematik>Linear algebraSummationMatrix (mathematics)SummationLösung <Mathematik>Direction (geometry)GradientGanzzahlige LösungInequality (mathematics)Set (mathematics)Euclidean vectorSolution setVariable (mathematics)LinieMathematisches ProblemTheoryZahlPolygonZielfunktionNumberComputer animation
06:47
IntegerLinear mapSymplectic manifoldTravelling salesman problemMaß <Mathematik>Fundamental theorem of algebraBound stateFeasibility studyDecision tree learningMathematical optimizationSubsetConstraint (mathematics)Network topologyArc (geometry)RootZielfunktionComputer programmingINTEGRALLinear programmingMatching (graph theory)Similarity (geometry)DivisorGraph (mathematics)Graph (mathematics)WeightMaxima and minimaSymmetric matrixDrop (liquid)Gaussian eliminationCombinatoricsEckeLösung <Mathematik>Configuration spaceSolution setNetwork topologyUntere SchrankeSupremumKanteSummationZielfunktionVertex (graph theory)Partition of a setSet (mathematics)ComplementarityCost curveDirection (geometry)Relaxation
16:54
Feasibility studyMathematical optimizationBound stateZielfunktionMaxima and minimaLemma (mathematics)Computer programmingLinear mapIntegerINTEGRALConstraint (mathematics)Linear programmingSolution setZielfunktionDirection (geometry)KanteKantenmengeUntere SchrankeBerechnungMatching-ProblemSubsetBerührung <Mathematik>IntegerSet (mathematics)Lösung <Mathematik>Energy levelVertex (graph theory)Constraint (mathematics)Plane (geometry)Link (knot theory)Matching (graph theory)ZeitraumNetwork topologyIntegral elementCloning
25:57
Similarity (geometry)CombinatoricsMathematical optimizationGraph (mathematics)WeightMaxima and minimaDivisorGraph (mathematics)SubsetSymmetric matrixGaussian eliminationConstraint (mathematics)Drop (liquid)Ganzzahlige LösungDirection (geometry)Vector graphicsEckeThree-dimensional spacePolygonBounded setKanteSolution setUntere SchrankeDimension nOptimumSeries (mathematics)Negative numberMathematicsGradientConstraint (mathematics)Half-space (geometry)Search algorithmInterface (chemistry)Coordinate systemLösung <Mathematik>SquareIntegral elementRoundingRelaxationTwo-dimensional spaceComputer animation
35:01
Travelling salesman problemCombinatoricsSymmetric matrixGraph (mathematics)Network topologyVertex (graph theory)Inequality (mathematics)KanteNetwork topologySummationWeightStress (mechanics)Incidence algebraPlane (geometry)Set (mathematics)Link (knot theory)Gebiet <Mathematik>Spanning treeLinear programmingRoundingLengthPredictionEquivalence relationLength of stayVector graphics
44:05
Mathematical optimizationModel theoryVector spaceVariable (mathematics)Linear mapFunction (mathematics)Decision theoryConstraint (mathematics)Drop (liquid)Lagrange-MethodeSimilarity (geometry)WeightMaxima and minimaGraph (mathematics)Graph (mathematics)SubsetDivisorSymmetric matrixGaussian eliminationCombinatoricsSymplectic manifoldImplicit function theoremAlgebraLösung <Mathematik>Function (mathematics)CurveZusammenhang <Mathematik>MathematicsCoefficientValuation using multiplesKennzahlZielfunktionNormal (geometry)Propositional formulaGanzzahlige OptimierungEquationEquationComputer programmingKanteNichtlineares GleichungssystemInequality (mathematics)Differentiable functionVariable (mathematics)Linear algebraImage resolutionSolution setLinear equationMathematical analysisSystem of linear equationsLagrange-MethodeLineares Ungleichungssystem
53:08
Mathematical optimizationFeasibility studyVector spaceConstraint (mathematics)ZielfunktionSymplectic manifoldFunction (mathematics)Model theoryVariable (mathematics)Linear mapLagrange-MethodeDrop (liquid)Maxima and minimaDecision theoryZielfunktionUntere SchrankeNeighbourhood (graph theory)Vector graphicsValuation using multiplesFunction (mathematics)SummationBoom barrierWeightGreatest elementKanteSolution setPoint (geometry)Set (mathematics)Matrix (mathematics)Term (mathematics)Sign (mathematics)Mathematical optimizationLengthConstraint (mathematics)
01:02:12
Mathematical optimizationFeasibility studyVector spaceLagrange-MethodeConstraint (mathematics)ZielfunktionSymplectic manifoldFunction (mathematics)Maxima and minimaInfinityJunction (traffic)SupremumNetwork topologyAbstieg <Mathematik>Direction (geometry)Differentiable functionSubdifferentialNumerical analysisGradientDifferentiable functionGreatest elementNegative numberMathematical optimizationNumberMathematicsBound stateUntere SchrankeValuation using multiplesSchrittweiteConstraint (mathematics)OrbitFunction (mathematics)HöheComputer programmingMathematical structureComputer animation
01:11:15
Travelling salesman problemSymmetric matrixLinear programmingGraph (mathematics)Variable (mathematics)Set (mathematics)ComplementarityConstraint (mathematics)QuotePlane (geometry)Computer programmingVariable (mathematics)Partition (number theory)MathematicsDirection (geometry)Inequality (mathematics)KanteSummationOptimization problemAbsolute valueRoundingSubdifferentialComputer animation
01:20:19
Network topologyMaxima and minimaSymplectic manifoldSymmetric matrixTravelling salesman problemLinear programmingGraph (mathematics)Variable (mathematics)Direction (geometry)CalculationObject (grammar)LengthOrder of magnitudeDecimalLokales SuchverfahrenGrand Unified TheoryZielfunktionBoom barrierSet (mathematics)Physical lawSearch algorithmStress (mechanics)Valuation using multiplesEigenvalues and eigenvectorsPhysical quantityMultiplicationComputer animation
01:29:22
Travelling salesman problemSymmetric matrixSymplectic manifold
Transcript: German(auto-generated)
00:01
präsentiert von OpenLearnWare, die Plattform für Lernmaterialien an der TU Darmstadt. So, hallo allerseits, ich darf Sie herzlich wie üblich begrüßen zu dieser Nachtschlafenden Zeit 9.50 Uhr. So, ich wollte noch mal ganz klar kurz einen Schritt zurückgehen auf eine Folie,
00:25
die wir, glaube ich, vorher übersprungen haben, Folie 32 oder jedenfalls nur sehr kurz angesprochen haben, weil sie noch mal wesentlich sein wird, als kleine Auffrischung wesentlich sein wird für das, was wir heute zu besprechen haben, für einzelne Punkte.
00:42
So, das Ganze ist hier etwas kompliziert oder etwas abstrakt formuliert. Was zunächst einmal hier steht, ist, Sie kennen lineare Gleichungssysteme aus der linearen Algebra A x gleich b. A x kleiner gleich b, das ist im Prinzip dasselbe.
01:07
Nur, dass sie nicht Gleichheit, sondern Ungleichheit haben, das heißt also, sie haben die Matrix A kürzlich wie üblich ab mit der Spaltenzahl m und der Zeilenzahl n.
01:31
Der Vektor, den Sie suchen, ist x1 bis xm. Gut, ich glaube, ich muss hier die Zeilen und die Spaltenzahl umtauschen, denn auf der Folie
01:44
steht nicht xm, sondern xn. Ne, doch ist richtig, Entschuldigung, die Zeilennummer, so wie jetzt, hier, das ist falsch, m1 und 1n, so.
02:06
Das ist jetzt komponentenweise kleiner gleich b1 bis bm, was nichts anderes bedeutet als für jedes i ist Summe aij, j gleich 1 bis n, mal xij gleich bi, für alle i aus 1 bis m.
02:39
Klein, eben nicht gleich, sondern kleiner gleich.
02:42
Wir werden gleich nochmal, behalten Sie das erst einmal im Kopf, wir werden gleich nochmal bei unserem Standardbeispiel TSP sehen, dass wir eine ganze Menge verschiedener Problemstellungen auf diese abstrakte Art und Weise formulieren können. Das ist ein wesentlicher Punkt, beispielsweise auch in der Veranstaltung algorithmische Modellierung
03:01
im nächsten Semester diverse Problemstellungen modellieren als so ein ILP. Warum macht man das? Weil man für diese abstrakte Darstellung, wenn man ein Problem so darstellen kann, dann gibt es Löser, mit denen man dieses Problem dann besser lösen kann, also man kann gut erwarten, dass auch relativ große Problemstellungen ganz gut damit gelöst werden können,
03:27
mit diesen Lösern, auch wenn es NP-schwere Probleme sind, ist man da schon sehr weit. So, das ist ein integer linear programming problem, so heißt, also das Wort programming hier ist eingeführt worden zu einer Zeit, als es noch keine Informatik gab, als man noch nicht von programmieren,
03:46
also als es noch nicht darum ging, Programme zu schreiben, so als man, als es darum ging, oder als man programming verstanden hat, als mathematische Probleme aus der Praxis zu lösen, mehr oder weniger variablen Werte zu finden.
04:01
So, das kann man sich so vorstellen, wie es hier rechts gezeichnet ist. Im zweidimensionalen, also stellen Sie sich vor, das x wäre zweidimensional, n wäre gleich 2, dann können Sie sich das so vorstellen, wie das hier rechts steht. Jede Ungleichung zerlegt den Gesamtraum in zwei Hälften.
04:23
Eine Hälfte gehört zum Lösungsraum, die andere Hälfte nicht, so dass dieser Lösungsraum schrittweise so ein konvexes Polygon wird, kann von allen Seiten beschränkt sein, dass die Bedingungen gerade so im Raum liegen, dass der Lösungsraum von allen Seiten beschränkt ist,
04:43
muss aber nicht, so wie es hier angedeutet ist, kann auch durchaus so sein, wenn die normalen Vektoren nicht in alle möglichen Richtungen gehen, sondern weniger als 180 Grad insgesamt, in einem Bereich von weniger als 180 Grad sind, dann öffnet sich das in eine Richtung, könnte sich sogar theoretisch in zwei Richtungen öffnen,
05:05
wenn Sie sich vorstellen, Sie haben zwei Bedingungen, die parallel zueinander sind, und die eine schneidet nach unten ab, die andere schneidet nach oben ab. Die Punkte hier drin, das ist die dritte Zeile hier, wir wollen ganzzahlige Lösungen haben, wir wollen nicht irgendwelche beliebigen, reellwertigen Lösungen haben,
05:26
sondern ganzzahlige Lösungen, das ist in der Regel in der Praxis das, was man will, dazu kommen wir dann auch gleich noch im Beispiel, und was wir wollen, das ist, wir wollen nicht einfach nur irgendeine zulässige Lösung finden,
05:42
was schon entweder schwer alleine ist, eine zulässige Lösung, unter der Bedingung a x kleiner gleich b x ganzzahlig zu finden, sondern wir wollen noch einen Schritt mehr, wir wollen eine lineare Zielfunktion, das kennen Sie, diese Formulierung aus der linearen Algebra,
06:06
c transponiert x ist dasselbe wie Summe i gleich 1 bis n c i mal x i, also c 1 mal x 1 plus c 2 mal x 2 plus und so weiter.
06:27
Das heißt, was Sie immer optimieren wollen, ist die gewichtete Summe der einzelnen variablen Werte. So, das ist zunächst mal noch ohne Zusammenhang zum Thema,
06:43
bei dem wir das letzte Mal stehen geblieben sind, aber der Zusammenhang, ich werde darauf dann heute zurückgreifen müssen, ich habe es an den Anfang gestellt, weil das Rumsuchen durchaus ein bisschen kompliziert und umfangreich ist. So, jetzt versuche ich an die richtige Stelle zu,
07:04
ne, habe natürlich gleich das falsche erwischt, hier, nein, das war jetzt, ich muss, so, keine Treffer, Mist, ich habe es,
07:23
vorher habe ich geschaut, ob ich es so finde, jetzt sagt er mir auf einmal keine Treffer, na gut, dann versuche ich doch irgendwie da hinzukommen, ich bin gar nicht so weit weggelandet, keine Ahnung, warum er mir jetzt keine Treffer sagt,
07:44
so, da wollte ich hin, so, die Folie haben wir beim letzten Mal schon gesehen. Worum geht das bei der ganzen Sache? Sie erinnern sich,
08:00
wir haben einen Baum, den ich wie üblich so zeichne, und die Wurzel repräsentiert die Instanz, wie sie gegeben ist, wir zerlegen den Lösungsraum in Gedanken, natürlich nicht in echt,
08:23
weil wir den Lösungsraum hier gar nicht in echt zur Verfügung haben, wir haben ihn ja nicht in der Hand, wir zerlegen ihn, indem wir einerseits eine Bedingung einfügen, kommen wir zum nächsten Knoten, und andererseits das Komplement dieser Bedingung einfügen, muss nicht binär sein, man kann es natürlich auch, man kann natürlich auch drei oder mehr Bedingungen einfügen,
08:44
die zusammen den gesamten Lösungsraum ergeben, also die so komplementär zueinander sind, aber im Allgemeinen betrachtet man binäre, binäre Zerlegung ist einfacher. So, und wir würden natürlich ungern den ganzen Baum durchsuchen müssen,
09:05
wir würden natürlich so oft wie möglich, wenn wir an einem Knoten sind, sagen können, es lohnt sich nicht, den Teilbaum unterhalb dieses Knotens zu durchsuchen, es lohnt sich deshalb nicht, weil wir von vornherein wissen,
09:23
dass entweder, dass da überhaupt keine zulässige Lösung drin ist, dass der Lösungsraum, wenn wir diese Bedingungen hinzunehmen, diese Bedingungen für diese Kante und diese Kante, dass dann plötzlich die Bedingungen überbestimmt werden, und wir plötzlich einen leeren Lösungsraum haben, was wir natürlich erstmal nicht sehen, weil wir den Lösungsraum nicht in der Hand haben,
09:43
oder dass wir sagen können, naja, das ist jetzt das Konzept von Branchen bound, wir haben schon mal irgendwo anders eine Lösung gesehen, und wir wissen definitiv, was immer es hier an zulässigen Lösungen gibt, wird nicht besser sein als die hier, die wir schon gesehen haben.
10:02
Wenn wir das wissen, dann können wir ohne Beschränkung der Allgemeinheit, können wir einfach, ohne schlechtes Gewissen, an dieser Stelle aufhören mit dem Weiter runtergehen im Baum und können diesen ganzen Teilbaum abschneiden, können ihn ignorieren. Und wir haben auch schon beim letzten Mal betrachtet, wie wir das bei Branchen bound wissen,
10:22
wir haben eine obere Schranke, das ist am Anfang irgendein geeignet gewählter Wert, aber so wie wir das erste Mal in unserer tiefen Suchartigen Suche zu einer Lösung kommen, zu einer zulässigen Lösung kommen, gibt uns das natürlich eine obere Schranke für den Optimalwert.
10:41
Jeder Wert einer zulässigen Lösung ist eine obere Schranke für den Optimalwert der Lösung. Wenn wir bei einem Minimierungsproblem sind, wir hatten von Anfang an gesagt, in diesem Abschnitt betrachten wir Minimierungsprobleme, Maximierungsprobleme sind spiegelsymmetrisch, es reicht, wenn wir uns Minimierungsprobleme ansehen.
11:03
So, und auf der anderen Seite, wenn es uns gelingt, für diesen Teilbaum hier eine untere Schranke für die Werte, für die Zielfunktionswerte aller zulässigen Lösungen zu berechnen, und wenn wir dann feststellen, dass diese untere Schranke,
11:25
das ist auf der Folie, wenn wir feststellen, dass diese untere Schranke für alle zulässigen Lösungen, für alle Zielfunktionswerte von zulässigen Lösungen in diesem Teilbaum sind, wenn die größer ist als die obere Schranke, die wir schon haben,
11:42
dann wissen wir definitiv, wir können an dieser Stelle Schluss machen mit diesem Teilbaum, wir können woanders weitersuchen. Das ist die Grundidee von Branchenbound, wie wir sie beim letzten Mal schon betrachtet haben. Die anderen Fälle hier sind Spezialfälle,
12:01
die man natürlich auch noch betrachten muss. Wenn wir eine untere Schranke haben, die plusunendlich ist, wenn wir das rauskriegen, dann wissen wir, dass der gesamte Teilbaum infeasible, also er enthält keine zulässigen Lösungen, weil jede zulässige Lösung hat einen endlichen Zielfunktionswert und der kann nicht größer gleich der untere Schranke plusunendlich sein.
12:24
Also wenn wir plusunendlich rausbekommen, dann ist der Teilbaum, enthält der Teilbaum keine zulässigen Lösungen sein, seine Einschränkungen, die zugehörige Einschränkung des Lösungsraums ist die leere Menge. Und gut, das hatten wir alle schon betrachtet.
12:41
Wie wir mit der oberen Schranke umgehen, das haben wir letztes Mal auch schon betrachtet. Jetzt kommen wir zu diesen unteren Schranken. Wie kriegen wir das hin? Für den Knoten V, wie wir ihn eben auf der in den letzten Folien genannt haben, eine untere Schranke L von V zu bestimmen,
13:00
die wir testen können gegen die obere Schranke. Die obere Schranke zu bestimmen, das haben wir letztes Mal betrachtet, das ist eine einfache Sache. Wann immer wir eine Lösung, eine zulässige Lösung besuchen, also einen Blatt in diesem Baum, die besser ist als die bisherige gespeicherte obere Schranke U,
13:21
dann setzen wir U auf den Wert dieser neu gefundenen zulässigen Lösung. Die Grundidee hier ist umschrieben mit dem Fachbegriff Relaxierung. Relaxation im Englischen. So, worum geht das? Das haben wir schon betrachtet.
13:43
Ach so, ich gehe zurück. Ich habe mich schon gewundert, warum es jetzt nicht mit Relaxierung weitergeht. Kein Wunder, wenn ich in die falsche Richtung gehe. So, das ist jetzt alles ziemlich abstrakt. Wir kommen dahin zurück. Oder nee, wir bleiben hier. Ich hatte beim letzten Mal schon ein Beispiel genannt.
14:03
Wenn Sie beim TSP die Bedingung relaxieren,
14:22
dass es eine Rundtour ist, die alle Knoten umfasst, und wenn Sie zulassen, wenn Sie den Lösungsraum erweitern, um alle Gebilde wie diese, das heißt also, jeder Knoten ist in einer Rundtour drin, aber nicht jeder Knoten ist in derselben Rundtour drin, dann haben Sie eine Relaxierung in diesem Sinne,
14:43
nämlich im obigen Sinne, Sie haben, oder nee, hier in diesem Sinne, hier von diesem Punkt, Sie haben den Lösungsraum X durch einen erweiterten, vergrößerten Lösungsraum T ersetzt.
15:02
Ja, der erweiterte Lösungsraum, der enthält auch Konfigurationen wie diese, die im ursprünglichen Lösungsraum fürs TSP natürlich nicht drin sind. Das ist ja keine Rundtour. So, das heißt also, wir haben das ursprüngliche Problem. Wir wollen eine Zielfunktion minimieren. Bei der Rundtour wissen Sie, was die Zielfunktion ist. Das ist die Summe der Kantengewichte derjenigen Kanten,
15:24
die in der Rundtour drin sind. Groß X ist der Lösungsraum, ist die Menge aller Rundtouren. Relaxiert heißt, wir haben zunächst einmal die Kostenfunktion gleich gelassen. Also dieser zweite Fall, den betrachten wir noch gleich, aber wir haben den Lösungsraum erweitert.
15:40
So, wenn wir, der entscheidende Punkt ist der, das werden wir jetzt hier nicht genauer betrachten, aber der entscheidende Punkt ist der, dass diese Problemstellung viel einfacher und effizienter zu lösen ist als die ursprüngliche Problemstellung. So, und weil das eine Relaxierung ist,
16:02
weil eben die Rundtouren selber ebenfalls im Lösungsraum drin sind, ist das noch alles drauf? Okay, weil die Rundtouren selber ebenfalls noch in diesem Lösungsraum drin sind, aber noch zusätzliche Lösungen hinzugekommen sind, ist das optimale Ergebnis, was wir hier raus bekommen können,
16:25
was vermutlich, so wie es gezeichnet habe, das hier tatsächlich ist, ist das eine untere Schranke für die optimale Rundtour. Also es kann, je nach, achso, ich habe das jetzt hier, so passt es zusammen.
16:43
Es kann zufällig tatsächlich so sein, dass eine Rundtour das optimale Ergebnis ist. Wenn die eng beieinander sind, die drei Punkte, und wenn die drei Punkte eng beieinander sind, ist die Rundtour wahrscheinlich das optimale Ergebnis.
17:00
Wenn Sie sich aber vorstellen, diese Kanten wären jetzt jeweils eine Million Kilometer lang, nein, die beiden Kanten wären jeweils eine Million Kilometer lang, das wäre so auseinander getrieben, dann wird vermutlich das hier die optimale Lösung sein. Im Einzelfall kann es passieren, dass Sie tatsächlich hier eine optimale Lösung bekommen oder auch nicht.
17:28
So, wir sind aber hier noch nicht fertig an dieser Stelle mit der Erklärung. Sie sollten noch etwas vermissen bei dieser Erklärung, nämlich wir haben hier noch zusätzliche Bedingungen.
17:44
Wir haben hier die Bedingung zum Beispiel, dass irgendeine bestimmte Kante drin sein soll, nach links, wir können es ja vielleicht vereinbaren, nach links gezeichnet, bedeutet, die Kante, die wir auf dieser Ebene betrachten, gehört dazu. Die erste Kante, die wir betrachten,
18:01
und dementsprechend bedeutet dieser Fall, dieselbe Kante gehört nicht dazu zur Lösung, sodass wir also den Lösungsraum in zwei Teilmengen partitioniert haben. Die linke Teilmenge, darin sind alle zulässigen Lösungen aller Rundtouren, die diese Kante enthalten, die rechte Teilmenge, alle zulässigen Lösungen, die diese Kante nicht enthalten.
18:20
Und Sie sehen schon vielleicht dabei, man kann schon eine ganze Menge abschneiden hier, allein schon dadurch, dass es keine Subtouren geben darf. Wenn die drei Kanten, die alle drei drin sein sollen, eine Subtour ergeben,
18:40
dann kann ich an dieser Stelle schon abschneiden, weil eine Subtour lässt sich natürlich nicht zu einer Rundtour erweitern mehr. So, das war nur nebenher gesagt. Hier haben wir eine zweite Kante und wir sagen an dieser Stelle im Baum, diese Kante gehört dazu und diese Kante gehört nicht dazu. Das heißt, was wir eigentlich haben, ist nicht einfach nur die Problemstellung,
19:02
gegeben diese Punkte mit diesen Abständen, wir wollen eine, einen Gebilde wie dieses mit möglichst wenig Kantengewichten haben, sondern noch einen Schritt weiter. Wir wollen, dass eine bestimmte Kante drin ist, zum Beispiel wäre es sie gewesen. Und wir wollen, nehmen wir mal die, dass eine bestimmte Kante nicht drin ist, zum Beispiel wäre es sie gewesen.
19:25
Und darauf will ich jetzt nicht hier an dieser Stelle weiter eingehen. Auch mit dieser Einschränkung, dass wir also nicht nur Punkte und ihre Distanzen gegeben haben, sondern auch eine Liste von Kanten, die drin sein müssen und eine Liste von Kanten, die nicht drin sein dürfen.
19:42
Auch mit dieser Einschränkung ist diese Problemstellung hier immer noch sehr effizient lösbar. Sie erinnern sich vielleicht an das Matching-Problem, wo es, wo die Aufgabe daran bestand, eine Kantenmenge zu finden, sodass jeder Knoten mit maximal einer Kante in Berührung ist.
20:01
Das ist hier eine Variation des Matching-Problems, nämlich die Forderung, dass jeder Knoten mit genau zwei Kanten in Berührung ist. Und mit ähnlichen Techniken für das Matching-Problem lässt sich auch diese Problemstellung lösen, aber das ist jenseits dieser Vorlesung. Den anderen Fall, warum haben wir das gemacht?
20:26
Warum haben wir die Relaxierung so getroffen, dass wir von Rundtouren zu solchen Gebilden übergegangen sind, die wir als Lösungsraum. Das haben wir deshalb gemacht, weil diese Bedingung,
20:40
dass alle Knoten in einer Rundtour sein sollen, diese Bedingung macht uns das Problem extrem komplex, extrem kompliziert, macht uns richtig bösen Ärger. Und deshalb macht es Sinn, diese Bedingung zu relaxieren und dann hier bei jedem Knoten für Berechnung der unteren Schranke
21:05
mit den einzelnen, damit da eine Optimallösung zu finden. Es gibt auch den anderen Fall, der ist, das werden wir dann noch sehen, der ist dafür da, falls die Problematik, die Komplexität der Problemstellung
21:20
nicht in den Nebenbedingungen drin ist, die wir beim Übergang zur Relaxierung fallen lassen oder relaxieren, sondern die Komplexität könnte auch in der Zielfunktion drin sein, dass die Zielfunktion sehr unübersichtlich ist und dass wir übergehen zu einer Zielfunktion,
21:41
die sehr viel einfacher gestrukturiert ist und deshalb sehr viel einfacher behandelbar ist. Das ist hier nicht der Fall beim DSP. Die Zielfunktion ist einfach das und ich sage es mal salopp, einfacher geht es eigentlich gar nicht. Was Einfaches kann man nicht erwarten. Deshalb haben wir hier an der Zielfunktion nichts gedreht, sondern an der Lösungsmenge.
22:01
So, was wissen wir? Wir wissen, bei einer Relaxierung ist der Optimalwert der Relaxierung höchstens so groß bei einem Minimierungsproblem wie der originale Optimalwert. Das heißt, es ist eine untere Schranke. Vielleicht nochmal hier dazu zu beachten.
22:22
Hier steht die neue Zielfunktion. Wenn wir tatsächlich die Komplexität in der Zielfunktion haben und diese durch Übergang zu einer einfachen Zielfunktion rausschmeißen, dann, damit das Ganze funktioniert, damit es eine untere Schranke gibt, müssen wir natürlich fordern, dass wir in eine bestimmte Richtung vereinfachen, nämlich so, dass die neue Zielfunktion für jedes Element des Lösungsraums
22:45
höchstens so groß ist, wie der alte Zielfunktionswert. Wenn das der Fall ist, dann ist das auf jeden Fall eine untere Schranke. So, auch die Problemstellung überhaupt eine zulässige Lösung zu finden,
23:00
ist häufig NP-schwer. Und wenn die Relaxierung einfacher zu lösen ist, dann ist es natürlich auch einfacher festzustellen, insbesondere, ob dieser Erweiter-Lösungsraum leer ist.
23:21
Und wenn der auch schon leer ist, dann ist natürlich der originale Lösungsraum, der eine Teilmenge davon ist, erst recht leer. Das heißt, auch da, wenn wir feststellen, das ist das, was ich hier angedeutet habe, wenn Sie hier bei diesem Knoten hingekommen sind, dass Sie gesagt haben, zuerst diese Kante 1, die muss drin sein,
23:43
diese Kante 2 muss drin sein, diese Kante 3 muss drin sein, dann wissen Sie, der Lösungsraum dieses Knotens hier ist leer. Denn es gibt keine Möglichkeit, diese Menge von drei ausgewählten Kanten
24:01
zu einer Rundtour, also zu sowas, zu erweitern. So, noch ein letzter Punkt. Falls wir zufällig tatsächlich als optimale Lösung sowas rauskriegen und nicht sowas,
24:25
dann haben wir sogar noch mehr Glück gehabt. Wir haben nicht nur das Glück gehabt, dass wir tatsächlich eine untere Schranke in die Hand bekommen haben, die greift, wo diese Bedingung U kleiner L von V tatsächlich erfüllt ist, sondern wir haben sogar noch mehr. Wir haben tatsächlich eine optimale Lösung innerhalb dieses Teilbaums
24:45
in die Hand bekommen. Denn wenn eine optimale Lösung der Relaxierung zum Ursprungsproblem, zur ursprünglichen Lösungsmenge gehört, dann ist sie auch optimal hier.
25:02
So, jetzt kommen wir hier zu dem, womit ich heute angefangen habe. Eine Möglichkeit, sie ändern sich. Das waren jetzt Matrizenbedingungen. Habe ich das noch hier? Ich habe noch nichts heute gewischt. Sie ändern sich. Der Lösungsraum wird beschrieben durch zwei Sätze von Bedingungen.
25:25
Der eine Satz steht hier. Und der zweite Satz ist, dass X ganzzahlig sein soll. Und diese Bedingung, Ganzzahligkeit, macht das Problem sehr viel schwerer.
25:43
Das will ich versuchen, kurz anschaulich zu skizzieren, warum dieser zweite Satz, dieser gerade unscheinbare Satz von Bedingungen hier, so in aller Welt Bedingungen, ganze Zahlen und nicht reelle Zahlen, warum das plötzlich die Problemstellung sehr viel komplizierter macht.
26:47
Ups, das ist noch nicht richtig trocken. So, warum sieht das so aus? Sie ändern sich an das Bild, was wir eben hatten.
27:04
Wir haben vielleicht ein zweidimensionales Koordinatensystem. Aus Gründen, die ich hier nicht näher erläutern muss, kann ich ihn nicht mehr als zwei Dimensionen anbieten hier. Und sie haben die Bedingungen,
27:24
die vielleicht tatsächlich von allen Seiten jetzt hier diese Fläche in der Mitte zum Lösungsraum machen. Bedingungen, die tatsächlich von allen Seiten Halbräume abschneiden, sodass ein endliches, beschränktes Polygon übrig bleibt.
27:45
Vielleicht nur, wie könnte man sich das vorstellen, im Dreidimensionalen? Mein Lieblingsbeispiel, an dem ich mir das immer vorstelle, sieht so aus. So ein schöner Diamant.
28:03
Stellen Sie sich vor, Sie schleifen einen Edelstein, so wie man das kennt. Dann kommen von allen Seiten so ein bisschen mal Facetten abgeschliffen. Dann kommt im Dreidimensionalen das entsprechende raus. Sie haben dann dreidimensionale Halbräume, die Sie von allen Seiten abschneiden.
28:23
So muss das ungefähr sein. Ich bin nicht ganz gut dran, wie Sie sehen, sowas zu zeichnen. So, der Standard-Algorithmus, also in irgendeine Richtung geht jetzt,
28:40
wir haben irgendeine Richtung, in die es immer besser wird. Egal welche, zum Beispiel in die. Das hängt von dem Vektor C ab, in welche Richtung das geht. Genauso gesagt ist das sogar der Vektor C. Oder beim Minimus-Problem das Negative von C. So, dann können Sie hier schon mal grafisch eine wesentliche Erkenntnis ableiten.
29:02
Natürlich jetzt nicht als strenger mathematischer Beweis, aber es gibt auch einen strengen mathematischen Beweis dafür, dass das Optimum mindestens immer in irgendeiner Ecke angenommen wird. Also wenn hier zum Beispiel die Richtung ist, wo es immer besser wird, wird das Optimum in dieser Ecke angenommen. Kann auch, je nachdem wie der Gradient liegt,
29:21
kann es auch zufällig gerade so sein, wenn der Senkrecht zu einer Facette ist, dass hier die ganze Facette optimal ist, aber wir wissen, es ist mindestens ein Punkt einer Ecke, bei der das Optimum angenommen wird. So, und der Standard-Algorithmus geht so fort, dass er irgendwo anfängt mit irgendeiner Ecke
29:42
und sich dann von einer Ecke zu einer benachbarten Ecke hangelt, immer in Richtung besser werdend, immer in Richtung Verbesserung der Lösung. Also ein Algorithmus, im Grunde ein lokaler Suchalgorithmus.
30:01
Sie haben eine Nachbarschaft auf den Ecken hier durch eine Kante verbunden und sie gehen immer in Richtung Verbesserung und man kann beweisen, dass sie damit automatisch irgendwann bei der optimalen Ecke ankommen. Genauso hier, wenn sie Pech haben, fangen sie genau an der verkehrten Seite an,
30:23
sodass sie also einen langen Weg haben, gehen zu einer benachbarten Ecke, zu einer benachbarten, benachbarten, benachbarten und man kann auch beweisen, egal wie, wenn sie nur immer in Richtung Verbesserung gehen, dann kommen sie irgendwann zur optimalen Ecke an. Das funktioniert aber nur, solange sie nicht Ganzzahligkeit noch als Bedingung dabei haben.
30:48
Dann können sie so mit diesem Algorithmus, der nennt sich Simplex-Algorithmus, schreib ich vielleicht mal dazu, falls es Sie da weiter interessiert. In der Mathematik gibt es Lehrveranstaltungen, die diese Thematik vertiefen.
31:04
Das machen wir jetzt hier in Informatik nicht. Und wenn sie aber Ganzzahligkeit haben, dann muss die Lösung einer der Punkte von diesem Ganzzahligkeitsgitter sein.
31:26
Und damit im Allgemeinen nicht mehr eine Ecke. So, jetzt könnte man natürlich sagen, es ist doch kein Problem, wir gehen zur nächsten Ecke und gucken uns da an, was ist da so in der Nähe an ganzzahligen Lösungen?
31:42
Kein Problem, eine von denen wird schon die optimale ganzzahlige Lösung sein. Aber ganz so einfach ist es nicht, wenn Sie sich beispielsweise Folgendes vorstellen, dass Sie hier eine sehr, vielleicht noch exzentrischer, dass Sie hier, wo es optimal wird, dass Sie hier eine sehr spitz zu laufende Ecke haben
32:05
und alles was in der Nachbarschaft an ganzzahligen Lösungen ist, ist erst einmal nicht drin. Die nächste Reihe ist vielleicht auch nicht drin. Und Sie stellen sich vor, Sie haben jetzt nicht zweidimensional,
32:20
sondern Sie haben N-dimensional. Das heißt also, Sie haben nicht zwei Quadratpunkte drum herum, sondern zwei hoch N-Punkte drum herum und entsprechend immer mehr. Und hier unten irgendwo ist die erste ganzzahlige Lösung, die im Lösungsraum drin ist.
32:41
Dann sehen Sie schon, die zu finden, das ist nicht so einfach. Ja, also einfach die optimale nicht ganzzahlige Lösung, diese Ecke zu finden und dann in der Umgebung rumzusuchen, ist ein guter Lösungsansatz, wird auch häufig gemacht, funktioniert aber nicht immer bei schlecht gestellten Problemen wie hier,
33:01
wo die einzelnen Nebenbedingungen sehr nah beieinander liegen, also fast parallel zueinander sind, funktioniert es nicht mehr gut. So, aber für uns hier ausreichend, wenn die Problemstellung ein ILP ist,
33:27
dann können wir zur LP-Relaxation übergehen, lass mich mal hier, können wir zur LP-Relaxation übergehen, indem wir die Ganzzahligkeitsbedingungen fallen lassen. Das gibt uns eine Relaxierung,
33:45
das heißt also, wenn wir die lösen, so wie ich das eben skizziert habe, mit dem Simplex-Algorithmus von Ecke zu Ecke hoppeln, das gibt uns eine Lösung, die mit Sicherheit eine untere Schranke ist für die ursprüngliche Problemstellung, denn wir haben den Lösungsraum erweitert, indem wir übergegangen sind
34:03
von ganzzahligen Lösungen auf beliebige, reellwertige Lösungen. So, das Beispiel hatten wir eben. Sie sehen jetzt hier nochmal, habe ich das jetzt gelöscht?
34:22
Ja, ich mal es nochmal auf. Das ist genau das, was wir eben betrachtet hatten.
34:51
Sie erinnern sich, TSP. So, wenn das weit genug weg ist, ist das sicherlich die optimale Lösung und die Rundtour,
35:01
und die beste Rundtour darauf ist wahrscheinlich nicht mehr die optimale Lösung. Ich muss mir angewöhnen, nicht jedes Mal, wenn ich hier herkomme, die ganzen Kreide hier rüber zu bringen.
35:25
So, was dann übrig bleibt, Sie sehen plötzlich, dass letztlich tatsächlich, als ein ILP schreiben, wir minimieren die Kosten. Für jede Kante haben wir ein 0,1 Vektor.
35:40
Was heißt 0,1? Das heißt, xe ist kleiner gleich 1, lineare Bedingung, lineare Ungleichung. xe ist größer gleich 0, lineare Ungleichung, und xe ist Element aus z.
36:01
Das alles drei zusammen ist Äquivalenz zu xe ist aus 0,1. Ja, das heißt also, zu sagen, xe ist aus 0,1, xe ist Teil eines ILP.
36:27
Und die Bedingung, dass wir so ein Gebilde haben, lässt sich sehr einfach ausdrücken. Was bedeutet das nämlich? Das bedeutet, dass jeder einzelne Knoten genau incident zu zwei, exakt zwei Kanten ist.
36:42
Wenn Sie diese Forderung haben, wie Sie da sehen, für jeden Knoten sollen die xe der Kanten, ich habe das vielleicht noch nicht ganz genau gesagt,
37:01
xe gleich 1 bedeutet natürlich, die Kante ist drin, und xe gleich 0 bedeutet, die Kante ist nicht drin. So, wenn Sie jetzt diese Semantik haben, xe bedeutet, die Kante ist drin in der Lösung, xe gleich 1, xe gleich 0 bedeutet, die Kante ist nicht drin,
37:22
dann lässt sich die Kosten eines solchen Gebildes einfach durch Aufsummierung der einzelnen Kantenkosten von den Kanten, die drin sind, bewerkstelligen. Und das ist ganz einfach, wir gehen über alle Kanten,
37:42
und wenn eine Kante drin ist, dann steht hier eine 1, das heißt, deren Kosten kommen mit in die Summe rein, und wenn eine Kante nicht drin ist, dann steht hier eine 0, das heißt, die Kosten dieser Kante kommen nicht rein. Was wir im Endeffekt hier oben haben, ist die Summe der Kosten aller Kanten, die in der Runde enthalten sind.
38:02
So, das ist das Erste, jetzt müssen wir nun dafür sorgen, dass diese 0,1 Werte für xe tatsächlich ein solches Gebilde ergeben, und sie ergeben ein solches Gebilde durch diese Forderung, für jeden Knoten soll gelten, die incidenten Kanten,
38:20
wir summieren hier über alle zu diesem Knoten incidenten Kanten auf, diejenigen incidenten Kanten, die zu diesem Knoten incident sind, deren x-Werte sollen in Summe 2 sein, die x-Werte sind aber alles 0,1 Werte, wie kann es sein, dass eine Summe von 0,1 Werten genau den Wert 2 hat?
38:41
Das kann nur dadurch sein, dass genau 2 dieser x-Werte den Wert 1 haben und alle anderen 0. Mit anderen Worten, dass genau zwei Kanten, die incident zu diesem Knoten sind, in diesem Gebilde enthalten sind und die anderen nicht.
39:01
Und das geht, wie gesagt, in sehr schneller Zeit. Sie sehen hier ein erstes Beispiel dafür, wie mächtig ILP als Sprache ist, nämlich dass man solche Dinge einfach mal so schnell als Bedingungen hinschreiben kann.
39:23
Das ist der Grund, warum wir uns in der Algorithmische Modellierung so intensiv damit befassen, weil es auf der einen Seite sehr gute Löser dafür gibt, auf der anderen Seite ist diese Sprache so mächtig, dass diverse Problemstellungen, die wir hier betrachtet haben, eigentlich alle Problemstellungen, die wir hier betrachtet haben, sich in guter Form in dieser Sprache beschreiben lassen
39:42
und damit mit diesen Lösern gelöst werden können. So, ein anderes Beispiel, TSP. Was ist ein 1-Baum? Das ist auch eine Relaxierung von Runtour. Sie haben wieder die Knotenmenge gegeben.
40:10
Die Punkte in der Ebene zum Beispiel. Das müssen keine Punkte in der Ebene sein, können irgendwelche abstrakten Gebilde sein, das haben wir ja besprochen gehabt.
40:45
So, das wäre in unserem Standardbeispiel, was wir jetzt immer benutzt haben, die optimale Runtour wahrscheinlich. Und ein 1-Baum ist etwas, Sie wissen, was ein Baum ist im ungerichteten Sinne,
41:03
im Sinne von minimal spannender Baum. Das ist ein ungerichteter Graf, der ist zusammenhängt und hat keine Zückel. Wir lernen sich dunkel an dieses Thema aus der GDI 2. Ein 1-Baum ist im Prinzip ein Baum,
41:21
der noch eine Kante mehr enthält, sodass sich genau ein Zückel schließt. Also zusammenhängt und enthält genau einen Zückel. Das wäre beispielsweise hier, könnte der Zückel so aussehen. Und hier, wenn wir es ein bisschen länger machen,
41:44
wenn wir es ein bisschen weiter wegtreiben, so, hier ist der nächste, dann ist wahrscheinlich das hier der optimale 1-Baum. Ja, wir zählen wieder die Kantengewichte auf, wir summieren die Kantengewichte auf, der Einfachheit halber die euklidischen Längen hier an der Tafel.
42:13
Und Sie sehen, das ist eine Relaxierung, denn die ursprüngliche Rundtour,
42:22
jede Rundtour ist offensichtlich ein 1-Baum. Nämlich ein 1-Baum, wo da nichts weiter dranhängt. Wir können das vielleicht noch ein bisschen erweitern, damit das noch mal klarer wird, dass nicht nur eine Sache da dran hängen muss, sondern es könnte zum Beispiel auch sein, dass hier noch was dranhängt, so.
42:47
Das würde dann hier aussehen, es könnte so aussehen, weiterhin so, und dann so. Wie wäre das optimal? Wahrscheinlich so auch.
43:03
Oder nee, optimal wäre es wahrscheinlich so. So, jetzt haben wir das Beispiel ein bisschen komplizierter gemacht, damit Sie sehen, dass das nicht nur an einer Stelle da irgendwas dranhängt, was keinen Zykkel enthält, sondern durchaus an verschiedenen Stellen da beliebige Verästelungen geben kann.
43:20
So, jede Rundtour ist ein 1-Baum, nämlich dann, wenn hier nichts weiter dranhängt, sondern alles im Zykkel enthalten ist, alle Knoten. Aber nicht jeder 1-Baum ist eine Rundtour, das heißt, wir haben eine Vereinfachung, wir haben eine Relaxierung, Entschuldigung, und wir werden das später in einem anderen Thema genauer betrachten,
43:43
sondern hier auch wieder vorhersagen. Diese rechte Problemstellung, einen optimalen 1-Baum zu finden, ist viel, viel einfacher zu lösen als die linke Problemstellung. Auch dann wieder, Sie erinnern sich,
44:01
wenn wir eine Liste von Kanten haben, wo vorgegeben ist, die muss drin sein, die muss drin sein, die muss drin sein, und wo wir eine weitere Liste von Kanten haben vorgegeben, die darf nicht drin sein, die darf nicht drin sein, die darf nicht drin sein.
44:22
Auch dann ist diese Problemstellung immer noch sehr effizient lösbar. Das werden wir aber später genauer betrachten, wenn wir zu den Lösungsalgorithmen dafür kommen, wie man das lösen kann. So, jetzt sind wir weiterhin in der Welt der linearen Algebra.
44:48
Kommen wir zu einem sehr, sehr wichtigen Thema, was so ein bisschen eins der Arbeitsferde beispielsweise auch in der nicht ganz zahligen Optimierung ist, also im technischen Bereich, wenn Sie typischerweise mit reellwertigen Kenngrößen zu tun haben
45:01
und nicht unbedingt mit ganz zahligen Kenngrößen. Ja, wenn Sie irgendwelche Eigenschaften an einem Bauteil beispielsweise optimieren wollen, Wärmekoeffizienzen oder was auch immer, nur als ein einfaches Beispiel für viele, viele ingenieursmäßige Anwendungen.
45:22
So, wir haben jetzt eine etwas andere Situation als Ausgangspunkt, macht aber nichts. Das ist alles äquivalent zueinander. Wir minimieren wieder eine lineare Zielfunktion über einem linearen Gleichungssystem. Ein linearer Gleichungssystem oder ein linearer Ungleichungssystem ist vollkommen wurscht.
45:42
Jedes linearer Gleichungssystem besteht natürlich aus zwei linearen Ungleichungssystemen, weil jede Gleichung oder ein doppelt so großes lineares Ungleichungssystem, weil Sie ja jede Gleichung durch zwei Ungleichungen ersetzen können. x kleiner gleich y und x größer gleich y ergibt zusammen x gleich y. Und umgekehrt können Sie auch lineare Ungleichungssysteme in lineare Gleichungssysteme überführen,
46:09
indem Sie noch eine zusätzliche Dummyvariable jeweils einführen, die den Unterschied von kleiner gleich auf gleich aufnimmt. Aber gut, wir haben so eine Situation.
46:20
Wir haben irgendwelche linearen Gleichungen. Sie erinnern sich zum Beispiel, hier hatten wir solche linearen Gleichungen. Das ist ein Beispiel für lineare Gleichungen in so einem Kontextoptimierung. Und wir haben noch irgendwelche weiteren Bedingungen. Zum Beispiel, dass es ein Rundtour sein soll. Zum Beispiel TSP mit zusätzlichen linearen Gleichungen,
46:40
die von jedem Element des Lösungsraums erfüllt sein müssen. Sonst ist es kein Element des Lösungsraums. Wäre denkbar. So, was ist jetzt die Idee? Die Idee ist, wir schmeißen diese Bedingungen raus. Ja, also wir hätten jetzt hier beispielsweise diese Bedingungen rausgeschmissen,
47:04
wenn wir bei dem Beispiel bleiben. Aber nicht ersatzlos, so wie bisher. Bisher haben wir Bedingungen ersatzlos rausgeschmissen. Oder nicht ersatzlos rausgeschmissen, sondern relaxiert von hier nach hier.
47:21
Aus dieser Bedingung eine einfache Hand zu haben, wenn auch komplizierter aussehende Bedingung gemacht. Sondern wir nehmen die Bedingungen, die wir weggeschmissen haben, raus und aus dem Bedingungssatz und packen sie auf geeignete Art und Weise in die Zielfunktion.
47:49
So, was passiert hier? Also Sie sehen an den Namen Lagrange, dass das eine relativ alte und eine relativ wichtige Sache ist. Das ist Ihnen vielleicht in der Analysis, in der Mathematik schon mal begegnet.
48:01
Der Name Lagrange, Lagrange-Multiplikatoren, vielleicht im Zusammenhang mit dem Satz über implizite Funktionen, falls der Ihnen was sagt. Sagt Ihnen das Satz über implizite Funktionen was? Spontan nicht. Ist jetzt hier in diesem Kontext auch nicht so wichtig.
48:20
Also falls es Sie interessiert. Der Satz über implizite Funktionen besagt, wenn Sie eine Funktion haben in X und Y, zum Beispiel sowas, und Sie können die nicht auflösen nach einem Y, nach einem X,
48:41
weil Sie zum Beispiel so eine Kurve beschreibt. Dann können Sie weder nach X noch nach Y auflösen, wenn hier X und hier Y ist. An diesen Stellen gibt es Probleme mit Auflösen nach Y und an diesen Stellen hier gibt es Probleme mit Auflösen nach X. Aber der Satz besagt, wenn Sie an irgendeiner Stelle Differenzierbarkeit haben,
49:06
dann können Sie zum Beispiel sowas wie X² plus Y² gleich R, die Kreisgleichung, dann können Sie einfach differenzieren, wie Sie das immer gewöhnt sind nach X und Y,
49:21
ohne dass Sie es erst nach dem anderen auflösen müssen. Das besagte Satz über implizite Funktionen. Sie dürfen auch dann differenzieren, wenn Sie es gar nicht als eine Funktion ausdrücken können. Von einer Variablen in die anderen Variablen. Und in dem Zusammenhang, falls dieser Zusammenhang Ihnen doch nochmal unterkommt
49:43
oder falls Sie sich daran erinnern, dass es vielleicht doch in der Mathematik vorkommen kann, weiß ich jetzt nicht. In dem Zusammenhang führt man auch in der Analysis typischerweise Lagrange-Multiplikatoren ein, weil Aussagen darüber auf dem Satz über implizite Funktionen beruhen.
50:00
Gut, aber das ist jetzt alles für uns hier nicht weiter wesentlich. Das war nur ein kurzer Exkurs. Das ist jetzt die neue Zielfunktion. Was wir hier stehen haben, ich glaube, das müssen wir mal auseinanderfädeln.
50:23
Übrigens kann ich mich mal erinnern, bei einer Professur in Mathematik, wo ich in der Berufungskommission war, war als Vorgabe eine Lehrprobe, eine Viertelstunde didaktischer Aufbereitung, Einführung in den Satz über implizite Funktionen.
50:42
Und ich sage nur dazu, wenn Sie den Satz lesen in einem Analysisbuch, sieht das ganz anders aus, als wie ich das jetzt hier versucht habe aufzubereiten. Also allein der Satz in dem Buch, in nachdem ich damals Analysis gelernt habe, allein die Formulierung des Satzes nahm da eine halbe Seite ein.
51:01
Also durchaus ein gutes Thema, um die didaktischen Qualitäten eines Dozenten mal zu überprüfen.
51:53
So, ursprünglich steht da c t x gleich c 1 x 1 plus c 2 x 2 plus und c n x n.
52:06
Vielleicht noch mal kurz zusammengefasst, i gleich 1 bis n c i x i. So, jetzt steht da etwas komplizierteres. Wenn ich das hernehme, c t x plus lambda transponiert a x minus b.
52:34
Jetzt muss ich mal nachdenken. Ich glaube, hier ist eine Ungeschicklichkeit in der Folie.
52:41
Hier sollte nicht a x gleich b stehen, sondern hier sollte tatsächlich a x kleiner gleich b stehen, auf dieser Folie hier. Sonst macht das nämlich weitere, was ich jetzt hier sage, keinen Sinn. Tut mir leid. Also ich bin nicht derjenige, der die Folie verzapft hat,
53:00
aber ich bin natürlich verantwortlich für die Folie, wenn ich sie hier präsentiere. So, dann haben wir hier weiterhin, das kürze ich mal ab, c t x plus, was steht jetzt hier? Ich hoffe, dass ich das jetzt hinkriege. Lambda 1 mal Summe j gleich 1 oder i, nehme ich wieder i,
53:29
i gleich 1 bis n a 1 j x j minus b 1.
53:43
Ja, das ist die, was hier immer steht, ist lambda i mal a i 1, dieser Vektor a i n, mal x 1 bis x n.
54:04
Diese Zeile der Matrix multipliziert mit diesem Vektor. Und das Ganze noch natürlich hier die rechte Seite davon weggenommen. Halt, ich habe hier jetzt i genommen, dann sollte ich zur Unterscheidung hier,
54:20
dass es nicht dasselbe i ist, ein j hinschreiben. So, also das Plus, dasselbe noch mal für 2, Summe i gleich 1 bis n a 2 i mal x i minus b 2
54:46
und so weiter, bis wir das Ganze noch mal bei Lambda m haben, mal Summe i gleich 1 bis n a m i mal x i minus b m.
55:04
So, was bedeutet das? Die Lambda-Werte steht jetzt hier nicht direkt da, ist aber trotzdem so, die Lambda-Werte sind alle größer null,
55:22
keine negativen Werte, größer gleich null, aber gleich null macht jetzt weniger Sinn. So, wenn das die Bedingung ist, dass das a x, dass die, Halt, ich habe hier einen Fehler gemacht.
55:42
So müssen die Klammern gesetzt sein. So und hier auch. So, hätte sie auch finden können. Oder habe ich es jetzt falsch gemacht? Nee, so ist es jetzt richtig. So, was bedeutet das jetzt hier?
56:05
Das bedeutet, wenn das Lambda 2 größer null ist, wenn dieser Wert hier auch größer null ist, dann wird es bestraft.
56:21
Ja, wenn ich hier Summe i gleich 1 bis n a 2 i mal x i minus b 2, wenn das größer null ist, wenn also hier Verletzung ist, dann bedeutet das, dieser ganze Term ist positiv.
56:40
Positiver Term auf der Zielfunktion bei Minimierung bedeutet Bestrafung. Ja, Sie erinnern sich dunkel, so was hatten wir schon mal, dieses Muster, im anderen Kontext bei nachbarschaftsbasierter Suche, dass wir zulassen, dass Bedingungen verletzt werden,
57:02
indem wir sie einfach rausnehmen aus dem Satz der Nebenbedingungen da oben. Aber wir bestrafen sie. Wir erweitern die Zielfunktion um einen Term,
57:20
der positiv ist, also bestrafend ist, wenn diese Bedingung verletzt wird. Ja, wenn wir die Bedingungen überfüllen, verbessern wir uns da dabei an dieser Stelle.
57:51
Das müssen wir dann mit in Kauf nehmen. Wir sind jetzt nicht mehr dabei, an dieser Stelle das Problem, wie es gegeben ist, zu lösen, sondern unsere Schranken zu generieren.
58:01
Da müssen wir hin und wieder auch mal Kompromisse schließen. Da haben Sie voll und ganz recht. So, die Behauptung ist jetzt, egal wie wir die Multiplikatoren jetzt definieren,
58:27
dass das Ganze dann tatsächlich in dem Sinne einer Relaxierung ist. Und hier sehen wir mal wieder seit langer Zeit das böse Wort Beweis. Lange sind wir hier verschont geblieben in dieser Veranstaltung von dem Wort Beweis.
58:40
Jetzt holt uns das wieder ein. Die Behauptung ist, dass das, egal wie wir den Vektor wählen, ist das eine Relaxierung. Und das basiert jetzt tatsächlich auf der Formulierung a x gleich b, nicht a x kleiner gleich b.
59:02
Aber letztendlich funktioniert es mit a x gleich b wahrscheinlich auch. So wie hier, gehen wir es noch mal durch. So, für irgendeinen Vektor lambda, egal was wir hier einsetzen, wobei nicht mal positiv verlangt wird, für irgendeinen Vektor lambda, gilt,
59:30
egal was wir als lambda einsetzen. Genau, hier halten wir lambda fest. So, das ist die ursprüngliche Zielfunktion. Minimiere c Transponent x unter der Bedingung,
59:41
dass a x gleich b ist und x ansonsten auch aus dem Lösungsraum ist. Sie erinnern sich hier, das war diese Formulierung. Zum Beispiel denken Sie sich, groß x ist die Menge aller Rundtouren auf N-Punkten und a x gleich b sind Zusatzbedingungen, die die Rundtour zu erfüllen hat, damit sie noch zulässig ist. Und wir minimieren wieder die...
01:00:00
die Summe der Kantengewichte in der Rundtour. So, das ist die ursprüngliche Definition. Wenn Sie jetzt hier rechts schauen, das ist die neue Zielfunktion und der alte, der ursprüngliche Satz von Bedingungen.
01:00:25
So, wenn ax gleich b gilt, dann ist dieser Ausdruck hier Null. Egal wie die laranchen Multiplikatoren Lambda definiert sind, das heißt also, was hier rechts steht, ist identisch mit dem, was hier links steht.
01:00:45
Dasselbe Minimum, weil dieser Ausdruck Null ist. So, das heißt, der erste Schritt ist, wir gehen vom Ausgangsproblem zu einer neuen Problemstellung, wo noch dieselben Bedingungen da sind.
01:01:01
Die Bedingungen, die immer im Hinterkopf eine Rundtour beispielsweise konstituieren, plus den zusätzlichen linearen Nebenbedingungen, betrachten aber schon die neue Zielfunktion, stellen fest, dass diese neue Zielfunktion auf dem ursprünglichen Lösungsmenge gleich der alten Zielfunktion ist, weil dieser zusätzliche Sommand hier Null ist,
01:01:23
weil das ax minus b gleich Null ist, wenn ax gleich b ist. Und jetzt gehen wir noch den zweiten Schritt weiter. Wir lassen diese Bedingungen ax gleich b fallen. Und wenn wir Bedingungen fallen lassen, das sind wir in der selben Situation wie bisher waren, wenn wir Bedingungen fallen lassen, dann kann das nicht zu einer Vergrößerung der Zielfunktionswerte führen,
01:01:43
sondern nur zu einer Verminderung. Damit ergibt sich, egal wie die Lambda Werte sind, eine untere Schranke für die zulässige Lösung des Ausgangsproblems. Nochmal vielleicht ganz kurz, ich habe jetzt ein bisschen hier Konfusion reingebracht,
01:02:03
das gebe ich offen zu. Ich kenne es eigentlich eher in dieser Variante ax kleiner gleich b, wo man diese schöne Interpretation hat, dass man dann bestraft. Es funktioniert aber auch in der Variante ax gleich b und hat offenbar den Vorteil, dass der Beweis einfacher geht.
01:02:24
Gut, das heißt also in der Vorbereitung auf die Prüfung, nehmen Sie das, was ich hier gesagt habe, her als Idee, die dahinter steckt. Bestrafung von Abweichung von den Bedingungen. Und nehmen Sie eher das her, diese Variation her, um es systematisch zu betrachten.
01:02:52
So was bedeutet das jetzt? Wir wollen natürlich eine möglichst gute untere Schranke haben.
01:03:02
Ja, gehen wir nochmal ganz zurück an den Anfang. Muss ich allerdings jetzt wieder Platz schaffen dafür.
01:03:54
Wir wollen Teilbäume abschneiden. Wir sind immer noch beim Thema Brown and Bound. Wir haben immer noch den großen Baum, sind jetzt hier irgendwo
01:04:04
bei irgendeinem Knoten angekommen und wollen nach Möglichkeit diesen Teilbaum abschneiden und was machen wir hier? Und wir wollen, wir können abschneiden, das ist der Knoten V im Baum.
01:04:23
Wir können abschneiden, wenn die untere Schranke von V größer als im aktuellen der aktuellen Oberschranke auf der optimalen Lösung drauf ist. Das bedeutet natürlich, wir wollen diese hier möglichst möglichst hoch haben.
01:04:42
Wir wollen diesen, wir wollen diesen Wert so haben, dass er möglichst hoch ist, gleich möglichst nah am am optimalen Wert im Teilbaum.
01:05:15
Das in den Sachen, die wir bisher betrachtet haben, geht das nicht so richtig.
01:05:21
Der optimale 1-Bomb ist halt der optimale 1-Bomb fertig. Oder der optimale, das optimale Gebilde, was aus aus mehreren des jungen Subturen besteht, ist eben das optimale Gebilde aus mehreren des jungen Subturen fertig. Aber hier haben wir eine andere Situation. Wir haben Werte, die Lambdas, die wir frei setzen können.
01:05:44
Bis jetzt haben wir noch nicht darüber gesprochen, wie wir diese Lambdas eigentlich setzen. Wir wollen die natürlich so setzen, da kommt jetzt das hinzu, so setzen, dass die untere Schranke, die wir daraus generieren,
01:06:00
dass wir das machen, was auf der letzten Folie drauf stand, hier, die wir daraus generieren, dass wir diese Problemstellung durch diese ersetzen, also genau gesagt am Ende durch diese Problemstellung hier unten, dass diese die Lambdas so setzen, dass dieser Wert, der hier rauskommt, dieses Minimum möglichst nah an dem ursprünglichen Minimum dran ist.
01:06:23
Da haben wir völlige Handlungsfreiheit. Die Lambdas können wir, die einzelnen Lambdas können wir beliebig aus den realen Zahlen wählen. Völlige Handlungsfreiheit. Sie wissen, dass am Regal mit Zahnpasta im Supermarkt völlige Handlungsfreiheit macht die Sache nicht unbedingt einfacher. Aber in diesem Fall schon, nämlich mit Methoden aus der numerischen Mathematik.
01:06:49
Die numerische Mathematik haben Sie ansatzweise in der Mathe 3, heißt es glaube ich, kennengelernt. Diejenigen von Ihnen, die Informatik studieren, studiert jemand nicht Informatik?
01:07:01
Okay, alle, die hier im Raum sind, studieren entweder Informatik oder outen sich nicht. Ich nehme mal an, sie studieren an Informatik, also Mathe 3. Und mit diesen Methoden, die Sie da vielleicht, weiß ich nicht, kennengelernt haben, können Sie das lösen. Das ist wieder ein Beispiel für lokale Suche.
01:07:24
Das Schöne an der Sache ist, dass man kann zeigen, dass diese Problemstellung hier eine sehr schöne Struktur hat. Fast so schön wie die Strukturen, die wir am Anfang bei lokaler Suche hier an der Tafel hatten.
01:07:40
Fast so schön. Sie erinnern sich, wir hatten bei lokaler Suche immer so diesen Fall gehabt,
01:08:17
einer konvexen, differenzierbaren Funktion. Wir stehen irgendwo, vielleicht an dieser Stelle.
01:08:27
Und wenn wir wissen, dass die Funktion konvex ist, dann gucken wir uns den Gradienten an. Also stellen Sie sich das vor, wir sind jetzt nicht im zweidimensionalen, sondern dieser Bauch kommt auch hier raus, vor der Tafel und hinter der Tafel,
01:08:41
dass wir wenigstens drei Dimensionen zur Verfügung haben. Und wenn wir hier den Gradienten nehmen, oder das Negative vom Gradienten, die Richtung des steilsten Abstiegs, hier einen Schritt weitergehen und hier wieder einen Schritt weitergehen und so weiter. Wenn wir da vorsichtig genug sind, nicht allzu hohe Schrittweiten zu machen,
01:09:03
dann kommen wir automatisch, ob wir wollen oder nicht, wir wollen natürlich, aber ob wir wollen oder nicht, wir kommen bei der optimalen Lösung oder sehr nah an der optimalen Lösung raus. Hier, wenn es darum geht, diese Lagrangischen Multiplikatoren zu optimieren,
01:09:25
sieht die Funktion ein bisschen anders aus. Sie ist nicht so schön differenzierbar, aber stückweise differenzierbar. Sowas. Müssen Sie sich jetzt, also es wird jetzt ein bisschen schwierig,
01:09:42
das sich in 3D vorzustellen, denken Sie wieder an diese, vielleicht an diesen Diamanten oder so etwas und stellen Sie sich vor, es gibt oder schauen Sie im Internet nach, es gibt Edelsteine, die so geschliffen sind, dass sie wirklich aus vielen, vielen, vielen kleinen Facetten bestehen.
01:10:01
Das gibt Ihnen dann vielleicht einen Eindruck, wie man sich sowas vorstellen kann. So und wenn Sie jetzt hier irgendwo stehen, dann haben Sie an dieser Stelle einen Gradienten und können in die Richtung gehen und wenn Sie an dieser Stelle gehen, dann ist es zwar nicht differenzierbar, aber es ist in jede Richtung differenzierbar.
01:10:23
Das sind jetzt im zweidimensionalen nur zwei Richtungen, im dreidimensionalen und hochdimensionalen sind es dann noch mehr. Sie können, Sie haben keinen Gradienten mehr, sondern das nennt man Subgradienten dann. Sie haben in jeder Richtung die Möglichkeit zu differenzieren, eine Richtung des Abstiegs zu finden oder des Aufstiegs
01:10:43
und können dann unter diesen auswählen, wo es lang geht, da wo es am steilsten runter geht. Also fast dieselbe schöne Situation, wie wir sie hier prototypisch für lokale Suche hatten.
01:11:01
Und damit auch wieder ganz gut handhabbar. Das nennt sich deshalb Subgradientoptimierung. Also Sie kennen den Begriff Gradient aus der Mathematik. Das ist bei einer mehrdimensionalen Funktion die Richtung des steilens Anstiegs, wenn sie differenzierbar ist. Wir reden also eigentlich bei Minimierung immer vom Negativen des Gradienten und Subgradient, wenn an einer Stelle die Funktion nicht differenzierbar ist,
01:11:25
sowie an diesen Stellen hier. Sie ist aber in jeder Richtung salopp gesprochen differenzierbar. Dann haben Sie in jeder Richtung einen Subgradienten. Es ist letztendlich nur eine Frage der Terminologie.
01:11:43
Das betrachten wir hier nicht weiter. Da verweise ich Sie auf Mathematikveranstaltungen über Optimierung. Da wird das lang und breit ausgeführt. So nehmen wir wieder. Wir kommen immer wieder zu unserem Standardbeispiel her. Es ist einfach ein wunderbares Beispiel, um alles Mögliche zu erklären.
01:12:05
So TSP. Sie erinnern sich. Wir haben für jede einzelne Kante, die in der Rundung sein könnte, einen 0 1 Wert, eine 0 1 Variable. Wir haben auch schon geklärt, dass das ins Modell reinpasst für ganze Linienprogrammierung,
01:12:22
weil xe Element aus 0 1 gleich bedeutend ist mit xe größer gleich 0, xe kleiner gleich 1 und xe ganz zahlig. So und die Semantik war xe gleich 1 bedeutet, dass die Kante e ist in der Rundung drin. xe gleich 0 bedeutet, ist nicht drin. Haben wir auch schon geklärt, dass hier also dann mit dieser Semantik der Variablenwerte xe.
01:12:48
Was hier ausgedrückt wird, ist die Summe derjenigen Kanten, die Kosten derjenigen Kanten, die in der Rundung drin sind, weil bei denen hier eine 1 steht, sodass die CE reinkommt in die Summe und bei den anderen steht eine 0, sodass die CE nicht reinkommt.
01:13:00
So Sie können zum Beispiel, es ist nur eine von vielen Möglichkeiten, wie Sie das TSB als ganz zahlig lineares Optimierungsproblem formulieren können. Jetzt das hier kennen Sie schon, diese Bedingungen kennen Sie schon,
01:13:21
nämlich das zu jeder, dass jeder Knoten zu genau zwei Kanten in der Rundung incident ist. Das haben wir heute schon mal besprochen. Die Bedingung hier unten haben wir auch schon geklärt. Hier steht noch drin die Bedingung, dass wir genau n Kanten haben wollen.
01:13:43
Wobei ich glaube, diese Bedingung ist eigentlich redundant. Die ist durch diese Bedingung schon ausreichend erzwungen. Also wenn diese Bedingung erfüllt ist, wenn jeder Knoten zu zwei Kanten incident ist, kann es gar nicht anders sein, als dass genau solche Gebilde rauskommen,
01:14:04
wie wir sie hier haben und dann ist auch automatisch sieben Knoten, sieben Kanten ist auch automatisch die Anzahl der Kanten, die in diesem Gebilde drin sind, gleich der Anzahl der Knoten.
01:14:20
Also wenn ich jetzt spontan nichts Falsches hier sehe, dann ist die Bedingung 3 eigentlich überflüssig, redundant. Also sie ist automatisch durch die Bedingung 2 erfüllt. So, aber wir wollen dieses Gebilde eben nicht drin haben. So ein Gebilde und dafür brauchen wir noch zusätzliche Bedingungen, die dafür sorgen, dass solche Gebilde nicht drin sind.
01:14:43
So was steht jetzt? Und das sind diese Bedingungen Nummer eins, die von denen ich sagte, das sind die, das sind die komplizierten, das sind die ärgerlichen Bedingungen. So was steht jetzt hier? Hier steht drin erst einmal, was ist dieses Groß S?
01:15:06
Groß S ist, vielleicht sollten wir das mal auch illustrieren, was wir hier unter diesem Groß S verstehen.
01:15:52
Sie haben beim TSP eine Menge von Elementen, die Sie verbinden wollen, die Sie nacheinander besuchen wollen.
01:16:01
Können Punkte in der Ebene sein, sind natürlich immer einer Tafelpunkte in der Ebene, müssen aber nicht. So, Sie haben jetzt einen Knoten hier, der in der Reihenfolge der Knoten die Nummer eins trägt. Und dieses S ist jetzt zum Beispiel, könnte man das so zeichnen, dass hier auf dieser Seite der Trennlinie das S steht.
01:16:28
S ist nicht leer. Das heißt, auf dieser Seite der Trennlinie müssen Knoten sein, sind auch welche, 1, 2, 3, 4, 5 sind sogar da. Und die andere Bedingung eins Nicht-Element aus S besagt, dass auch das Kompliment, also eins aus S-Kompliment
01:16:47
besagt, dass auch S-Kompliment nicht leer sein muss, nicht sehr leer sein darf, weil die eins drin ist. Das hier ist das Kompliment mit diesen vier Knoten. Das heißt also, dieses S, mit diesem S durchlaufen wir, das ist ein Satz von Bedingungen für jede Menge
01:17:05
S, die auf diese Art und Weise die Gesamtknotenmenge in zwei Teile partitioniert, in zwei nicht leere Teile partitioniert. Für jede dieser Mengen S haben wir eine Bedingung drin. Und was sagt jetzt diese Menge, diese Bedingung S? Sie besagt, was ist denn das hier?
01:17:24
Wir gehen über Kanten. Wir summieren hier über Kanten. Wir summieren aber nicht über irgendwelche Kanten, sondern wir summieren über Kanten, die hier drin sind. So über solche Kanten, wie ich sie hier beispielhaft angedeutet habe.
01:17:43
Noch mehr Kanten. Ich habe jetzt nicht alle Kanten drin. Über die Kanten, die zwei Knoten in S miteinander verbinden. Hier sehen Sie unten IJ-Element aus S. Und diese Summe soll kleiner gleich S-Betrag sein. Was bedeutet das?
01:18:02
Ich zeichne jetzt mal, damit das besser klarer sichtbar wird, zeichne ich jetzt mal ein anderes S. Ich zeichne es etwas leicht anders. Eben war es mir wichtig, zu zeigen, dass dieses S jetzt nicht einfach einfach strukturiert ist rechts und links. Deshalb habe ich hier noch so Kringel gemalt.
01:18:22
Aber jetzt wird es einfacher zu zeichnen oder illustrativer, wenn ich es doch so ein bisschen so zeichne. Weil was es bedeutet ist, dass zum Beispiel sowas nicht erlaubt ist.
01:18:53
Denn Betrag von S ist gleich 1, 2, 3, 4, 5, 6, 7.
01:19:05
Anzahl der Kanten in diesem Gebilde hier, die wir denn zugenommen haben zur Lösung, 1, 2, 3, 4, 5, 6, 7. Weil es ja eine Rundtour hier ist. Und genau das wird durch diese linielle Nebenbedingung, durch diese Ungleichung hier verboten.
01:19:22
Genau das, dass sieben Kanten in diesem siebenelementigen S drin sind. Und wenn keine sieben Kanten drin sein dürfen, dann heißt das, das kann nicht sein. Das kann nicht passieren. Und wenn wir das über alle S machen, dann heißt das, es kann keine Subtour im Endergebnis sein.
01:19:45
Jede einzelne Subtour, jede einzelne Subtour, die wir irgendwo haben, können wir induziert ein solches S und dann greift die Bedingung. Sie haben eine Frage?
01:20:07
Ach so, guter Hinweis, diese dritte Bedingung hier meinen Sie. Also Ihre Frage ist, ich wiederhole immer die Fragen, weil Sie nicht ins Mikro reinsprechen.
01:20:21
Also die Frage ist, ob diese dritte Bedingung nicht doch notwendig ist, wenn wir in gerichtlichen Grafen betrachten, dass wir da nicht plötzlich zwei geneanergenes Zyklen haben. Ja, da würde man das sicherlich so irgendwie sowas in die Richtung brauchen. Aber Sie sehen ja, das ist jetzt hier alles ungerichtet formuliert. Ist nicht hundertprozentig allgemein formuliert hier, denn Sie können ja durchaus unterschiedliche Längen haben in der einen oder anderen Richtung.
01:20:48
Und dann muss man da sicherlich etwas tun, da gebe ich Ihnen voll und ganz recht. Aber ich glaube hier in dieser absolut ungerichteten Sichtweise, wo Sie eben auch nicht die Möglichkeit mehr haben, dass zwei Objekte in der einen Richtung andere Distanz haben als in der anderen Richtung.
01:21:05
Also einmal geht es bergauf, einmal geht es bergab, kostet länger Zeit, kostet weniger Zeit oder so etwas. Da habe ich doch trotzdem immer noch das Gefühl, ich habe noch nicht gesehen, warum die dritte Bedingung nicht redundant ist. Aber das ist auf jeden Fall ein wichtiger Hinweis, wenn wir das Ganze
01:21:24
gerichtet aufziehen, könnte man natürlich auch hier machen, wird halt ein bisschen komplizierter. Dann sollte man sich nochmal überlegen, ob die dritte Bedingung nicht doch wichtig ist. So, aber entscheidend ist hier für das, was wir hier erzählen, diese Bedingung hier, das ist genau die Bedingung, die dafür oder der Ersatz von Bedingungen, der dafür sorgt, dass es keine Rundtouren gibt, die nicht die eins enthalten.
01:21:48
Ja, weil für jede Rundtour, die nicht die eins enthalten, habe ich ja so ein S. Gut, jetzt könnte man fragen, was ist mit Subtouren, die die eins enthalten? Naja, wenn es eine Subtour gibt, die die eins enthält, gibt es auch noch eine weitere Subtour, die die eins nicht enthält.
01:22:03
Und da habe ich wieder mein S. Ja, wenn Sie eine Subtour haben, wieder mein Standardbeispiel, was die eins enthält und das ist keine Rundtour, ist keine zulässige Lösung fürs TSP, dann gibt es noch eine zweite Subtour, die die eins nicht enthält und dann können Sie hier auf diese vier Knoten als ihr S definieren.
01:22:30
So, jetzt sehen Sie nochmal ein schönes Beispiel dafür, wie mächtig ILP als Sprache ist, um Optimierungsprobleme auszudrücken. Wie gesagt, das vertiefen wir in der algorithmischen Modellierung nächstes Semester, falls es Sie interessiert.
01:22:46
Bitte? Ja? Ok, gute Frage oder erstmal gute Beobachtung. Die Anzahl dieser Bedingungen ist exponentiell groß.
01:23:08
Ja, überschlagsweise, was ist exponentiell? 2 hoch 100. Wo stehen wir da? In der Größenordnung im Dezimalsystem.
01:23:20
Also bei 100 Knoten wären wir hier bei Größenordnung 2 hoch 100. Also was ist 2 hoch 10? Ich habe eben gefragt, alle haben sich als Informatiker geoutet. Also 2 hoch 10 sollte bekannt sein.
01:23:41
Das ist ungefähr 1000, das ist nämlich genau 1024. 2 hoch 20 ist dann ungefähr was? Wenn 2 hoch 10 1000 ist, also 10 hoch 3? Also 2 hoch 10 ist ungefähr 1000, also 10 hoch 3. Frage, was ist jetzt 2 hoch 20?
01:24:25
So, jetzt müssten Sie da irgendwie mit exponentiell gesetzten und logarithmengesetzten vertraut sein. Ungefähr 10 hoch 6. So, das frage ich Sie jetzt nicht mehr, sondern setze ich 1, 2 hoch 100, ist ungefähr 10 hoch 30 dann natürlich.
01:24:50
Ungemütlich, nicht? Diese Größenordnung. Wenn man allein schon diese Größenordnung in den Rechner zu packen. Wir reden ja noch nicht von der Lösung. Wir reden ja nur das Ganze zu repräsentieren. Also eine sehr wichtige Frage. Kann man das überhaupt einsetzen? 2 Antworten.
01:25:02
Erste Antwort. Ja, es gibt algorithmische Verfahren, die nennen sich Column Generation Schemes, also Spalten, Generierungs, Schematar, Prozeduren, Algorithmen, was auch immer. Und die ignorieren am Anfang erst einmal diese Bedingungen, sondern versuchen erst einmal hiermit mit den anderen Bedingungen klarzukommen und
01:25:34
gucken immer mal zwischendurch, welche von diesen Bedingungen werden sehr stark verletzt und packen ein paar von diesen Bedingungen rein,
01:25:46
lösen weiter, arbeiten weiter, gucken dann wieder, was ist mit den Bedingungen, die wir reingetan haben, was ist mit anderen Bedingungen, werden die auch verletzt, entscheiden dann, dass Sie ein paar von diesen Bedingungen, die Sie reingenommen haben, wieder rausnehmen. Sie kennen das Ganze. Wir haben sowas, sage ich sagen, bei lokalen Suchverfahren solche Ideen gehabt, nehmen dafür wieder andere
01:26:07
Bedingungen rein, die jetzt besonders gröblich verletzt werden und versuchen so Schritt für Schritt dann zu einer Optimallösung zu kommen, bis Sie feststellen, keine dieser Bedingungen wird mehr verletzt. Es gibt solche Verfahren, die auch in der Praxis, also theoretisch sind sie gruselig, aber in der Praxis funktionieren die sehr, sehr gut.
01:26:26
Erste Antwort. Zweite Antwort. Wir sind ja hier in einem Kontext, wo wir ja gar nicht Lösung haben wollen, sondern wo wir über unsere Schranken reden. Und da sieht die Sache natürlich noch mal anders aus. Aber beachten Sie auch die erste Antwort. Ja, auch wenn
01:26:43
wir nicht in dem Bereich untere Schrankenbranche bauen sind, sondern wenn wir wirklich lösen wollen, dann ist so eine Formulierung realistisch. Damit kann man, damit können solche Löser ganz gut umgehen, indem Sie eben nicht die Gesamtmenge betrachten, sondern immer eine sehr kleine Auswahl dieser Bedingungen.
01:27:08
Erfahrungsgemäß reicht das, um ganz gut hinzukommen. So, wie spät haben wir es? Wir sind jetzt fast fertig. Vielleicht nur ganz kurz noch, was wir jetzt beim TSP da eigentlich machen. Die Nummer 5. Wo ist Nummer 5? Da.
01:27:38
Diese Bedingungen, dass es genau zwei Kranken incident wird, wird reduziert, die wird relaxiert, dass es genau zwei sind.
01:27:51
Das heißt, wir führen die ein in die Zielfunktion. Wir nehmen sie raus aus dem Satz von Bedingungen. Entschuldigung, halt, halt. Diese Satz von Bedingungen nehmen wir her und für jeden Knoten i gleich 2 bis n lassen wir den, diese Bedingung her.
01:28:28
Und für den Knoten 1, für alle Knoten, die den Wert 1 haben, jetzt muss ich nochmal überlegen. Zum Glück ist jetzt die Zeit vorbei, sodass ich nochmal eine Woche Zeit habe, mir genau zu überlegen, was ich jetzt hier eigentlich sagen wollte.
01:28:53
Okay, also, was das jetzt genau bedeutet, hier, wie wir das Lagrange-Relaxierung auf
01:29:04
diese Problemstellung anwenden, das betrachten wir dann beim nächsten Mal wieder in alter Frische. Für heute und für den Rest der Woche, ja, Ihnen eine schöne Zeit. Sieht ja sogar langsam mal wieder mit dem Wetter einigermaßen aus, auch wenn es bitterlich kalt ist. Okay, bis zum nächsten Mal. Oh, Sie sehen, ein paar Sekunden habe ich jetzt zu wenig Vorlesung gehalten.