Merken

Exakte Verfahren I: Branch & Bound, Dynamische Programmierung

Zitierlink des Filmsegments
Embed Code

Automatisierte Medienanalyse

Beta
Erkannte Entitäten
Sprachtranskript
das These Aenis is a war am herzlich willkommen
zur Vorlesung in diskreter Optimierung Herr Herman ist auf einer Tagung in Dagstuhl hält daher bin ich heute und am Mittwoch hier bei euch und lernen echt coole Sachen diese Woche weil dann die Sachen dran sind die sich in den aktuellen lösen Verwendung haben also so richtig das was geradegemacht wird um diskreter Optimierung zu lösen also hoffe ich dass ich das interessieren wird das ich alter Zehner wir schauen uns Jahr die ganze Zeit soll ich hier diskreten Optimierungsprobleme gemischt ganzzahlige Probleme von soner Form an ja solche Probleme schauen wir uns jetzt schon seit Beginn des Semesters in irgendeiner Form an wir haben ein Optimierungsproblem linear Jahr wo einige Variablen ganzzahlig sind ich hab jetzt zusätzlich hier dieser Grenzen angebracht wobei hier steht dass diese Grenzen auch minus und plus unendlich sein können also wenn wir keine Restriktionen an die Variablen haben ist das damit abgedeckt den sind allen im Minus und plus unendlich was haben wir schon in der Hand um mit diesem Problem umgehen zu können was können wir schon das ist ne Frage an Sie was waren die letzten beiden Kapitel Bormanns damit beschäftigt zum Beispiel also Relax zierung was können wir mit Relax tierung machen was geben die uns also was haben wir praktisch schon die das sage ich Kapitel 3 was geben die uns wenn Relax Chirurgen davon anschauen also dem Obst bei einem Minimierung Skroblien dann gibt uns die Lösung von einer Relax ierung was für das gesamte Problem da ist genau also hier kriege untere Schranken aus gut und was haben wir jetzt ganz aktuell letzte Woche gemacht ja genau also haben wir das Ding angeschaut Sachen irgendwie versucht Lösungen zu konstruieren von den man noch nicht gefordert haben dass sie optimal sind aber die geben uns immerhin schon mal obere Schranken so gut werden wir mindestens eine Lösung also der haben wir dann eine 1. eine zulässige Lösung oder aber damit dass es ja bisher erst mal noch einen noch nicht so ganz befriedigende Situation ja wir können zwar schon mal Schranken für unseren optimal Wert angeben aber haben bisher noch keine Möglichkeit zu sagen wir sind jetz optimal ja jetzt sind wir am Ziel genau da angelangt wo wir hin wollten und genau das soll das Thema der Vorlesung heute und am Mittwoch sein nämlich exakte Verfahren wie können wir wirklich sicherstellen dass wir eine Lösung finden die eben auch optimal ist neben der Zulässigkeit n wäre ok wie kommt man an sowas werden und wie kann man überhaupt zeigen dass etwas optimal ist diese Schranken kann uns dabei helfen wenn die gleich wären der Name im Zertifikat für Optimalität aber grundsätzlich erst mal muss man dafür sorgen dass man seinen Lösungsraum wirklich ganz betrachtet bei der Heuristik hat der letztes Mal zum Beispiel sowas wie lokale Suche gemacht wo man irgendwann anfängt sich einzuschränken auf nur einen Teil des Lösungsraum ist wenn man vermutet dass man vielleicht schon ne ganz gute Lösung im wie Algorithmus bekommen hat früher so aber man schaut dann nicht mehr auf den ganzen Lösungsraum also wichtig ist dass wir in irgendeiner Form den gesamten Lösungsraum und betrachten müssen was ist jetzt dann schlecht wenn wir das setze erst mal grundsätzlich tun da kann man im Zweifelsfall ganz schön lange suchen nach Wien ihre Probleme in hohe Dimensionen das man auch schon lange unterwegs ist hat ich im Zweifelsfall exponentielle Laufzeit also muss man sich dann bis hin geschickt anstellen das ist also nicht so die IB naja man rät eben und dann kommt man schon ins Ziel hat dann ein Zertifikat das glücklich das kann nicht der Weg sein und deshalb haben auch Vorarbeit geleistet und die es uns diese Sachen angeschaut Heuristiken und Relax zierung um Häusern Verfahren kennen zu lernen bei dem wir genau diese Sachen nutzen um insgesamt den Lösungsraum denn wir wirklich anschauen müssen so geschickt anzuschauen so geschickt zu durchsuchen das Leben mit guter Hoffnung sind dass wir nicht alle Lösung aufzählen müssen gut wie wollen wir das
Tool in den 2 Vorlesung jetzt heute und am Mittwoch werden wir 2 Verfahren Kindern dass einer Maisbrei brennt scheinbar und dann kommt das Wort bauen schon vor die beiden Schranken über haben wenn wir verwenden sie die Varianten Schranken zu finden und dynamische Programmierung so Arbeitsfreude zuerst mal wollen uns hiermit beschäftigen an Name haben ebenso ein Problem ganz ähnlich wie es da drüben im steht ich nehme jetzt erstmal hier nur ganzzahlige Variablen und mach keine explizite Aussage über die Schranken weil die am 2. Valemon endlich sein können es geht erstmal nur darum bisschen Prinzip klar zu machen bevor wir den Algorithmus so er im Skript steht dann durch werden wenn also zum Problem P haben man kann nicht für dieses Problem wenn ich ne Heuristik habe eine Anwen und vielleicht nie irgendeine zulässige ganzzahlige Lösung konstruieren ein für dich dann Ziel Funktionswert raus OA und ich mache das jetzt wie gesagt habe er keine Zahlen eingesetzt die Zahlen fallen jetzt haben wir es geht wie gesagt nur darum bis in das Prinzip zu verstehen was man bei brennt scheinbar und macht eine Norm ich hab hier in Minimallösung bisher gefunden durch neues Tisches Verfahren mit dem Wert 25 und meine LP Relax zierung gib mir auch ne Schranke zum Beispiel 20 ,komma von der das kann ich einfach mit jedem Problem erst mal machen im Zweifelsfall wenn ich keine Heuristik zur Verfügung hab keine nicht einfach eine ganzzahlige Lösungen finden kann naja wenn die beste bisher gefundene Lösung im Plus unendlich dann hab ich halt noch keine vielleicht kennt ihr solche Ansätze die Leute die Informatik als Nebenfach haben die weiteren Conga heißen immer Teile die irgendwie das Problem in so Probleme auf und versuche die in den Griff zu bekommen so was kann man bei ganzzahligen oder gemischt ganzzahligen Optimierungsproblem auch machen man kann nicht einfach sagen ich möchte für eine Variable nicht alle möglichen Werte betrachten sondern ich teile mir das ein wenn eine Variable x ist auf der einen Seite haltet größer 5 und auf der anderen Seite kleiner 4 ich fühle also zum meinem System was ich sowieso schon Haber zusätzliche Bedingungen zu und kriege damit neue Optimierungsproblem am was wichtig ist zu verstehen wir verlieren damit keine Lösung denn wir sagen unseren Variablen sollen ganzzahlig sein also es ist okay wenn ich sage auf der einen Seite 7 größer 5 große gleich 5 und auf der anderen Seite kann man einen Teil Problem sie kleine gleich 4 es sollte allen klar sein dass die die beiden vereinigt zusammen trotzdem den ganzen Lösungsraum ergeben ja das heißt wenn die zusammen betrachte ich immer noch meinen gesamten Lösungsraum und insgesamt das Minimum von der gesam Gesamtproblem wird natürlich das Minimum dieser beiden Teilprobleme sein gut jetzt hab ich ja gesagt wir wollen mit Hilfe also das Verfahren herkömmlich hat einfach weitermachen können die entweder jetzt ne andere Variable x K nehmen und die weiter aufteilen oder hier nochmal aufteilen auf der 1 in einem weiteren Problem soll die Variable x J jetzt auch zusätzlich noch größer gleich 7 sein und dem anderen in dem anderen Teil halb 6 oder 5 Jahren sich könnte hier immer weitermachen aber das wäre ja genau das was wir nicht wollen wenn am Ende vollständige aller Lösungen die man hat ne immer Einschränkung ich hier mache umso mehr komme ich sozusagen eine echte ganzzahlige Belegung meine Variablen weil ich mich immer weiter einschränken aber wenn ich das einfach so erst mal grundsätzlich als Einschränkung immer weiter mache komme ich zu einer vollständigen Innovation das möchte ich nicht was für Fehler könnten jetzt aber also vorkommen wenn Aufteilung machen was kann mir passieren Na ja vielleicht hab ich durch meine Aufteilung hier eine Ungleichung hinzugefügt wir mein Problem kaputtmacht ginge es unlösbar macht es ok ja war dank schön gut also was kann mir passieren wenn ich wenn ich seine
Aufteilung vornehmen könnte mehr passieren dass die zusätzlichen wo zu Lösbarkeit führt Na ja das ist zwar nicht schön aber immerhin weiß ich dann schon mal Herrn Hawass über die Variable gelernt Unlösbarkeit festzustellen schmeiß ich einfach meine LP an und schaue ob die Relax leer ist ja das darf man zwar noch nicht darüber ob der vielleicht nicht doch noch falschrum wenn DLP-Lösungen lösbar ist sagt dass man nichts darüber ob da nicht vielleicht doch noch ein ganzzahliger .punkt keine ganzzahlige .punkt um mal so erstmal eine LP lösen zu haben sagt man nichts darüber dass ich nicht vielleicht ein kleines Stück aus irgendeinem er auch ein ausgeschnitten abnehmen keine ganzzahlige .punkt mehr drin ist aber wenn die Lösung erst dann bin ich zumindest weiter und kann diesen Teil des Baumes einfach ich mehr beachten so und jetzt komme zu dem viel spannenderen teilen deswegen also Brain schien es eben das was ich gerade meinte nur wir machen irgendeine Annahme über meine Variable dem komm ich 2 Problem und damit das könnt ich fortsetzen und jetzt hab ich aber er bisher so nicht dass da aufgeschrieben hat eine ganzzahlige Lösungen vielleicht in der Wurzel schon gefunden und hab aber meine meine Schranke nur für den Wurzelknoten die untere Schranke durch ne LP Relax Xiong das ist dieses des Best was ich dann geschrieben haben wir nur für die LP Relax Jung vom gesamten Problem angeschaut was kann man passieren wenn ich jetzt wieder in P 1 also in meinem Teilproblem nochmals die LP Relax zierung ausrechnen dadurch dass sich der neue Nebenbedingungen zugefügt haben wie wird sich dann auf jeden Fall die Schranke praktisch verändern ja genau ich bekomme eine Schranke die über also größer gleich der bisherigen Schranke ist was mir passieren kann und dazu völlig den Baum vielleicht einfach noch mal ein bisschen auf eine Norm ich mach hier unten einfach noch mal weiter nämlich irgendeine weitere Variable so ich das 8. XK auch auf Teile zusätzlich ja und dann schon gesagt ja die die SSH untere Schranken jede schnell per lanzierung passiert es die wird schon mal schlechter vielleicht also ist die an dieser Stelle vielleicht schon nur noch 22 , 5 ja irgendwie schlechter als vorher und hab ich hier noch eine zusätzliche Nebenbedingung da zugefügt und dann wird man die Schranke plÃtzlich richtig schlecht sag ich mal nämlich den was weiß ich mit dir die 7 20 innerhalb die war aber hier oben haben wir schon eine Lösung gefunden die den viel Funktionswert 25 hat wir sind jetzt in so einer Situation was verschlüsseln kann ich jetzt ziehen mag jemand anderer mitmachen ja genau richtig ich bin hier ne 1 Teil wo ich eine untere Schranke hab wie schlecht ist als meine bisherig gefundenen Lösung ja also wirklich in diesem Teil Baum in egal wie wir hier unten weiter auf Teile er dich nie besser werden als diese Schranke also kann ich das vergessen und kann sagen hier dieser Knoten dieser Teil Baum interessiert mich nicht dann brauch ich mich weiter anschauen und das genau die Idee von Brennstäben Bau und wir versuchen Schranken möglichst Dusche auszurechnen und mit Hilfe dieser Schranken unseren Lösungsraum so klein wie möglich zu halten so gut das geht selbst mit solchen Schranken ist man nicht gefeit davor dass man dennoch alles ignoriert manchmal hat man Instanzen woanders gar nichts hilft diese Schranken auszurichten wenn man nie zurück sozusagen zu so einer Art Widerspruch bekommt wenn man keine guten Schranken berechnen kann oder so aber es ist zumindest eine Möglichkeiten das ist die Möglichkeit die genutzt wird aktuell also 2. Variante ist gut und was man im Verlauf vor natürlich auch haben kann ist dass man irgendwie dadurch dass man hier weiter eingeschränkt hat jeder die Möglichkeit hat also man hat grundsätzlich natürlich in jedem Teil Problem die Möglichkeit wieder Heuristiken anzuwenden oder auf die bisherige Lösung irgendwelche Verbesserungs Algorithmen irgendetwas zu machen und das kann er natürlich passieren dass man irgendwie hier das war nicht so gut das war in einem an anderen Treiber und vielleicht ein neuer IP also nur schone ganzzahlige Lösung findet die aber schon besseren Ziel Funktionswert hat und
wenn es nur 24 ist ja dann muss man natürlich sie revidieren und da ein Update machen und dementsprechend weiter also auch Einschränkungen dadurch dass meine bessere obere Schranke findet es natürlich hilfreich weil man dann im unteren Schranken schneller etwas verletzen kann also man versucht sich natürlich anzunähern und auch klar ist wenn wir an irgendeinem Treiber um Anlagen wo die beste gefundenen Lösungen muss ich aufpassen sich die ungleichen richtig Hinrik Poly Buddy Schranken so sind dass man eben genau weiss dass die untere Schranke gleich der oberen Schranke praktisch wird ja dann weiß man ja man hat Optimalität und brauch auch nicht weiter so logischerweise also dass es auch nur Hoffnung dass man auf dem Weg schon die Lösung geben findet bevor man den ganzen Baum aufgespannt hat das schreiben und jetzt als Algorithmus ordentlich auf ich hoffe aber zumindest schon mein Eindruck davon gewonnen die Menschen bauen an sich funktioniert als unser in Rot das und der Import ist genauso und mit wie ich da oben mit mir bezeichnet hat und was wir gerne zurückhalten wäre entweder eine ich sagt deshalb zulässig bzw. optimal weil nicht klar ist dass man den ganzen Baum denn immer weiter aufspaltet überhaupt aufbauen kann möchte will oder überhaupt ja ganz oft ist es so dass man sich in diesem Aufbau irgendwann damit zufrieden gibt dass man schon in einem gewissen nur noch mehr gewisse Distanz zwischen unterer und oberer Schranke hat
sein verweist dass man sich nahen Fenster rund um die optimale Lösung befindet man hört auf dann ist man schon froh wenn man eben da überhaupt Variablen Belegung gefunden hat die alle ganzzahlig keits Bedingungen wie man fordert erfüllen wurde ja oder wir wollen dem rausfinden wir haben gar keine ganzzahligen .punkt in unserem Problem gut was macht man einmal und muss man muss sich zuerst überlegen welche Variablen brauch man damit der Algorithmus alle Informationen hat die er braucht und wie initialisiert ich die na ja im brauchen als 1. eine Variable die uns die beste ganzzahlige Lösung speichert die initialisiert ich erstmal weil ich ja noch nichts gelöst hat mit plus unendlich und dann wenn ich das Problem aufgeteilt habe dann hab ich jetzt plötzlich 2 Probleme nicht lösen müssten möchte also muss sich in irgendeiner Form mir meine Probleme die ich noch abzuarbeiten haben nämlich im Zweifelsfall die hier einen bin ich da unten schon wieder weiter schon weiter verzweigt und hab ich insgesamt irgendwie 3 Probleme die ich abarbeiten muss in irgendeiner Reihenfolge die muss ich mir auch merken die Speicher nennen lässt am und initialisieren damit unserm Ursprungs Problem wenn wir irgendwann alle Probleme die wir je hatten in unserer Liste durchgearbeitet haben sind wir natürlich den Namen nichts mehr wo wo werden was rausholen kann um Informationen herholen können Sie mal so fertig also versuchen wir so lange werden welche Probleme haben die aber zu lösen das ist sozusagen unsere mobile Schleifer Na ja dann nehmen wir uns also ein Element der Liste zu und während wir natürlich das Problem das wir gerade bearbeiten aus unserer Liste so und jetzt wollen wir unsere Schranken berechnen Na ja an dem Raume irgendetwas um uns vielleicht eine ganzzahlige Lösung zu finden also irgendein Primal es Verfahren als unzulässige Lösung gefunden wird speichern wir diesen optimal also den Wert wenn er besser ist als der bisherig gefunden ja das ist wie gesagt der Fall finden bessere Lösung dann wollen wir sind erst am auf genau und wir merken uns auch diese Lösung denn wir wollen ja irgendwann vielleicht ne Lösung ausgeben damit haben wir also und so obere Schranke und dann möchten wir irgend eine untere Schranke berechnen mehr mehrerer gegebenenfalls mehrere Varianten nicht nur die LP Relax zierung die wir anschauen können und die beste gefunden Schranke behalten wir also merken uns wenn was nicht so ganz klar wer kann man vielleicht was nicht lesen das okay ja okay gut gut und jetzt jetzt kommt der der Zeitpunkt wo wir haben irgendeine eine ganzzahlige Lösungen gerne Schranke also der Ärztezeitung die beiden zu vergleichen um zu schauen ob wir vielleicht schon aufhören können mit unserem Algorithmus und also das ist der Fall wenn unsere duale Schranke im Teil Problem schlechter ist als unsere bisher gefundenen Optimallösung ist weil praktisch genau dieser Fall hier dann brauche ich den Arzt nicht mehr weiter angucken da sagt der Algorithmus vergisst einfach das was hier war sucht er nicht weiter erzeuge keine neuen Teil Probleme sondern such dir in Schritt 2 also such dir wieder wenn die Liste noch nicht jetzt nächste Teilproblem aus das ist praktisch genau das was man hier mit dem Abschneiden des 1. das macht man erzeugt keine weiteren 9. halt Probleme in der Liste gut muss haben gut im anderen Fall haben wir da also noch einen ein Teil Problem in dem wir uns gerade einmal gut muss also das weder dem Algorithmus betrachten was gegebenenfalls noch eine sinnvolle Lösung ne bessere Lösung enthalten könnte also müssen wir
damit weitermachen und an dieser Stelle würde man dann eben weil das Problem noch interessante Lösungen halten könnte es weiter aufteilen sollen jetzt müssen wir diese Aufteilung Hilfe zu investieren komplizierter aufgeschrieben also man nimmt einen Werte zwischen beiden Schranken legt und sagt das ist mein Grenzwert einmal links davon einmal rechts davon das 50 das dieses Gamer so und dann fügen wir zu unserer Liste 2 neue Probleme dazu der sagt mir einfach nur in dem einen Teil Probleme hab ich die obere Schranke entsprechend angepasst und dem anderen Problemen die untere Schranke so angepasst das zusammen und noch die gesamte der gesamte Nutzungsbereich ist und das kann man dadurch angehen dass man sagt alle anderen Variablen die auf den ich gerade nicht brennt betrachte ich nicht mehr bleibt die Schranke ansonsten nämlich in mir mein gewähltes Gamma zwischen den beiden Schranken genau so auch mit den oberen Schranken der unteren Schranken ende das ist einfach nur ein bisschen umständlich aufgeschrieben dass das eben aufteilen in die 2 Bereiche ja richtig also meinen wir genau die Initialisierung Erfolg geben wird genau mit einfach nur mein Problem das steck ich rein und fange an machende prima alle Mal Heuristik oder so was ein prima das Verfahren finde Schranke machen du Verfahren und wenn das schon er war oder man also da wird man kein Widerspruch finden denn da hat man erst mal ja denn das ist in dem Spezialfall der Fall nennt man dann schon also wenn man packt es genau sagt angenommen Mehr haben eine LP Lösung und eine unserer ganzzahligen Variablen ist in jener Form gebrochen Mehr als ist keine ganzzahlige Lösung bei der LP Relation außer kommen kann man genau sagen da mächtig schneiden aber das ist schon Spezialfall das stimmt nannte man ja das kann also das macht schon so erstmal sind nicht mehr wir sprechen gleich noch mal ne Pause drüber aber die Einschränkungen die wie man die wie wie sagt man gibt mir sozusagen nochmal Sub Varianten von diesem Algorithmus und da ist es weiß ich nicht ob sie immer total klar ist dass man genau auf einer gebrochenen Variablen brennt muss es wird einfach gut so war ein Zimmer gleichwertig mit dem Algorithmus und nach einer Pause das ist ne lustige Schreibweise das wir zum murren weil Schleife zu machen der nicht wundern was n zu lange heißen soll es ist dieses solange aus 2. was wieder zu machen ok man also alle Probleme die wir noch unsere Problemliste durchlaufen haben das nach der hier das jetzt eben wieder zurück zu deiner überprüfe ob das Kriterium noch Geld suchte das nächste Teilproblem macht wieder weiter weiterbrennt gegebenenfalls weiter und so fort und wenn er am Ende nachdem wir zuende gebremst habe nichts gefunden haben dann bleibt unser ZIP einfach auf plus unendlich weil nie eine zulässige am ganzzahlige oder die entsprechenden Ganzheitlichkeit Bedingungen erfüllen Lösung gefunden haben und andernfalls haben wir eine sind glücklich damit gut dann machen wird erst mal kurz Pause so 10 Minuten da gut man mit 2. und es
gibt noch ein paar Sachen einfach so zu überlegen wie dieser Trend einbauen Algorithmus überhaupt abläuft was der tut worauf man da 8. könnte kann wenn man sich um das begrenzen also um die Schranken nicht schert wenn man einfach keine nicht nicht rein investieren will dann funktioniert das Verfahren natürlich immer noch man hat wie diese Updates der besten Schrank und sowas sondern dann läuft einfach auf Innovation heraus ja also dem
zugrundeliegendes praktisch Innovations verfahren wir haben's verfeinert dadurch dass wir die Schranken haben aber wenn man vielleicht keine Möglichkeit hat Schranken zu berechnen ist zumindest eine Variante eines Innovations Verfahrens das funktioniert also dass alle den Lösungsraum wirklich absucht Dennis ist die Frage warum können wir damit überhaupt eine Lösung finden oder warum gibt es eine oder sowas denn da haben wir zum Glück sind ein Lemma aus alter Zeit was uns hilft also wenn unser Optimierungsproblem mit denen Ganzheitlichkeit Bewegung auf einigen Variablen nicht leer ist mir also einfach einen solchen .punkt enthält dann wissen wir haben ist die Kodierung es länger dich so abschätzen einst .punkt das war der Mann zwar 7 weil wir wissen dass wir wenn wir einig der das Programm haben dann haben wir in einer bestimmten Umgebung rund um die 0 zu sagen das gibt uns praktisch so ne Art ab Sterns die Kodierung es länger haben wir einen ganzzahligen .punkt und den finden wir dann auch werde es endlich weit weg also müssen auch nur endlich viele Bahnschiene Schritte machen um einen davon zu dem zu gelangen also beides diese diese Abschätzung Gerd wissen wir dass unser Algorithmus was die auch findet in endlicher Zeit ja zu der wo kann wenn man unser Problem wirklich beschränkt also beispielsweise wenn unsere Schranken nicht plus und minus unendlich sein sondern echte Schranken in den rationalen Zahlen dann finden die Optimallösung damit auch sorgten steht der FC Teil dass man das Verfahren besonders gut in dem brennten Baum Baum darstellen kann das ist genau das was ich Euch vorhin versucht habe anzudeuten ohne jetzt echte Zahlen aber wo ich meinte na ja man hat eben seinen Teil Probleme man schreibt sich an die Knoten jeweils die kann er die kann in die Schranken dran die man schon ausgerechnet hat es einfach nur gute Darstellungsweise wird so auch in der Literatur verwendet und eben benutzt einfach um das zu visualisieren wo Code wir haben jetzt immer Braunschen gewählt wo wir jede Variable nur auf praktisch 2 also in 2 Teile aufgeteilt haben ihren Lösungsraum ihren Ganzheitlichkeit Bereich das ist nicht zwingend notwendig na also man kann da auch 5 3 Probleme aus dem 1. Problem generieren solange man damit den ganzen bei der ganzen Lösungsraum wieder darstellt sie zu wenn man es halt das einzige Wort man 8. muss ist das man Detailprobleme wieder zum ganzen Lösungsraum zusammensetzen können muss wir eine andere wichtige Sache die man nicht vergessen darf ist wie was ist Deskop von meinen Schranken wie weit sind die gültig für was sind die gültig und so einer LP Relax Chirurgen die gilt genau für das Teilen Problem beziehungsweise den darunter liegenden Baum wenn ich mir anschaue wer mehr gesehen dass sich die Apple Relax jung durch das Zufügen von weiteren Ungleichungen weiß sehr genau dem Brunch nennt spricht sich verschlechtern kann ja diese geht also immer nur lokal während einer gefundene ganzzahlige Lösungen als obere Schranke global für den ganzen gesamten Bentschen .punkt gilt das heißt wir brauchen auch immer nur diese eine einzige Variable die wir immer wieder updaten so weit eine bessere ganzzahlige oder dem ganzzahlig Calls Bedingung entsprechende Lösung gefunden haben .punkt ja wenn wir ja einem bestimmen voran
unteren Schranken also beim Bestimmen von einer LP Relax sierungen oder na ja wenn man LP Relax Jung hat und davon die Lösung dann kann man hier mit Schnittebenen Verfahren die ja auch schon kennen gelernt hatte manchmal noch verbessern ja so man kann die alte LP Lösung die man hatte noch abschneiden noch eine bessere Annäherung an das ganzzahlige Problem finden und dadurch die Schranke besser Bestimmer seine bessere untere Schranke bestimmen und wenn man solche Schnittebenen Verfahren verwendet dann nennt man den Algorithmus gleich mal anders nämlich brennt hat weil man Schnittebenen verwendet hat und in dem Fall wird dann auch auf jeden Fall immer auf einer nicht ganzzahligen Variablen verzweigt es wird einem andern aus dieser Lösung die man in dem Teil Problem bekommen hat eine Variable die gerade ihre ganzzahlig Keith Bedingungen verletzt die es 2 , 5 und dann sagt man eben im einen Teil warum soll sie kleiner gleich 2 mit dem anderen Teil war am nächsten Tag Problem größer gleich 3 sein dass ich muss man machen wenn man eben in diesen unter diesem Namen eingehen möchte wir wir werden unser aber da war ja die ganzzahlig sein sollte ganz ehrlich war haben wir aktuell in der Lösung geben nicht ganzzahlig ist ja und diese Sachen 2 ich denke das ist relativ gut zu verstehen dass die Brent scheinbar und beziehungsweise brennt Schein kann grundsätzlich funktioniert ist das was Sie plexe und alle anderen Möser tun ja das ist das womit wir gerade arbeiten wenn man in der Form eine IP Löser anschmeißen dann sind ist da in irgendeiner Form brennt scheinbar und trennen im implementiert besser oder schlechter je nachdem sie Plex macht das meist sehr gut aber die haben Konkurrenz bekommen namens Grobi also lohnt sich das auch durchaus mal reinzuschauen denn da gibt's ganz viele also wo kann man denn noch drehen in diesem Algorithmus was sind denn da sozusagen auch Sachen wo ich noch keine genaue Spezifikationen gemacht haben ja genau also man hat zum Beispiel Spielraum deren in welcher Reihenfolge arbeite ich die aktuellen Blätter meines Baumes ab und dann hab ich noch ne Stellschrauben nämlich wie wenig die Variable aus auf der Spur Verzweiger welche nämlich der welches der schlau oder ist es schlau überhaupt grundsätzlich immer zuerst ganz tief rein zu gehen dann so lange weiter zu planschen oder ist es schlau irgendwie das hängt mit der Reihenfolge der Abarbeitung wieder ab oder schlau ab und zu mal zu dem ganz anderen Teil meines Traums zu springen wie baue ich denn überhaupt auf mein Weltenbaum Baum und wer da schlauer Dinge aus findet da freuen sich viele andere Leute sehr drüber also das ist wirklich was für Leute aktiv zurzeit noch drüber nachdenken bleibt nur noch an dieser Stelle ein paar kleine Schlagworte doch an wenn Sie gesagt der irgendwie Spaß dran hat es ist ja eigentlich keine besonders kompliziertes Verfahren man kann es ruhig in Matlab in was auch immer egal was am noch unterschreiben und sich bei dem Parsteiner Problem anschauen dieses Visum den aussieht oder wie sich das verhält in verschiedener Weise und ganz essentieller Punkt ist ich kann ja irgendwie mit einem Problem an der und brennt darauf mache dann alles mögliche aber wenn dieses Problem zulässt dass ich vielleicht von Anfang an schon die Ungleichungen sehr viel stärker machen kann durch Runden durch Schnitte durch was weiß ich dann sollt ich das tun oder wenn sich wenig vielleicht in dem binären Brook Programm haben wir oft Möglichkeiten Lösung auszuschließen wäre einfach dadurch dass man in die Ungleichung klar sieht diese Lösung kann also diese Variablen Belegung kann keine Lösung meines Problems sein die kann ich jede durch eine zusätzliche Ungleichung aus schließen oder so etwas dar das sollte man dann definitiv tun ja ich möchte mein Ursprungs Problem und gegebenenfalls sogar in jedem Teil Problem wieder möglichst viel Wissen reinstecken und gute Schranken zu bekommen das heißt Prib riss es einfach mächtiges Werkzeug an der Stelle möchte man machen ich dann haben wir gerade schon gesagt wir wissen noch nicht welche Regeln für die Auswahl von Variablen oder Knoten besonders schlau sind gibt es jede Menge Literatur drüber dann die Frage kann ich vielleicht mit den Informationen die ich aus der Welt gebe ,komma also aus LP Löser oder aus dem dualen Simplex gegebenenfalls kann ich die werden vom Verwendung vielleicht Variablen schon zu fixieren im Laufe meines also muss alles was ich lernen kann sollte ich lernen um den Baum klein zu halten denn der wird im normalen echt Weltproblemen sowieso riesig also alles was irgendwie dazu beiträgt den Baum zu beschneiden in welcher Form auch immer ist hilfreich wir gerade schon gesagt man möchte vielleicht Schnittebenen hinzufügen eigener Form wenig die zum Problem hinzufüge wenn gelten ja auch für den gesamten Teil überwunden und runter das muss ich mir also mal vormerken das heißt da hab ich Managementaufgaben und muss aufpassen an welchen Stellen für dich gehen 2 möchte Schnittebenen Verfahren jedem Knoten machen ist ist schlau oder kostet mich das zu viel Zeit ist das zu teuer und wie in kriege ich mit dass sich praktisch Schnittebenen hinzugefügt habe und die dann für weitere Probleme unter Umständen gelten ob und dann als bei am Start Möglichkeit neben der dualen Simplex Algorithmus als der bessere wenn man LPs löst und LPs löst man logischerweise bei brennten baut am laufenden Band nämlich in jedem Knoten und seine Schranke gut das Wort Menschen bauen keine große Hexerei in den Übungen werden sie da diese Woche auch mal wirklich Beispiele zu
rechnen und sich auch an einem Beispiel überlegen wo brennt scheinbaren Probleme bekommen kann wenn zum Beispiel können Sie mitreden kann also wenn es einfach keinen Unterschied macht ob ich es sind wir zu beschreiben ohne die Aufgabe direkt vorweg zu nehmen manchmal ist es so dass sich Variablen das in das Setzen einer einzigen Variable in die Mehr ein Problem die Lösung nicht kaputt macht sondern sie nur verändert praktisch nur manchmal wenn ich irgend G Währungsproblem Betrachter und hab halt 20 Farben wenn ist für den 1. Klon nämlich ein Verleger lautlichen grün oder blau oder rot ein aber weil es der 1. Knoten also es mir einfach wurscht welche Farbe dieser Knoten erstmal bekommt weil ich zu jeder Farbe die ich jemals 1. gebe dem Grafen immer noch ne Färbung finden könnte und solche Sachen kann man sich überlegen sind ich besonders schön also dann wenn es brennt schon bald nicht mehr so so hübsch gut dann kommen zum 2. exakten Algorithmus nicht vorstellen oder den wir diese Woche kennen lernen werden dynamische Programmierung und auch die die das jetzt vielleicht schon aus Informatik kennen wirklich hier müssen vorsichtig zu sein weil die Notation und die Art wie das hier aufgeschrieben werde deutlich anderes so viele von Ihnen kennen das vielleicht so Rucksack Problem mehr das man das und dynamische Programmierung lösen kann aus die frag mich was irgendwas aber es wird hier halt ein bisschen anders aufgeschrieben und wollen erstmal überlegen welche Prinzipien von Optimalität sind überhaupt not also sind nötig damit man dynamische Programmierung es Ansätze machen kann und wir bieten heute eine Formalisierung an diesen Listen anders als die die sie vielleicht schon kennen bei der dynamischen Programmierung ist der der wichtige Bestandteile immer dass man die Gesamtlösung aus Lösungen zusammensetzen können muss das ist sozusagen die Eigenschaft des Problems die wir brauchen damit wir dynamische Programmierung anwenden können der die das sicher prominenteste Beispiel für solche dass diese Eigenschaft hat das Teillösungen optimal sein müssen das kürzeste Wege Problemen dem Grafen wenn ich einen kurzen und kürzesten Weg von einem Knoten es zu einem Knoten The Suche in einem Graben ist ist klar dass ich auch für jedes ein Stück dieses Weges den optimalen Weg gewählt haben was den könnte ich einen kürzeren Teil weg zu einem Knoten i bin ich unterwegs passiere finden kann ich es auch insgesamt eine bessere Lösung finden so sagte wir ist ja guten das weil man seit dem zunutze machen in dem wir versuchen Teillösungen zu erzeugen und die dann eben zu gesamt Optimallösung zusammenzusetzen zu mehr zu die ich möchte dazu
gut bevor ich jetzt mit der Definition von dynamischen System einheimischen erst wenn die Karte zu mir der angelangt ich sage das hier wahrscheinlich die erst mal Formalismus so'n bisschen hereinkommen muss weil das hier wie gesagt ein bisschen anders aufgeschrieben wird gehören man möchte sich ja praktisch Weisung kürzeste Wege Problem das ist ein Beispiel das dann am Mittwoch wahrscheinlich auch noch also nicht nur wahrscheinlich sein sicher kommt am kann man sich ja praktisch kürzeste Wege mit einer gewissen Anzahl an kannten suchen und dann versuchen je nachdem ob man wenn man eine neue kannte zunimmt und zwar einen mit mehreren kannten belegten Weg geht aber vielleicht trotzdem dadurch den kürzeren Weg was die Kosten betrifft erreichen kann möchte man das über die Zeit so hatte nennen Form Zeitfaktor und möchte das dann immer wieder n überschreiben seine Lösung je nachdem ob man eben mit mit den neuen Möglichkeiten die man sich die auf den Weg eine bessere Lösung erzeugen konnte einem Rucksack Problem war das so dass man den Rucksack zuerst mit also Rucksäcke jeder Größe anschaut zuerst mit den Kleinsten Elementen auffüllt und schaut ob man je nach Größe des Rucksacks durch größere Elemente die man einfüllt bessere Lösungen für diesen Teil Rucksack erzeugen kann wenn man von Teil Rucksack ne bessere Lösung gefunden hat dann ersetzt man die auch in einem größeren Rucksack und so weiter und so fort formalisieren von mir dass ich hier mit dynamischen Systemen das ist und es ist klar dass man Länder Form ein Ende hat zum Beispiel beim kürzesten Weg man kann ich mehr als alle Kanten des Grafen verwenden um Weg zu finden und 2. Mann hat irgendwann man hat auf jeden Fall so großes The Bus vorbei ist dass man nicht mehr weitermachen kann sie für mehr es ist klar dass wenn ich zum Beispiel kürzesten Wege mit K kann suche dass es unter Umstän nur einen Weg mit K kannten und erst nach T gibt das heißt ich hab mehrerer Möglichkeiten deswegen sagt es gibt eine Menge von Zuständen zu jedem Zeitpunkt in dem sich das System finden kann und den Zustand in dem ich wirklich bin den verglichenen variabler diese einfach klein XT sein und eben aus dem großen so und jetzt ist die Frage wo wo optimiert man hier irgendwas und die die Mehr das was besuchen ist eine Strategie die wir von einem Zuständen einer Periode zur nächsten zum nächsten Zustand übergehen wollen ja so eine Art Übergangsfunktion dynamisch von Zeit Periode zu Zeitperiode und über die wollen wir optimieren über alle möglichen Übergängen und jetzt brauchen wir eben diese Übergangsfunktion Jamie die sind diese Zustände untereinander abhängig hier nicht ist n viel ja wenn wir möchten Abhängigkeit zum Zustand in dem wir gerade sind für die Variable Zustandsvariablen nächsten Schritt und von der Steuer Variable also unserer Strategie Variable nur und das soll dann so aussehen dass XT +plus 1 oh oh oh oh oh dass wir so unseren nächsten zu stellen immer beschreiben können .punkt
weiterhin als Annahme soll sein das ist wir keiner also in diesem Zustand XT soll wirklich alle Informationen die wir brauchen um die nächste Entscheidung zu treffen wie wir weitermachen wollen mit unserem dynamischen Programmen kodiert sein die wir brauchen wir sollen nicht weiter in die Vergangenheit schauen müssen ja dass es genau das mit dem Teillösungen sollen schon optimal sein dass man zu einer gewissen Teil Lösung gekommen sind und brauchen uns nicht so und wir müssen uns um den Rest sozusagen nicht kümmern sondern ein Detail Optimalität reicht uns um wenn insgesamt nur Optimalität aufbauen zu können das heißt die aktuelle das Akt der aktuelle Zustand des Systems ist ausreichend Informationen brauchen keine Vergangenheit Informationen Zorn am Steuer Variablen haben wir vielleicht auch irgendwelche Restriktionen Vox sie sollen also auch aus irgendeiner vordefinierten Menge jeweils Brotzeit Zustand sein und wir wollen NFC-Funktion minimieren und die soll auch additiv über die Zeit sein das heißt dass wir immer so wenn man praktisch wenden die optimale Lösung den Gesamt kürzesten Weg kann ich auch also den die Länge dieses kürzesten Weges kann ich mir auch aus der Länge der Teil Wege zusammensetzen mehr die bin zahlen soll die Gesamtziel Zielfunktion ebenso aussehen .punkt kann wir haben vielleicht irgendwelche Kosten ganz zum Schluss wenn um Endzustand angekommen sind gut 1. zusammen soll unsere Definition von einem dynamischen Programm sein es mehr wir starten Ländern Startzustand aus der Stadt Zustands Mengen wollen dass unsere Zustände unterwegs in den zugehörigen Mengen und wir auch unsere Steuer Variablen so wie wir unsere Anforderungen haben entsprechend werden und wir suchen diese diese Steuerungs Variablen so dass wir das das Optimierungsprobleme lösen wir wir brauchen wir dir diese funktionale Abhängigkeiten der Staaten im Startzustand und so weiter und dann für unsere Strategie entschieden haben wir unsere 10 haben wir haben über die funktionale Abhängigkeit immer nächsten den nächsten Zustand der des Systems ja und eine Strategie soll natürlich eben dafür sorgen dass nach dem ich diese funktionale Abhängigkeit ausgenutzt habe ich ja auch in der richtigen Menge Menge Lande nur dann wenn man solle Strategie zulässig und natürlich müssen meine Steuer Variablen aus den entsprechenden Mengen sein die wenn ich eben mit der Strategie meine funktionale Abhängigkeit lieber Rechner das sich dann in der richtigen Menge Lande dass sie zwar erst mal ziemlich naja
unbekannt aus aber man kann ne Menge Probleme in dieses in dieses Setting rein übersetzen und das schöne an dieser bisher 10 ist dass man ein Algorithmus hat gestern löst ja das man sich da haben nein überlegen kann der dann die optimale Lösung findet wenn wir unser Problem so aufschreiben können und zu diesem Prinzip der Optimalität schreib ich gleich noch was weil wie gesagt erstmal nicht nicht zu sehr davon abschrecken lassen und wir fühlen das spätestens am Mittwoch auch noch ein bisschen mit Leben wir haben also die Nebenbedingungen in unserem dynamischen Programm sind praktisch ein dynamisches System und optimieren also hier bei dynamischer Programmierung über einen dynamischen System jetzt hatte ich ja vorhin gesagt dass das
essenziell Leben ist dass man das brauch das sich die Gesamtlösung aus Teillösungen zusammensetzen lassen muss wie kann man sich das also wie findet man das in dieser Definition wieder Hits nix n wo .punkt angenommen wir haben so optimale Strategien und wir
betrachten uns jetzt so wie ich vorhin schon angedeutet hat nicht mehr das gesamt Problem sondern wir sagen einfach Mensch wir sind jetzt schon mit unserem dynamischen Systemen Zeitpunkt t angelangt wir haben sind einfach schon haben schon ne Weile was getan sind jetzt dort und wollen nur noch ab da wissen was passiert und .punkt ich in seinem Namen sind Zeitpunkt nein T und haben dann eben auch unsere 1. Perioden von The +plus 1 bis Großzeh abzuarbeiten dann muss auch die Teilstrategien ab dem Zeitpunkt des optimal sein ich kann und dafür ist es sehr mächtig das besondere 2. Additive die Funktion haben nur dass die sich da nicht überschneiden logischerweise ODS macht das keinen Sinn dass sich hier einfach nur ab einem gewissen Zeitpunkt betrachten das System betrachten kann und immer noch bei Teilstrategien Optimallösung rausbekommen ja und das bedeutet halt dass die Entscheidung zum zu einem Leben Zeitpunk unterwegs nicht von den vorher getroffenen Entscheidung abhängt mehr gut und das wollen wir uns zunutze machen um den Algorithmus dann zu finden mit dem wir das dynamischer Programm lösen können aber das war erst am Mittwoch
Untere Schranke
Obere Schranke
Zehn
Minimierung
Laufzeit
Heuristik
Optimierungsproblem
Optimum
Hausdorff-Raum
Lösungsraum
Computeranimation
Restriktion <Mathematik>
Lösung <Mathematik>
Variable
Vorlesung/Konferenz
Diskrete Optimierung
Schranke <Mathematik>
Unlösbarkeit
Nebenbedingung
Minimallösung
Untere Schranke
Punkt
Dynamische Optimierung
Baum <Mathematik>
Heuristik
Optimierungsproblem
Zahl
Lösungsraum
Ganzzahlige Lösung
Lösung <Mathematik>
Variable
Ungleichung
Minimum
Vorlesung/Konferenz
Schranke <Mathematik>
Lösung <Mathematik>
Variable
Untere Schranke
Punkt
Obere Schranke
Bewegungsgleichung
Machsches Prinzip
Besprechung/Interview
Vorlesung/Konferenz
Optimum
Raum <Mathematik>
Ganzzahlige Lösung
Schranke <Mathematik>
Lösung <Mathematik>
Variable
Untere Schranke
Obere Schranke
Spieltheorie
Ganze Abschließung
Besprechung/Interview
Heuristik
Vorlesung/Konferenz
Ganzzahlige Lösung
Schranke <Mathematik>
Finite-Differenzen-Methode
Punkt
Obere Schranke
Besprechung/Interview
Optimierungsproblem
Lösungsraum
Zahl
Ganzzahlige Lösung
Variable
Ungleichung
Ganze Abschließung
Rationale Zahl
Abschätzung
Schranke <Mathematik>
Untere Schranke
Simplex
Punkt
Baum <Mathematik>
Besprechung/Interview
Binärbaum
Variable
Ungleichung
Spielraum <Wahrscheinlichkeitstheorie>
Menge
Rundung
Verzweigungspunkt
Dualitätstheorie
Schranke <Mathematik>
Mathematische Größe
Formalisierung
Punkt
Euler-Winkel
Dynamische Optimierung
Besprechung/Interview
Element <Mathematik>
Optimum
Kante
Formalismus <Mathematik>
LOLA <Programm>
Übergang
Dynamisches System
Lösung <Mathematik>
Variable
Weg <Topologie>
Menge
Zustand
Vorlesung/Konferenz
Kantenfärbung
Variable
Länge
Rechenbuch
Menge
Zustand
Vorlesung/Konferenz
Zielfunktion
Optimum
Aggregatzustand
Restriktion <Mathematik>
Nebenbedingung
Dynamisches System
Menge
Dynamische Optimierung
Besprechung/Interview
Strategisches Spiel
Vorlesung/Konferenz
Optimum
Dynamik
Vorlesung/Konferenz
Frequenz

Metadaten

Formale Metadaten

Titel Exakte Verfahren I: Branch & Bound, Dynamische Programmierung
Serientitel Diskrete Optimierung (Optimierung II)
Teil 19
Anzahl der Teile 26
Autor Nowak, Nicole
Martin, Alexander
Lizenz CC-Namensnennung - keine kommerzielle Nutzung - Weitergabe unter gleichen Bedingungen 3.0 Deutschland:
Sie dürfen das Werk bzw. den Inhalt zu jedem legalen und nicht-kommerziellen Zweck nutzen, verändern und in unveränderter oder veränderter Form vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen und das Werk bzw. diesen Inhalt auch in veränderter Form nur unter den Bedingungen dieser Lizenz weitergeben.
DOI 10.5446/31777
Herausgeber Technische Universität Darmstadt
Erscheinungsjahr 2009
Sprache Deutsch

Inhaltliche Metadaten

Fachgebiet Mathematik

Ähnliche Filme

Loading...