Merken

Ungleichungen mit Struktur: Das Rucksack und Set Packing Polytope

Zitierlink des Filmsegments
Embed Code

Automatisierte Medienanalyse

Beta
Erkannte Entitäten
Sprachtranskript
mal Monte sagen Harms die so herzlich
willkommen zur heutigen Vorlesungen über uns das letzte Mal bekommen geschnitten beschäftigt rauf und runter sozusagen also erst mal lesen klassischen in Plätscherbach Moorrege Schnitt er sich nennen und dann die Verallgemeinerungen zum mit indischer Kommune Schnitt beim in der Java das Argument einig wir lief einfach wir haben eine in ganz speziellen Quartal schnitt erzeugt unseren Dank war gesagt dem Monster ganzzahlige linke Seite wenn die rechte Seite gebrochen ist ,komma die abrunden und genau das hat Kommode gemacht denn es an die Weber zu sagen wir können aus dem Simplex direkt an solchen Schnitt ableiten und damit kostet uns das praktisch überhaupt keine aufwenden müssen keine über Basen also in keiner Seitenflächen Urin und dergleichen mehr Sonne können eigentlich direkt ein ablesen wenn man kann auch mit dem Verfahren zeigen dass es genauso endlich ist wie wie der der Quartal Ansatz auch also das spezielles herauspicken man letztendlich muss man Schluss auch Aldi Silber Basen Elemente in wenn man denn dieses Ähnlichkeits Argument fahren will ja aber es ist natürlich von algorithmischen Seite deutlich interessanter weil man sozusagen direkten Schnitt Geschenke und und damit sozusagen in der Prozedur hat mit der man immer weiter etablieren kann und letztendlich nachdem das Ähnlichkeits Argument hat reicht eigentlich diese Verfahren auch damit Data sich ganzzahlige Probleme zu lösen und das letzte Mal ein bisschen diskutiert was für Schwierigkeiten da gibt das ist in der Praxis dann doch nicht geht dass ich ständig die Schnitt Anwender und immer wieder an Wände weiß aber zur numerischen Problemen führt weiß der große oder gebrochene werde auftreten können und das 2. ist dass die Ungleichung die Tendenz dazu haben das ist sehr dicht sind was in der Regel dann das Lösen der linearen Programme und insbesondere natürlich der Gleichungssysteme aufwendig und teuer machen die Idee mit dem einfachen runden funktioniert nicht mehr so weil wir kontinuierliche Variablen haben da klappt wieder das runde Argument von Quartal ein gerechtes sei runden oder das Addieren beliebig viele skalare ganzzahlige skalare bei kontinuierlichen Variablen beides den Lösungsraum verändern würde und da man an das Argument gefahren zum bis zum dieses Argument wenn gesagt wird sich zerlegen zu sagen unsere unser Politiker in 2 Teilen bestehen jeweils würde und bleiben für den einteilen mitgelie für den anderen und basteln aus diesen beiden Ungleichungen eine die das gesamte gültig SMS Argument war relativ einfach kleine gleich Bedingungen haben nämlich immer komponentenweise den kleineren Koeffizienten auf der linken Seite und und dem Gewinn was größeren Kollwitz 10 auf der rechten Seite bei größer gleich und gleich genau umgekehrt war damit gesehen dass man tatsächlich damit eine Verallgemeinerung dieses ganz sagen ,komma Durchschnitts bekommt der sogar stärker ist als als der ursprüngliche ganzzahligen in der Tat so dass diese Schnitte auch heute praktisch in jedem gängigen Code Aubert Forschungsgruppe oder kommerziellen kodieren alle eine Variante dieses Korps in dieser dieser Gemisch ganz Kommune steht implementiert gibt es bis dahin noch Fragen vom letzten Mal gut wenn das nicht der Fall ist dann wird morgen enden bis den andern Fokus auf diese Schnittebenen kriegen wir haben bislang und ebenso wohl ,komma wurde als auch Quartal sind von dem Typ gegeben die Matrix und ist völlig egal woher die Struktur dieser Matrix kommt ich nehmen also die Matrix wie sie ist und generiert daraus im Schnitt man kann jetzt sehr viel man kann es auch ein 2. Weg gehen und sagen dass es kommt ganz konkret die Struktur dieser pro Leder anschauen und können wir aus diesen Strukturen was lernen und können wir aus diesen Strukturen Rückschlüsse auf die politische Struktur schließen und das ist ein Gebiet was sich an Anfang der siebziger Jahre auf dem Weg gemacht hat und einige bis bis Ende der 90 er so richtig Euro war und ist es sehr sehr viele Veröffentlichungen gaben genau in diesem Bereich praktisch zu allen klassischen Problemen oder auch aus Anwendungen und Anwendung sei der motivierten Problem hatten versucht diese politische Strukturen besser zu verstehen dass Reisende sind wir alle ein gutes Verständnis wäre natürlich eine vollständige Beschreibung zu kriegen aber gesehen dass es im Allgemeinen zu schwer es aber ist kann er es reichte häufige partielle bescheiden zu finden und die beste Beschreibung die man kriegen kann sind solche in Form von Fassetten definieren Ungleichung also solche um gleich den maximalen schnitt mit dem Politiker haben das selten die Facette und da gab es ja diesen Entwicklungen eines der bekanntesten Beispiele sehen das ist allerdings ist mein Problem war das vom klassische Rundreise Problem sie am 50 Städte sagen wir mal sie starten in einer Stadt und Sie möchten jetzt die Reihenfolge so bestimmen dass die gefahrenen Kilometer minimiert werden weil es ist das Verdienst ist ein Problem das es unendlich schwer das Problem was im Unterschied zum kürzesten Wege Probleme ich möglichst schnell von A nach B will ist ein einfaches Problem für die englischen Grafen Algorithmen oder Nebenfach Informatik haben sollten solche Algorithmen schon kennen ein es ein Problem ich vor geht doch welche ich -minus und die Reihenfolge ausführen will dass es unendlich schwer das Problem nur heute in genau mit dieser Technik dieser Schnittebenen Generierung die sich über dich entwickelt hat eigentlich sogar schon in den Fünfzigern es gab 54 von Danzig vor gelassen und schon sind die die Grundideen dafür entwickelt haben und daraus hat sie in den letzten 50 Jahren Einverständnis des zugrunde Polyeder sind wie die dass man heute die SPD ist praktisch in jeder beliebigen Größenordnung lösen kann also dann wenn sie dann mal Lust auf die Display-Seite zu zugucken denn sie mein googelt TSB ist ein und Unglück oder so dann kommen Sie auf die Display-Seite die von Bill Cook gepflegt wird da sehen Sie die aktuellen Weltrekorde purzeln der Zeit dieser so knapp bei 90 Tausend Städten wenn sie überlegen wir Variablen des sind 90 Tausend Knoten Grafen haben sie haben erlauben alle potenziellen Verbindungen Dance n n über 2 viele kannten das heißt ein cooles 99 Tausend mal 45 Tausend kannten welche 90 Tausend und 40 Tausend Variablen das ist dann Größenordnungen wie viele Nullen 8 Nullen also also Anzahl war ja wenn 10 auf 18 Wochen 9 in der ja und Sitz überlegen wie wir denn er war ja müssen entscheiden 0 oder 1 haben 2 hoch 10 hoch 8 potenzielle 0 1 Belegungen es sind mehr Lösungen als Atome im Weltall gibt es aber trotzdem gelingt es mit diesen Methoden die beweisbare optimales um zu bestimmen und das beruht letztendlich genau auf diesen Schnitt in den ansonsten hat bist allerbestes Best studiert das Depot Lieder ist dieses dessen Polit gibt es Unmengen an versetzen und gleich 7 zu analysiert hat und dann auch die zugehörigen dabei die lungsverfahren das heißt wie man sie gut separieren kann also algorithmisch behandeln und dann sieht man also welche Spannbreite der möglich ist wenn man kann also das sind die Bereiche wo man heute am weitesten vorgedrungen sind Probleme die man heute gut lösen kann es gibt auf der andern Seite auch welche über uns fehlt auch noch angucken es gibt auch waren Probleme mit 5 Variablen die heute noch keine lösen kann also da ist mir diese Spannbreite in dem Bereich ganzzahliger Programmierung und das ist vielleicht auch zum bisschen das spannende aus einerseits natürlich sozusagen diese Spannbreite von was kann ich löst das kann ich nicht lösen die Fragestellung sind oft intuitiv aber die die Antworten dazu teilweise richtig knifflig und schwer und das Kleid aus ein bisschen
Faszination von dem Problem und was wird heute in dieser Vorlesung machen und so ein bisschen an der Oberfläche kratzen zum 2 klassische Probleme anschauen und so ein bisschen in diese Kultur einsteigen wie gewinnt man steht eben wie beweist man die Fassetten Eigenschaft ist wird man sowas und das wollen wir exemplarisch an 2 Dinge machen einmal einem Rucksack Problemen und einmal ans Herz legen und aber die Probleme haben wir beide in der Einführung schon mal kurz angerissen diese beiden Probleme gut und schauen uns das an also das ist dann das Kapitel 3 1 2 Ungleichungen mit Struktur und wir fangen an mit den mit dem Rucksack Problemen also das Rucksack Problem mehr wir schauen uns das Polyeder dazu an wie sieht das aus ist die Definition 3 1 3 18 war so Pk das mal hier unten für K soll fernab SEC stehen n soll folgendes sein soll die Menge aller X aus 0 1 hoch n sein unter der Nebenbedingung Summe XJ kleiner gleich B und die aus allen so es aber wissen Vektor aus dem hoch n +plus b ist eine Zahl aus Einfluss und das ist das klassische Rucksack Problem so wie wir es kennen gelernt haben da haben wir zusätzlich natürlich noch mit Zielfunktion gegeben oder gesagt haben maximiere c't iX unter der Bedingung ATX kleiner gleich wie wenn man so möchte ist es ein Stück weit das einfach Anzeigeprogramm was man sich vorstellen kann man in nur eine Nebenbedingung und dabei war natürlich dass auch von Beginn an auch gerade dieses Polittalk von besonderem Interesse das so was hab ich hier noch einen Fehler gemacht das ein Skript der Fehler wir sollten hier aber Ankunft der vorschreiben wir also wollte ich die konvexe Hülle aller 0 1 Vektoren das gibt uns ein Prolet einer gewissen das haben wir ein Kapitel 2 gemacht hier gibt es endlich viele konvexe will endlich wieder mit Toren ist wieder ein Pole jeder Missstands genau die an diese Randbedingungen für so zusätzlich und das ist er ja und auch angeguckt und werden ich glaube Samson Einführung gemacht damit die Apple Erzielung von diesen Dingen anschaut was kommt da raus also was wird da typischerweise gemacht wenn nicht schauen uns mal also eine beliebige C-Funktion an maximiere CTX ATX kleiner gleich B wenn ich mir das so anschaue x größer gleich 0 das wäre die LP Relax jung was kommt innerhalb der Lachs Sicherung raus sehen wir die Lösung ohne dass man Simplex laufen lassen oder lädt sie Methode die Frage ist welche Parklicht sozusagen eine welche B welche Elemente würdigte die man das sozusagen als Gewichte nehme das mutmaßen Rucksack das die Kapazität des Rucksacks werde angegebenen Kilo von mir daraus dann die Sie haben eine Reihe von Gegenständen die Sie mitnehmen wollen sie müssen entscheiden wer in dem Sinne Einsicht nehmen wird ich nehme nicht mit wenn Sie es mitnehmen steht hier wie viel frisst das an Kapazität Kilogramm wer in der Zielfunktion unterdrücken auszusagen was ist der Mehrwert für Sie oder persönliche gewinnt sozusagen wenn Sie dieses einpacken oder andere Mehr realistische Fragestellung diesem Budget ausgedrückt in Europa zu wollen verschiedene Projekte investieren das er aktive kostet das Projekt ist sehr zeigt Ihnen wird was es meiner war der Ertrag von diesem Projekt ob und welche Projekte investieren setzt so wird was macht man typischerweise wenig essen wir der Erziehung anschauen man schaut sich das Verhältnis von CIA zu einer Art an weil das ist sozusagen dieses Verhältnis sagt er mehr was bringt mir das pro einhalten muss die Werte hier alle nur noch vom normieren und dieser Ausdruck dieser Koeffizient sagt mir was es mein erwartete Gewinn pro Einheit ja nach dem sortiere und wir können ruhig so annehmen dass der mir so S C H C 1 A 2 ist größer gleich C 2 a 2 und so weiter ja und dann wird folgendes die Lösung sein wenn man packt natürlich erst wenn ein so gut es geht dann den und so weiter und irgendwann stößt man die Grenze wenn noch ein bisschen Luft es dann packt man den letzten Fraktion war um einen Teil der noch so viel wie viel noch auf Luft ist aber nachdem ich ja kontinierlich rechnet kann ich ja sozusagen die die Variable die jetzt gerade am überlaufen ist er kontinuierlich will und auch dem gerade den Anteil der noch fehlt und das P aufzuführen und Einführung ist also wenn ich die Vorlesungen machen als Übungsaufgabe dann auch zu zeigen dass es tat sich die optimal die optimale sind Apple-Aktie ist diese LPs und kann es einfach nachweisen man zum Beispiel tualisiert und sich dazu die duale Lösung anguckt dann bis Mehr LP Dualität muss übereinstimmen so also das heißt wenn 1. ganzzahlige anschauen wollen da ,komma nicht gleich auf das 1. Konzert von Ungleichungen bisher wenig schönen dieser LP Galaxie gerungen was geht dann da schief also warum bricht der mir diesen letzten nur wenn's dumm läuft kann also schauen wir mal so vielleicht sogar ein konkretes Beispiel an weil sich nicht maximiere 4 x 1 machen hier um das ganz einfach 4 x 2 +plus 4 x 3 und das muss man schauen dass das am meisten bringt also muss sagen wir hier der 3 x 1 +plus 3 x 2 in nochmals etwas teurer +plus 4 x 3 kleinen gleich 7 so wenn man nach dem nach
der Strategie Vorgehen ja dann sind die beiden gleichwertig die haben falls sie kurz den betrifft den höheren Wert also wird die Erziehung so aus den den auf 1 setzen denn auf 1 setzen das habe ich 6 Einheiten schon verbraten 7 hab ich nur noch frei aber ich konnte mir nicht denken kann ich hier bin das entsprechend auffüllen also mal hier noch ein Viertel ja dann hab ich genau die 7 ausgefüllt und das ist meine Galaxie so und woran liegt jetzt das Mehr und mehr und setzt diese Menge anschauen ja alles sehr genau die 3 zusammen wenn man die aufaddiert passen nicht rein und so eine Teilmenge die Zuse wenn ich die auch so mir nicht da rein passt es mit meinem Körper die überdecken sozusagen diese Kapazität aus dem englischen Kabel überdecken so ist es offensichtlich dass sie aus und kann man nicht alle nehmen kann weil wir genau die Menge überdecken nein sie diesen Wert des überdecken und es gibt Anlass gleich zu dieser zu der 1. Ungleichungen auch zu dieser 1. Definition um ich also eine Teilmenge also C Teilmenge von N falls Kara falls diese wird lang dauern also die Summe der A J J aus -minus das B ist echt größer und also die überdecken diese Menge W und der Karwoche ist minimal CHS minimale falls AJ größer gleich Lander ist für alle J im C ja das heißt ich darf keine von den heraus lassen also minimal sobald ich ein Jahr raus passen sie eben alle schon deswegen immer nur es genau die Eigenschaften die EU abgesagt werden anders zu und da steht man gleich die 1. Ungleichung in dem Satz 3 20 da geht auf viele Leute zurück also wir haben ganze Reihe von Leuten unabhängig entwickelt einmal Ballast Ahmad Chancen Pelle Padberg und sie alle Mehr der gleichzeitigen also 75 die gesagt haben die Kaaba Ungleichung also seit c ein Körper ja und dann ist und Sorge um sieht so aus Summe über alle J Inc XJ alle gleichzeitig darf ich nicht nehmen das heißt es in Ungleichung zu formen nicht ich mir hab ich höchstens davon die Kardinalität von dem ,komma -minus 1 fielen die also das heißt die Ungleichung ist gültig und definiert Facette also gültig für dieses Polyeder Pk n und definiert eine Facette von Pk sonst schwerlich hier aber nun C also aufpassen und also Fassetten Eigenschaft gültig ja für alle auf vor allem natürlich Facette erstmal nur auf diese Teilmenge der CES das war also immer noch die Eigenschaft und falls ziel es sogar falls 10 Machart wir daher brauchen wir diese Eigenschaft so viel weiß man sowas die also Gültigkeit es offensichtlich der eine kommt aus der Definition nach dem alle Ländereien passen so weiß Fassetten Eigenschaften also müssen wir denn tun um nachzuweisen dass der Ungleichungen Facette ist können Sie noch etwas mehr Facette genau wir machen hier versuchen ein dreidimensionales Bild das mehr hören also fast selten werden in der Einführung dann die Charakterisierung von Fassetten fasteten sind die maximalen Seitenfläche wir also in den dreidimensionalen Fall eben so eine Fläche also maximal bezüglich Inklusion ja die kleinsten Seitenflächen also und wenns Polit Truppe sind sind über die Ecken ja die Hand mention 0 kannten Demission 1 und die maximalen seine Flächenland Dimension des Politikers -minus 1 Thomas nachzuweisen dass eine Facette haben was müssen wir tun wir müssen eigentlich genügend vieler wenige Punkte finden auf dieser Fläche das ist das was wir tun müssen also nicht die Dimension als wir sie mal die Dimension vom Polier bestimmen was uns keiner und wäre sozusagen die man so eine Facette bestimmen weil es die 1. sei die wir brauchen ja was oder also es ist die Dimension von diesen und diesen hat ob sagt Rohleder vor also Eigenschaft für wir bleiben jetzt erst mal in dem Bereich nur auf dieser Menge C was ist Daddy
Mention ich habe wie viele leeren Abfindungen Menüpunkt der Double 10. was in der einfachsten wer sich ausdenken können Einheitsvektoren waren ich nehme einfach mal ein Element dar also wird aus wenn ich mir die Menge C anschaulich kann jeden einzelnen eingehen will muss ich aufpassen dass es ARJ kleine gleicht dem ist ja aber das ist außer wenn es ja größer als den besten kann auf keinen Fall nehmen muss sie sowieso auf 0 setzen kann es gleich aus dem Problem schmeißen Nase können davon ausgehen dass alle a j e individuell Ajax kleiner gleich den besten das heißt jeder Einheitsvektor ist Lösung also da man den unabhängigen und unabhängigen also des Dinges voll dimensional da hallo also Dimensionen wirken sie haben in dem Pferd so also müssen wir jetzt um es nachzuweisen dass es wegen der Facette ist dass mir jetzt seh auf wie unabhängige finden und da wendet man gerne kleinen Trick an um das nachzuweisen ist Mann in hohen Emissionen müßig sich jetzt erst mal um CON entfiele Punkte auszusuchen dann sich diese Matrix anzugucken hat die volle ran und wir werden und das auszurechnen macht es gern auf individueller Basis also sagt man versucht sich 2 Lösungen auszurechnen und dann versuchen die Koeffizienten einer Facette zu bestimmen die die ist wissen auf jeden Fall diese Ungleichung ist gültig also wissen wir sehr sie selber schon etwas es immer fertig wenn nicht ist sie auf jeden Fall eine Facette enthalten war also selbst wenn setzen wenn es nicht mehr um gleichen über die nur als Schnitt diese kannte hat dann gibt es eine viel größere Seitenfläche die genau diese enthält und wir schauen uns mal an also sei wir transponiert X kleiner gleich da eine Facette mit so die Menge aller x aus P so dass die Karre Ungleichungen die aus 10 x E gleich 10 -minus 1 soll enthalten sein in der Menge alle x aus P der Transfer X gleich bester an also das muss eine Facette beginne Kündigung eine Facette ist so dass diese Inklusion will nur sollen einmal dieses Ding die Seitenfläche F und die da hinten erst viel so um das was Vista wenn dafür Wenzel wenn es Polyeder voll man zumal ist dann ist eine Facette es ist mir fast die eindeutig bestimmt bis auf Skalare vielfachen war zwar einen dieser Charakterisierung man Einführung kennen gelernt haben die ungleiche diese Facette wenn sozusagen sie bis auf das Calamares Vielfaches festgelegt ist dass er mir keine Freiheitsgrade werden soll das heißt es reicht wenn ich jetzt sozusagen diese Koeffizienten bestimmen kann man nicht nachweisen kann dass der NGO 10 bis auf ein Vielfaches genau die gleichen sind wie die wenn ich auch fertig werden umgehen und wie macht man das wir schauen uns einfach mal 2 Lösungen an also wir schauen uns morgen ,komma an seit sie also C ist minimal ja wir schauen uns zwar und mehr Bürger betrachten wir definieren das soll gleich 10 ohne dass eBay Element sein und können wir wissen aufgrund der minimale tät cm passt oder ein Jahr so das heißt wir wissen aufgrund der minimale täte wenn sie den Zweck davon VII passt in das Politiker rein ja das mal des 1. und wir wissen auch aufgrund gleich mal 1 mal ausgenommen der für das Ding auch mit Gleichheit der und die von CE er ist ein Element und diesen FAA so das heißt aber und wir jetzt schauen uns das hier an wie diese Inklusion das natürlich auch das ist ein Element von FB nun soll das heißt wenn wir uns das mal anschauen einerseits habe ich wir transponiert Chi ich Chi um C =ist gleich Peter das wissen wir und wir wissen auch noch das B transferiert wie oben CJ denn anderes J Billard ungleich i auch bei der es um diese Szene die beiden voneinander ab was bleibt übrig n wir sind überall gleich dieser an 2 Stellen der Film des IE und dem Filter Sie J also bleibt er stehen Ort -minus B E und auf der rechten Seite 1 0 ok also wissen RB =ist gleich Bj und dann wissen wir dass die muss Facette sein ja wenn BE gleich BJ das heißt die ganze linke Seite =ist gleich hier wirklich überall der gleiche Koeffizienten wir wissen ja wir mussten bis auch ein Skalar es vielfach als die Eindeutigkeit festlegen das heißt wenn man doch Bett teilen genau die Struktur von hier das heißt es muss eine Facette gewesen ok ich also dass es eigene da oder ein gängiger Trick umfasst hätten Eigenschaften nachzuweisen und man kann immer sozusagen mit 2 Lösungen argumentieren haben und konstruiert sich 2 Lösungen versucht man möglichst gleich zu machen bis auf wenige Komponenten dann zieht man die von ab und zu mit klicken man sukzessive was über die Koeffizienten dieser Fassetten definieren Ungleichung raus und am Schluss stellt man fest ich die alle festgenagelt alles sah ich genau die die ich haben wollte also zu einer dieser klassischen beweist Ideen über fast jeden Eigenschaft nachweisen wie funktioniert er ja auch er ist sehr sehr häufiges einig auch glaub ich die meist verwendest der der Strategie ja das wir ihr minimal voraussetzen müssen es auch immer klar ja aber wenn nicht minimal werde wenn man also zudem minimal es notwendig aber denn sonst immer Folgendes dann immer noch diese Ungleichungen Zunge je aus C X einer gleich 10 -minus 1 Jahr westlichen J J aus C mit C-One J ist immer noch unklar war so muss geben weil der Körper nicht
minimal war ja wenn ich das jetzt hier aber sie brauchen wir kommenden überlegen also nicht dieses J ein ganz falsch herum zu falschem argumentiert Sekunde machte so noch mal weg durchführt also wenn 10 minimal notwendig also ich muss anders umarmen will angenommen sie nicht minimal ja dann gezielt Teilmenge die minimal ist also es sei Zielstrich Teilmenge von C wie war beim gilt folgender Zusammenhang mein Geld wenn ich mir das anschaue Summe wie aus C sprich XII kleiner gleich Zielstrich -minus 1 ist die Kawa Ungleichungen und dann gibt es noch die Ungleichungen XJ kleine gleich 1 für J aus C-One Zielstrich ja das die obere Schranke ich 1 0 1 2 Jahre her weil ich die zusammen an der auf der linken Seite genau I aus 10 x J und auf der rechten Seite gehe ich genau kleiner gleich 10 -minus 1 nur das heißt diese Ungleichung ist eine Summe von anderen ungleich und damit kann das keine Facette sein wenn der können maximal das hier fast 1. sein wenn ich 2 Facetten an dir komplexes bekannte oder so oder aus aber ich noch meine Facette also das heißt die die Voraussetzung ist aus in dem Sinne notwendige hinreichend allerdings haben unser bislang nur eingeschränkt auf auf das Ziel wir bislang wissen wir nur dass man fast hätte wenn ich mich einstellen auf die auch diese Kammer war ja die Frage ist kann ich daraus auch eine Ungleichung machen eine Facette machen die für das gesamte Polit also auf der gesamten Index Menge in das geht es schauen ausbleibende Übung an wandelndes sozusagen dürften also Lifting Prozedur anfängt mit diesen Teilmenge Anfang der weiß was eine Facette ist das versuche ich die Grundidee ist zu sagen ok Zwillinge neue aber drin haben von der kenn ich den Koeffizienten nicht das Versuch ich den zu maximieren meine war ja alles ist der Koeffizienten meint die Funktion des maximiere den 10 der neuen Variablen und so das ist nach wie vor gültig bleibt wenn das wieder ein kleines Optimierungsproblem es ,komma nur sehr geschickt und einfach lösen aber hat mir diese Eigenschaften wenn man dann diesen maximalen Gerät 10. wählt und bleibt eine Fassetten Eigenschaft erhalten ja man hat vorher sie viele auf unabhängige jetzt kommt eine neue Variable dazu Krieg eine Lösung dazu nämlich genau dort wo das Maximum angenommen ich maximiert diesen Koeffizienten dazu gibt es eine Lösung und diese Lösung muss unabhängig sein von denen ich bislang hatte wirklich automatisch die eine Dimension mehr die braucht damit er halte diese Fassetten Eigenschaft ja und danach dann ist er das immer sehr klein Optimierungsprobleme lösen muss wegen eines den Koeffizienten das kann man bei beim Graber sehr geschickt und einfach machen aber auch dazu dynamische Programmierung das schauen wir uns erst im übernächsten Kapitel im nächsten und übernächsten Kapitel an immer genau dynamische Programm wiederum war aber mit dynamischer programmieren kann man hier dieses Lifting in Polen Zeit hinbekommen und legt damit auch aus einer Facette die jetzt erstmal mal für die Substruktur gültiges der Facette für das gesamte und wenn wir jetzt noch mal aus aus aus politischer Sicht uns das anschauen warum es immer interessiert an dieser Fassetten Eigenschaft wenn wir nachweisen können dass eine Facette haben dann wissen wir auf diese Ungleichung können wir nicht verzichten das ist eine von den wesentlichen Umleitung der sich an die Einführung dann werde man nicht reden dann der also Beschreibung kriegt man da doch in dem die Facette eine bleiben dabei hat wenn es nämlich nur bekannte Bescheid auf die können Sie verzichten auf die Fassetten können Sie verzichten das heißt wenn sie wirklich nicht einer der vollständigen Beschreibung gehen wollen ja dann müssen sie alle diese mitten im kennen also vielleicht noch ein Beispiel dazu ich hab hier verschiedene aufgezeichnet aber ein Beispiel war ja auch schon hier in dem Fall wäre uns das kleine Beispiel nochmal angucken als in dem Fall wird sie eben gerade die Index Menge 1 2 3 wir auch minimal nur mal eben eine sehr wenig Auslass pastoralen und die ungleichen sieht dann eben aus x 1 +plus x 2 +plus x 3 kleiner gleich 2 in das ist die Kawa und gleich wir sehen schon beim 1. Mal kommt wieviele gibt es denn was uns jetzt natürlich interessiert eigentlich noch einmal der theoretisches seidige nachgezahlt ok das sind wichtig um Gleichungen aber das ist natürlich algorithmisch verwenden wollen dass man noch Kelvin ich die also stellt sich die Frage gegeben weckt er es allgemein dabei das Problem die man weg da entscheide ob dieser weckte alle diese Kammer Ungleichungen erfüllt und man nicht geben den verletzten Körper oder auch bezogen auf die LP der Erziehung wenn man sozusagen über die LP der Aktion gegen die die gegeben optimale Galaxien und entscheide ob der All diese Carola unerfüllt und wenn ich gewinne Verletzte ist Problem wir ich ist es nicht kann also nachweisen eines dabei dieses Problem für die Karbaum Essen enthält vollständiges Problem endlich schweres Problem haben bei dem beide Fälle dass wenn ich sage ich hab DLP-Lösung vorgegeben es schwer oder wenn ich gar nix vor gibt es auch schwer das eine Art während seine Situation 98 gezeigt in dem Hause und Koautoren unabhängig n 3 Jahre später für den LP Fall sich Apple so vorgehen und das ist nur ein Bruchteil der um den es tatsächlich gibt man sich mal es gibt zu Tools die alle und Sohn Polittalk aus geben Polemik ist und es eine Software zum Beispiel die auch der Kollege Michael Joswig entwickeln mit der können Sie sich einfach mal sagen es ist und ganz heiß Programm eingeben und 7 alle Facetten ausspucken lassen wenn sie sehr leid fest und Rucksack Problem gibt es Tonnen von Ungleichungen untergrabe Anteil ist vielleicht 5 Prozent wenn überhaupt also will man ist bislang weit weg weit weg von einer vollständigen Beschreibung von diesen Rucksack Problemen sehr ich die Frage woran liegt das wäre man letztendlich in der verbirgt sich hinter dem Problem eigentlich auch zahlentheoretischen Fragestellungen was sie möchten hier man kann zwar einerseits sagen mir dass nur Einigung Gleichnis das einfachste was man sieht aber letztendlich mächtig hier eine gewisse Zahl 0 1 kombinieren also Partitions Probleme stecken da bei denen also wie kann ich zum Beispiel der Ausfall von Zahlen finden sie eine Menge von Zahlen gegeben sie möchte so
partitionieren dass beide Seiten gleich groß sind steckt auch in diesem Problem drin ja oder es Frobenius Problemen sie aus 0 1 ganzzahligen machen was ist die kleinste Zahl die sie nicht aus diesen kombinieren können aber diesen Größe können Sie jede Zahl doch ganz zeige gefiel kombiniert was die wäre es die größte Zahl die nicht kombinieren können er als solche Fragen können Sie mir diese in diesem Rucksack Problem verstecken die auch sozusagen in anderen Bereichen der Mathematik von Interesse sind aber für uns noch mal natürlich wie wichtig hier eines der Strukturen die so insbesondere dahin gehend wichtig weil im Rucksack steckt in jedem in jedem ganzzahligen Programm warum also wenn ich als kleiner gleich be gegeben hab ich's ganzzahlig weg so x größer gleich 0 am Stecken Rucksack in dem von diesem Problem ab kann n wer was können wir machen wir nehmen jede einzelne Zeilen der Matrix immer raus wie schauen Sie der 1. Zeile an ja nie 1 Liedzeile ist von dem Typ Summe alias XJ kleiner gleich und der rechten Seite wenn das ein was es noch passieren kann dass die der größer gleich 0 sind ja ein paar positive war negativ sind mehr und es stört uns das wirklich was uns beim komplementieren mal die Variable aus XI nach man 1 XI wenn dann steht da J mal 1 -minus x is Eier waren negativ mit IS XI machte sind pro große positiven Koeffizienten und des Eier stecken auf die rechte Seite dann haben wir genau das dürfen weg und eine Mama die komplementären wieder das heißt in jeden ganzzahligen Programme stecken Rucksäcke und das ist das was auch gemacht wird der Mann geht dann die kurz gehen teilweise doch die Matrix und schauen kann ich da draußen IPSec machen ja und dann versuchen sie Graber und andere Ungleichung anzuwenden so was was wer was natürlich häufig der Fall ist dass man diesen gemischten Fall hat also nicht nur eine Anzeige war ja besonders auch noch kontinierlich auftreten und dann klappt es ja wieder nicht mehr direkt das Argument wenn man dort wieder kontinuierliche dabei sind dann aber er gesehen auch an dieser Apple-Aktien dann können wir ja brechen und dann kann man den einfach hier um 1 aber unten ja nichts mehr und da muss unseres anders überlegen aber es gibt auch eine Erweiterung auf auf kontinuierliche Variablen die wollen uns ein bisschen angucken dies wird gleich etwas komplizierter aber kann nur andeuten dass sozusagen häufiger auch von den kombinatorischen jemand sie entwickelt es entsprechende Verallgemeinerung auf dem gemischt ganzzahligen Fall also sowohl ganzzahlige variabel also kontinuierlich auftreten also schauen was es mal an wir schauen uns hier so ne Menge an es seine mit X und es es sei jetzt nur eine Zahl also viel die wir diesen x-Wert aus 0 1 hoch n Kreuz +plus also wir schauen uns genau eine kontinuierliche Variable an und schauen dass wie folgt an so eine Art XJ kleiner gleich G +plus S und J aus aussendet eine sollte man konferieren der Stelle nicht aber also wenn man mehrere konnte die über ja hat dann kann man die wirklich alle in einer versteckten erreicht man alle kundendienlichen zusammen so wie auch wenn ich nur eine Ungleichung ab und versteckt die allen Design und Umlandes wie Sie das hier ist zwar speziell aus aber nicht dieses Polyeder verstanden aber das zugehörige Polyeder dann kann ich das sofort wieder als der gleich eine Matrix anwenden denn ich alle kontinuierlichen Variablen diese in dieser einen Kollegen Mai habe es versteckt also gibt setzen auch entsprechend Graber Satz ist der Satz 3 23 der geht auf Moorsee und Maschaal zurück 1900 99. sehen wir ,komma also schon immer näher an unsere Zeit daran die Ergebnisse die wir so langsam haben sind nach vorn gar nicht allzu langer Zeit sozusagen entwickelt worden also seized aber weit aber genauso definiert ist wie das 1 definiert haben egal ob meine Kunden im Wahljahr dabei haben oder nicht wir scheinen uns aber in dem Fall ein will ich freue mich doch eine an dieser Stelle wir stellen uns ein auf diese Menge es wasn't Graber betrifft man kann das Konzept auch arbeitete konnte war jahrelang ist dass man außen vor sondern dann ist schauen die Ungleichung an mir und das machen Minimum ihren Lander XJ Willard aus 10 kleiner gleich zum wäre er hat aus 10 Minimum war AJ Landa mir Auslander +plus S diese Ungleichung ist gültig und definiert Facette gültig für gültig und definiert Facette das die konvexe Hülle vorne es geschnitten wenn alle x wobei XJ gleich 0 ist für die Haut aus n ohne C also auch hier schränkt uns wieder ein auf die Menge auf dem Grabe sowie im anderen Fall auch der Unterschied hier Unterschied hierzu oben ist wenn
sie schauen hier hab ich nix Animalität gesagt hab ich ein Ankara genommen ja ist und es ist auch dazu die so dass sie jeder Körper sobald ich kann immer haben dabei hat jeder Karami eine Facette definiert nur so dass wir schon wissen will aus was hier steht als vorher und schauen uns mal an warum das denn überhaupt gültig ist die versenden Eigenschaft sie schenken uns die können sehr gerne danach komme es aber im Wesentlichen uns auch auf dem Konzept was sich was sich Omama dargestellt hat also müssen es dieses Minimum und wie auflösendes wegen schauen uns einfach 2 Mengen an das zieht mendici Celan dass ein hohles Lander kleines 1. AJ und und und und die restlichen also Lander ja sein alle I aus C für die Al Wallander kleiner gleich ARJ ist und des CIA ist sein dass sein die anderen wir unterscheiden wir 2 Fälle der 1. Fall dieses Zählern ist leer also es gibt gar keinen oder das Lander kleine ist also das heißt das Land erstmals größer als alle aber aber J das heißt es ist kein minimaler Körber also ich kann jederzeit noch eine rausnehmen ist immer noch ein Körper jeden von den und dann schauen was dann gilt schau die linke Seite an weil die sich die linke Seite also nach das Celan die leere Menge ist kann ich hier direkt schreiben für die linke Seite AJ J aus C XJ so dass sie sehr die orginal Ungleichungen mir das hier anschauen das ist sicherlich kleiner als G +plus S ja aber es war sozusagen nicht mehr um .punkt XS aus es aus sucht belaufen sich diese Bedingung soll das Musée einsetzen was das PS ja dann müssen wir gucken was in Karawanen Kavalkade definiert dass die Summe als das mal hin -minus langsam +plus S ja aus C dieses Teil hier bei gerade B BundeslÃnder war definiert als die Summe der eiert aus 10 -minus B ist der Überschuss wenn ich das nach b auflöst geklaut diesen Anteilen des genau das was auf der rechten Seite steht hier -minus Lander +plus S und je nachdem wie Selander die leere Menge ist steht genau diese Summe also für den Fall dass die Welt in Ordnung wie sieht es für den 2. Fall aus dass das Ziel anderer ungleich der leeren Menge ist und da unterscheidet man mal 2 Fälle der 1. Fall ist das das 1 x J 0 ist ich stamme zulässige Lösung an und 1 wenigstens 0 es also X für ein in mindestens Punkten ein J aus 10 da das liest sich jetzt die linke Seite wie Freud Summe ja hat aus 10 LÃndern solche kann ich Herrn anders schreiben man der XJ +plus Summe XJ für die Orts aus dem CIA an soll ich weiß mindestens ein Sitz 0 dann kann ich das abschätzen über Zählern da -minus 1 mal der ja ich weiß mindestens 1 0 müssten es schwerlich ab Summe XJ wird aus CA soll das kann ich jetzt noch mal abschätzen den 1. Teil und wir brauchen machen soll das ist sicherlich auch noch kleiner gleich wenn ich das hier belaste und hinten noch n S dranhängen ist ist sicherlich auch richtig aber es war größer gleich 0 welche genaue Recht es sei denn da Kommentar ist Mist erzählt er stimmt genau haben ja es genau die rechte Seite nämlich ja die Summe der Zählern das -minus das haben wir hier das ist das was hier steckt uns genau die rechte Seite gut dann bleibt der Fall wird der 2. Fall was B dass alle XJ gleich 1 sind für alle J aus 10 LÃndern so ein kann ich schreiben Summe wenn wir die linke Seite anschauen linke Seite Minimum ja und Lander J aus C XJ wenn ist nix anderes wenn die alle einzeln ist es die Kardinalität von 10 Malanda +plus Werder ist also J XJ und aus C sonst muss sie einfach der Reihe nach einsetzen wird weil sich dieses Ding muss damit ich die Orginal und Würfel also ist es sicherlich kleiner gleich wenn ich hier schreiben orientalische ich ab Selander +plus es ist -minus Summe ja und ja aus Zähler nach +plus b das einfach der orginal Ungleichung eingesetzt steht sie noch ich halte es auch wenn die Ziele anders und die CIA CAS wenn die CA sehen und bis auf die andere Seite bringen das muss als kleiner gleich B +plus S sein -minus den Anteil können so jetzt können wir dieses B selber aufschlüsseln es ging es dann doch noch einen Sinn hat nur beschweren was vielleicht dort freu ich ganz wischen doch also es kann weil für die ich Schlagerstar weitere sich also dass man ihnen das ist nichts anderes als Celan Lander +plus S -minus so Mehr AJ er hat aus 10 LÃndern sorglos so
Mehr aber JJ aus C -minus haben war dieser Anteil hier da hinten dass gerade das B das hat man schon mal eingesetzt Graber definiert wenn dieser Überschuss größer 0 ist das Land dabei gar zum mit der ARD und wird aus 10 -minus B 1 B aufgelöst genau das das Einreichen alles zusammen wenn wir uns das mal angucken dann kriegen wir insgesamt das Essen CJ Nylander Flores sollen wir das jetzt hier anschauen bleibt noch übrig nur Summe über J aus C a r a j habe ich die beiden zusammen nehmen -minus Lander das Erste nur an das englische hingeschrieben hier über sowie dem alle -minus die aus dem Zählern da es genau diese Menge ja und wenn wir das jetzt hier anschauen das genau die rechte Seite von der Ungleichung Mehr vielen wie Celan das steht da das Minimum Lander und das Ende des Dinges genau die Rechts Seite ok also wir sehen schon in dem Fall wird es deutlich aufwendiger allein schon die Gültigkeit zu zeigen als es häufig sogar diese Mischung aus ganzzahligen können ich war ja wie man das Problem richtig schwer weil eines kombinatorische Argument fehlt wie können den jährlichen verhindern sozusagen klassische kombinatorische Argumente anzuwenden und ich muss mir oft über über Umwege sozusagen zur Gültigkeit kommen und auch zu Fassetten Eigenschaft häufiger aber man ,komma wie Fall schon gesehen kommen interessanterweise auch West auch deutlich bessere im gleichen aus die dann natürlich auch für den allgemein oder für den ganzzahligen freigehalten gehalten Collins getan ist noch ein kleines Beispiel angeben ich glaub das brauchen wir das brauchen wir an der Stelle nochmal hinschreiben wichtig vielleicht noch mal der Unterschied den ich schon gesagt hab hier ist jeder caber zum Mehr Facette an dieser Stelle was nicht der Fall ist in in einem ganzzahligen gut so weit ein Stück weit zu den Zuhörern zu dem Rucksack Problem an sich wie gesagt als eine an eine der klassische untersuchten Probleme wobei es erstaunlich aber er weiß es sehr wenig hält bei gibt zu Projekt Rob wir haben wir es vergleichen der Riese ist ein Problem da gibt es Unmengen an Charakterisierungen von O Formen und waren die Facetten sind je kennt man denn die Graber man kennt ist 1 Gra Konfiguration wobei 1 gar Kongregation eigentlich nix anders sind als Graber wobei ich noch eine Variable Lifte hat aber auch erst spät entdeckt und dann gibt es noch der Reihe von so genannten rettet Ungleichungen die sozusagen mit Eskalierung in der Orginal Ungleichung zu arbeiten und die zu klassifizieren gewisse Gruppen und daraus dann gültige und zu machen es geht auf aber weiß man zurück diese letzten Aktivität aber sonst ist er die wenig bekannt und die meisten Verfahren ist dabei die gungsverfahrens dazu sind auch NP-Vollständigkeit also da ist nichts Bologna ist bekannt also vor aber auf der anderen Seite das eben auch wieder in das natürlich nicht sehr wichtig um den Hals sobald sie irgendein Problem haben können Sie immer darauf zurück greifen Sie wissen sofort wenn sie hier ohne Erfolg den Rucksack haben können sie sofort für jedes beliebige allgemeine ganz zeigeprogramm auch verwenden gut gibt es noch Fragen zu den Zeiten in ist nicht der Fall ist dann schauen wir uns jetzt noch ein 2. klassige an sozusagen und das sind 0 1 3. 10. was kann man über 0 1 2 sagen in wir werden in die und er ein wir also ein 2. klassige S 10 0 1 nun der Peking mit der SZ Grading per also das Zepter ich er Gegenpol tobt so Mo also wenn man so möchte ich bei dem Rucksack geht es um die um die Nummer Erregung die Zahl werden da kommt die Schwierigkeit doch die Al-Jazeera ja so sieht es auch am Beispiel angenommen alle ARJ Sven gleich ja da steht nur sowas wie zum ich sie kleiner gleich irgendwas na dann ist es genau dieser eine Graber und ist die einzige Ungleichungen die wie eine Facette sein kann also die Schwierigkeit bei den Rucksack kommt über die unterschiedlichen Koeffizienten erhalten das kann umgekehrt fragen was ist wenn ich den 10. festhalte konstant alles auf 1 ja 0 0 1 1 erlaubt was kann ich dann über diese Struktur der Matrix außer und da gibt es viele Untersuchungen und die wollen wir nun Christian Oberfläche auch auch auch ankratzen ein bisschen damit auch schon angefangen sich erinnern total ohne Modularität im wir haben uns Probleme angeguckt haben also von dieser Form klar dass man auch mal den maximiere Zielfunktion c't iX ja a x kleine gleich 1 alles soll 1 jetzt hier X aus 0 1 2 n das aber soll auch wir 0 1 Matrix sein hin an dann haben wir das schon so ist das 1. schon mal begegnet bei total ohne Modularität wer und was hat man da gesagt Anspruch dieses Ding immer eine ganzzahlige Lösung aus welche Eigenschaften bräuchten braucht für dieses Problem in die
erinnert sich noch nicht so allzu lange her kann man so einen Satz das ist total ohne Wohnung war ja 0 1 sind genau dann wenn ich weiß zugrundeliegender Graph spielt datiert war Mehr die Frage was der zugrunde liegende Graph aber wir warten geraten das wirklich würden dann Grafen oder aus also was man was man macht es für jede Spalte für jede Spalte für mein Knoten ja einen Knoten unter Quarantäne genau dann wenn er beide Knoten 1 1 wenn beide Knoten also sprich spalten 1 1 in einer Zeile gemeinsam haben also mach mal ein Beispiel Charles einfach so die Matrix hier den ich nochmal 1 1 1 1 ein sowas nie er warum aber jetzt 1 2 3 4 1 2 4. verliebt wir immer sowas ok was machen wir für also 5 Knoten ein 1 2 4 rund 5 wir kannte einen immer 2 1 nicht gemeinsam auftreten also die 1 und 1 und 2 haben wir eine gemeinsame 1 war erkannte der in 1 und 4 kann dann 2 und 4 kannte können das gleich jeder 2. 53 bis in jeder Zeile hier 2 3 und 5 Uhr das angucken 2 und 3 und 5 das hab ich noch 1 und 3 und dann haben wir noch 2 und 4 dann aber ich also das wär der zugehörige Graph ja und die Aussage war wenn sie ihre Lehren aus diesen Grafen Grafen wir haben wir dann das folgendes definiert indem wir gesagt haben jede Kante machen den Bedingungen ja das was sagen XI besitzt auf kleiner gleich 1 war und dann dieser kann dann ist das zugehörige zugrunde liegende Holtrop ganzzahlig genau dann wenn dieser Graph Tripartite ist und wir sehen jetzt hier schon eine der Eigenschaften zwischen dir und diesen Grafen was ist nämlich eine Lösung von AT die 1. Eigenschaft übersehen ist wenn ich eine Zeile anschaue ja alle Knoten die dieser wie diese in dieser Zeit involviert sind die definiert Lügen der Clique also wirklich Clique ist ne Teilmenge wo ich jeweils 2 einander benachbart sind also wenn ich mir die 3 einst anschauen ja es 1 2 und 4 ja das ist ne klicke ich jeweils 2 sind einander benachbart sind eine Clique das gilt natürlich auch für den für den hier unten also auch hier wenn ich mir die 1 wo ein sowie 3 anschauen das auch wirklich Clique an jeweils 2 sind einander benachbart wir das heißt jede Zeile hier drüben spricht Mehr Clique wie es jede Lösung aus wenig milde Sohn von hier anschauen der zulässige Lösung hier was entspricht denn wir würden ja erfasst der eine stabile Menge genau also der stabile Menge nur ich wenn ich hier also die 7 Lösung aus so dummerweise nur 2 Farben zur Verfügung also wenn ich hier irgend irgendeine ja mal an die Variable wäre in der Lösung war die einzige so dann dann wissen wir ich kann weder die zwar noch die 4 will er weich aber hier Bögen kleine gleich 1 stehen das heißt alle die denn dieser Knoten erkannte gemeinsam hat also ja alle Knoten mit denjenigen keine gemeinsame kann ich nicht mehr wäre das heißt der fliegt raus der fliegt raus aber auch der fliegt aus ja das heißt die Lösung kann nur so aussehen in dem Fall die 5 noch dazu so dass die weiß keiner einzelne Zeile gemeinsam haben das heißt der gerade spannender Pflügen haben keine gemeinsame kannte eine Teilmenge von Knoten die keine ihres paarweise keine gemeinsamen Kanten an wenn eine stabile Mängel wir und ist 1 zu 1 auch umgekehrt wenn ich das stabile Mengenproblem die sofort in diese Form und diese Form ich sofort ins und stabile Mengenproblem des mehr als 1 Beziehung her zwischen diesem Problem und diesen stabilen Mengenproblem mehr so und dieses Problem nennt dann also auch das der vergehen Probleme also hier das heißt seit Peking also packen von Mengen ja und das ist äquivalent zum stabilen wegen Problemen wenn man diesen Grafen hier das die Matrix A ist bezeichnen den den gern auch als G von oder als Konflikt Graph und ich während der in der modellierten alle Konflikte die sozusagen sein Antlitz
auftreten was man auch als 2. noch hatte es ist es Zeit Graber den Problem so maximiere wie aus dem kleinen gleichen größer gleich mein nix anders also ich schreibe hier größer gleich 1 Herr X aus 0 1 hoch n der 1 dann ist es Zeit ,komma den Problem also woher kommen die die Namen hat man ein Führerschein kennen gelernt ich kann jede Spalte hier als sie sie den Sektor einer Teilmenge interpretieren und das heißt ich möchte hier die Teilmengen die Mengen so parken dass jedes Element jedes Element der Grundmenge maximal einmal vorkommt ist der Peking gering packen von Mengen und im anderen Fall mächtig die Teilmenge so viel in der Auswahl der teilnehmen so dass jedes Element überdeckt ist dann so man kann wenn man das möchte aber das ist nur andeuten das ZK den Problem ist eigentlich nichts anderes als dass der wegen Problemen im Hypergraphen wir gerade vom 1. Weise wirst schon mal gehabt hat Übergabe seine verallgemeinern im Umfang Grafen indem man jetzt nicht mehr nur kannten erlaubt sondern sogenannte über Graph über kannten das sind 3 Mengen von Knoten also man kann eine Kante interpretieren einfach als eine zweier Teilmenge der Knoten bekannt ist nix an der sich immer 2 Knoten aus und sagt die 2. mindernde verbunden sei es kranken sie nix anders als 2 Elemente Teilmengen der Menge der Knoten dieses Konzept kann nicht verallgemeinern auf 3 Elemente Getreidemengen der Knoten in der Unterkreide Mennige teilnehmen K größer als 2 ist der man über kannte ich das erlauben dann spricht man von übertrafen das kann ich wieder fragen sich stabile Mengen in einem Hypergraphen wenn das ist eine Teilmenge der Knoten so dass keiner kann über kann der darin enthalten ist ja und und dieses seit Karl dem Problem lässt sich umformulieren nämlich mich einfach alle Variablen hier komplimentiert ja ich schreib hier statt x 1 1 -minus x sie dann klicke hier entsprechend die Matrix auf die andere Seite steht hier von den konvertierten Bayern a x kleine gleich und das steht hier drüben die Anzahl der einst in dieser Zeile -minus die 1 das heißt er sie jederzeit jede Zeile definiert man über kannte kleiner gleich an 2 1 1 30 ich darf mit einem nicht so viel dass der gesamte über kannte drin vorkommen kann also in dem Sinn sie beide ist leider immer größer gleich als sehr es nahe miteinander verwandt wobei das Studium von übertraf bei weitem nicht so fortgeschrittene sie das Studium von Grafen und für die Vorlesung geht es hier um uns das auch nur wirklich mal für diesen 1. Fall hier angucken also für das der Peking Probleme wir haben so und da haben wir auch schon vielleicht erst mal ein paar Eigenschaften also das was aber noch das Projekt Rob definieren n was ja ist dann noch ein paar Eigenschaften anschauen wir sollen wir
wir werden wenn das wird das ist kann wir kann wir haben also erst mal sollte man das bei tobt definieren mehr wann und wir also sei wir schauen zwar des A an 0 ja die Menge aller das 0 1 Uhr n a x leider gleich 1 oder wir es dem Grafen Spanien machen wollen zwar nicht dass er definiert mich 2 verschiedene Madrid und habe noch ja und die der wir so anders so meine hält genau dasselbe Polito P wir mal ich hab ne 2. Matrix in bisschen anders aussieht als diese die Charakterisierung der Lösungen von gleich B erhält man genauso gut über diesen Grafen G über die stabilen Mengen hier das heißt es macht Sinn an dieser Stelle wer anstatt die sind dieses G von Art zu schreiben er oder allgemein gleich auf dem Graph zu operieren weil hier die die gemeinsame B 1 zu 1 Beziehung zwischen diesen Bartels zum diesen Grafen beherrscht werden so was kann man über dieses ich habe das immer so willkommen wie ja wenn man nicht auf einmal gleich vom Grafen aus Staaten der Welt ist das die von geht was kann über dieses was kann über dieses Balea sagen glaube soll den und kommt von den machen wie auf das allerdings könnte auch sagen wir mal ,komma richtig also hier kommt noch im Konzern ja zum Beobachtungen dass es hier zusammengefasst Bemerkungen A 3 27 weil die 1. Aussage ist das Politologe wurde es erst mal wieder vor dem in 10 Mal warum ist denn so das gleiche Argument wie vorher und ich kann jeder eines der Spalte auf einsetzen alle andern auf 0 sie zulässiger .punkt das heißt jeder Einheitsvektor es zulässig Kiel als es den folgenden die 2. Eigenschaft ist das Palais der ist monoton wir absteigen und und Schwärmer Suppen monoton das heißt so wenn X in diesem Palais enthalten ist dann folgt auch das y in diesem Politiker ist für alle 0 kleiner gleich y kleiner gleich x also wenig komponentenweise kleine der Vektoren an mir anschau dann sind die auch drin ja das einer Eigenschaft dass die Matrix positiv ist ja ich kann jederzeit was rausnehmen und bleibt gültig und können was sich damit dem Blitz hier ist sofort dass jede Facette hat nur nicht negative Einträge und daraus folgt jede Facette hat nur nicht negative Koeffizienten unter alles daran den Charakter es sei nicht die fast sollen die ungleiche wie Facette induzierte hat man nicht negative konsistent warum es denn so wir haben man kann keine Koeffizient auftreten der negativ ist oder war das eine Übung wo ich irgendwas verrate aber mal sind Übungen war das lieber nicht und das 3. was man über ich auch gleich einen sehen kann das XJ größer gleich 0 ist und alles was er kann oder definieren versetzt .punkt das Johnson war ganz einfach Beobachtungen der weiß Übung der sollt ,komma dann gleich zum zum 1. interessanten fahlen Licht wenn uns noch mal überlegen wir hatten ja charakterisiert ist und Grafen haben spuckte mir ganzzahlige Lösungen aus das war genau dann wenn das denn also die Matrix A die zu diesem Graben G gehört hatten wir ganz das zugehörige war ganz war total ohne modular genau dann wenn der zugehörige Graph die Partie ist das hat man da ist und dann haben wir an den Datensatz und Übung gab Biberti genau dann wenn er kein ungeraden Kreis enthält also scheint das mit diesen ungeraden Kreisen zu sein wir waren und die genau die liefern uns auch um Gleichungen und die schauen wir uns zum 1. Mal nach die Definition dazu rollt an also wenig Sorgen um angereist ab wir mal ein Beispiel hier so viel wie kann ich davon maximal nehmen Wahlsieg sieglosen meine Variable wie kann ich maximal nehmen auch ungeraden Kreis wer hat die wie gehabt so können was schreiben oder wenn es der Desailly Längen dann haben also also 10 2. CD ziehenden ungerader Kreis man dann folgt Summe X I Auszüge was sollen wir damit sie argumentieren dass genau das was Sie gesagt haben die Knoten von dem Kreis ja -minus 1 Halde nun das genau also der Länge 2 n hätte und das ist in Halle dass genau das die Zahl die Sie gesagt haben da diese Ungleichung ist gültig und und definierten der Facette genau dann wenn C 1 und mir war das Loch ist das Ziel .punkt ich und wir da das Loch das heißt wissend gereist und wir sehen ja also ich da tritt sie nicht mir Diagonale drin haben war Schuldscheine belanglosen wir weil sich glaubt dem Klima immer ganz in das sage ich vielleicht eine Geschichte noch zu dieser Ungleichung wie
kriegen wir denn diese um gleiche Wikinger auch auf interessante Art an der Art und Weise und schauen uns mal wir jetzt einfach mal dass in Matrix vom anschauen jährlich 1 2 3 4 5 ja wie Sie meinen eine Matrix dazu aus der GD 5 Knoten 1 2 3 4 5 oder 5 kannten 1 2 3 4 5 war kann das immer so hier hab ich ne 1 1 ja dann habe ich 2 3 3 4 4 5 und 5 1 so sie diese Struktur aus nun und hier drüben hab ich jeweils stehen kleine gleich 1 kleiner gleich 1 und so weiter ist spielen zuweilen verrutscht es ist ein bisschen weiter oben Waigel und eine machen also 5 hab ich hier bei der 1 und 4 die 1 und hier steht jeweils kleiner gleich 1 kleiner gleich 1 es unser Ausgangs Problemen der Name jede Kante gesagt die darf ich viele kannte der vor ihr Kandidat mit maximal 1 nehmen bei stabilen Mengen sorge ich da wir es total verrutscht kann also kleiner gleich 1 kleiner gleich ein soll zu mir ich die mal auf ja was passiert denn jetzt aber an sich zu mir senden aus und es kann alle mit dem halb jede dieser Ungleichung skaliert ich mit halb und wir sie auf ok was passiert ich hab hier jede Ehe in jeder Spalte der mit mir 1 genau zweimal auf das heißt hier unten steht dann wenn x 1 +plus x 2 +plus x 3 +plus x 4 das X 5 so kleiner gleich und hier drüben steht die Länge von den Kreis wer Frau von 10 halte Marke sollen uns das anders mehr das sind alles gültige Ungleichung wenig Google die Ungleichung aufsummiert Dividende gültige ungleich ich gehe Kiel sogar ne nette und links ganzzahlige ist die rechte Seite ist gebrochen nach Quartal wir aber unten wenn ich Frau Halle Abgrundes genau das VC -minus 1 halbes genau das herrliche abgekommen ja oder an wie ist es mit ,komma die zu interpretieren dass eigentlich auch mit seiner leisen ,komma Durchschnitt warum wer was macht man ,komma wie Ihnen ,komma deeskaliert wir meinen ,komma Durchschnitt gequält damit der Eaton Basis in der 1. Tor multipliziert man die Idee Zeile der Basen genommen und dessen genaues Escalade die wir hier haben ja wir nehmen einfach als Caillat in den ehemaligen eintragen der in der sei der Basin lassen das ist das was ,komma und gemacht und hier einmal ganz spezieller warum soll ich denn jetzt also das Konzept sogar sich verallgemeinern aber ich muss nicht unbedingt jetzt als Call a decade sind die Basis wie derzeit der Basen lassen nämlich keine irgendwelche skalaren Größen nehmen wir und diesen Bereich ich alles in Hallenbädern komme hier auf eine Ungleichung wie genau vom Typ von Quartal ist und wo man jetzt sogar nachweisen können wir diese Sache ist das ist tatsächlich auch gerne Facette also wir sehen unter spezieller war dieser Koeffizienten Konzerts bei dieser Aktion aus ,komma die vom 1. allgemein nicht sagen konnten komm in speziellen Situation auch tat sich hätten definieren die Umgehung raus und es ist Zeit zu zeigen dass auch die Qualität dieser und die zwar im Allgemeinen doch aus nur in stabil sein kann aber ein heute in vielen häufigen Fällen kommt es sogar fast hätten definieren die Ungleichung aus und das ist tatsächlich eine Facette ist dass man weiß wann das nächste Mal gut
Simplex
Matrizenmultiplikation
Verweildauer
Besprechung/Interview
Lösungsraum
Computeranimation
Monster-Gruppe
Variable
Ungleichung
Verallgemeinerung
Stützpunkt <Mathematik>
Struktur <Mathematik>
Addition
Verschlingung
Polyeder
Fünfzig
Ganzzahlige Optimierung
Ähnlichkeitsgeometrie
Fokalpunkt
Null
Lösung <Mathematik>
Koeffizient
Durchschnitt <Mengenlehre>
Größenordnung
Schnitt <Mathematik>
Gebiet <Mathematik>
Nebenbedingung
Lucas-Zahlenreihe
Simplex
Gewicht <Mathematik>
Dualität
Variable
Ungleichung
Vorlesung/Konferenz
Zielfunktion
Inklusion <Mathematik>
Polyeder
Vektorrechnung
Reihe
Fläche
Konvexe Hülle
Randbedingung <Mathematik>
Vektor
Zahl
Maßeinheit
Teilmenge
Summe
Menge
Konferenz Europäischer Statistiker
Koeffizient
Ecke
Matrizenmultiplikation
Zusammenhang <Mathematik>
Gruppenoperation
Besprechung/Interview
Maximum
Gleichungssystem
Liften <Mathematik>
Skalarfeld
Freiheitsgrad
Index
Variable
Ungleichung
Inklusion <Mathematik>
Bruchteil
Einfach zusammenhängender Raum
Polyeder
Obere Schranke
Dynamische Optimierung
Eindeutigkeit
Optimierungsproblem
Hausdorff-Raum
Partitionsfunktion
Zahl
Teilmenge
Lösung <Mathematik>
Summe
Menge
Koeffizient
Schnitt <Mathematik>
Erweiterung
Matrizenmultiplikation
Polyeder
Mathematik
Besprechung/Interview
Konvexe Hülle
Zahl
Summe
Variable
Ungleichung
Menge
Verallgemeinerung
Koeffizient
Minimum
Vorlesung/Konferenz
Struktur <Mathematik>
Parametersystem
Verschlingung
Punkt
Matrizenmultiplikation
Mischung <Mathematik>
Besprechung/Interview
Reihe
Liften <Mathematik>
Zahl
Ganzzahlige Lösung
Summe
Ungleichung
Homogenes Polynom
Menge
Würfel
Koeffizient
Minimum
Zielfunktion
Konfigurationsraum
Teilmenge
Hypergraph
Variable
Matrizenmultiplikation
Graph
Menge
Geometrischer Körper
Vorlesung/Konferenz
Gravitationsgesetz
Kante
Umfang
Bogen <Mathematik>
Mathematische Größe
Kreis
Länge
Matrizenmultiplikation
Kreisfläche
Graph
Vektorrechnung
Gruppenoperation
Gleichungssystem
Kante
Ganzzahlige Lösung
Zahl
Lösung <Mathematik>
Summe
Variable
Ungleichung
Menge
Koeffizient
Stützpunkt <Mathematik>
Vorlesung/Konferenz
Durchschnitt <Mengenlehre>
Diagonale <Geometrie>
Aggregatzustand

Metadaten

Formale Metadaten

Titel Ungleichungen mit Struktur: Das Rucksack und Set Packing Polytope
Serientitel Diskrete Optimierung (Optimierung II)
Teil 13
Anzahl der Teile 26
Autor 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/31794
Herausgeber Technische Universität Darmstadt
Erscheinungsjahr 2009
Sprache Deutsch

Inhaltliche Metadaten

Fachgebiet Mathematik

Ähnliche Filme

Loading...