Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Lineare Optimierung
Gehe zu Seite Zurück  1, 2, 3  Weiter
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Mathe-Forum -> Lineare Optimierung
 
Autor Nachricht
Thomas_Da
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 21.11.2004
Beiträge: 352
Wohnort: Darmstadt

BeitragVerfasst am: 09 Jan 2005 - 19:41:57    Titel:

Wenn man davon ausgehen kann, dass im nichtganzzahligen Bereich die Optimale Lösung eine Ecke oder eine Kante ist, dann muss im ganzzahligen Fall die Lösung auch am Rand zu finden sein. Diese ganzzahligen Randlösungen besitzen die Eigenschaft, dass mindestens ein benachbarter ganzzahliger Punkt nicht zur "erlaubten Menge" gehört. Jetzt kann man aber so argumentieren, dass es somit für jeden inneren Punkt (Kreuz) einen Nachbarn gibt, dessen Lösung besser ist, entweder ein anderer innerer Punkt, oder ein Randpunkt. Letzteres müsste man nun "mathematisch" beweisen.
Thomas_Da
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 21.11.2004
Beiträge: 352
Wohnort: Darmstadt

BeitragVerfasst am: 09 Jan 2005 - 23:40:58    Titel:

Ich habe eben mal nachgeschaut was sich über ganzz. lin. Optimierung so habe.

Wie schon beschrieben sei die Menge der zulässigen Lösungen durch ein konvexes Polytop (Polyeder) gegeben. Wenn man nun NB (Ungleichungen) ermittlt, so dass sich diese nur in ganzz. Lösungen schneiden und alle ganzz. Lsg. des Ursprungspolyeders enthalten sind, dann erhält man durch Lösung dieses neuen Problems (im reelen) sofort eine ganzz. optimale Lsg.
Dieses "neue" Polytop mit ganzz. Eckpunkten nennt man dann die konvexe Hülle der ganzz. erlaubten Lsg., die ebenfalls ein konvexes Polyeder ist.

Dann haben wir noch ein paar Methoden kennengelernt, wie man Nebenbedingungen verschärfen kann, so dass die zulässige reelle Lsg.menge verkleinert wird ohne aber die ganzz. Lösungsmege zu beeiflussen.
Z.B
NB die andere NB dominieren
Schnittebenen (Cover-Ungleichungen)


Wenn Du sicher bist, dass Dein neues Verfahren funktioniert (und nicht langsamer ist als bestehende) dann kannst Du ja mal bescheit geben (und mir Deinen Aufsatz zukommen lassen).
Natürlich helfe ich auch bei Fragen so gut ich kann.
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 10 Jan 2005 - 15:02:17    Titel:

Ich muss heute noch ne Übung halten. Ich renne so schnell wie möglich zu meinem Betreuer Prof und checke das mal mit Ihm. Schaumaramal.
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 11 Jan 2005 - 22:30:25    Titel:

Gestern und vorgestern war's ein wenig stressig ... naja.

Zitat:
Wenn man davon ausgehen kann, dass im nichtganzzahligen Bereich die Optimale Lösung eine Ecke oder eine Kante ist, dann muss im ganzzahligen Fall die Lösung auch am Rand zu finden sein. Diese ganzzahligen Randlösungen besitzen die Eigenschaft, dass mindestens ein benachbarter ganzzahliger Punkt nicht zur "erlaubten Menge" gehört. Jetzt kann man aber so argumentieren, dass es somit für jeden inneren Punkt (Kreuz) einen Nachbarn gibt, dessen Lösung besser ist, entweder ein anderer innerer Punkt, oder ein Randpunkt. Letzteres müsste man nun "mathematisch" beweisen.


Ist wirklich sinnig. Ich werde mal das verfolgen und versuchen das formal zu beweisen.

Zitat:
Wenn man nun NB (Ungleichungen) ermittlt, so dass sich diese nur in ganzz. Lösungen schneiden und alle ganzz. Lsg. des Ursprungspolyeders enthalten sind, dann erhält man durch Lösung dieses neuen Problems (im reelen) sofort eine ganzz. optimale Lsg.


Es zu ermitteln ist auch exponentiell, oder? Hast Du da eine Komplexitätsabschätzung? Habt ihr ein Verfahren dazu angeschaut (name reicht).

Vielen Dank. Es gitb mir wieder Auftrieb.[/quote]
Mirona
Gast






BeitragVerfasst am: 12 Jan 2005 - 21:24:43    Titel:

Hallo algebrafreak,

ich versuche mal auf deinen ersten post zu antworten .

Versuche "ähnliche" Sätze zur Charakterisierung optimaler Lösungen von ganzzahligen Optimierungsproblemen zu bestimmen, gibt es sehr wohl.
Sei zum Beispiel P ein Polytop (also ein beschränkter Schnitt endlich vieler Ungleichungen mit reellen Variablen, ohne Ganzzahligkeitsforderung), so kann man die Menge P' definieren als konvexe Hülle aller ganzzahligen Punkte von P.

Also P' := conv{ x : x ist Element von P und x besitzt ganzzahlige Koordinaten} .

Dann ist P' selber ein Polytop, kann als Schnitt endlich vieler Ungleichungen dargestellt werden (an die man noch weitere Anforderungen stellen kann) und P' besitzt die Eigenschaft, das alle Ecken ganzzahlig sind und damit "normale" lineare Optimierungsmethoden zum Optimieren benutzt werden können.

Ob dieser Ansatz jedoch algorithmisch "vernünftig" ist, ist eine andere Frage.
Ein Problem liegt zum Beispiel darin, das eine Darstellung von P' als Schnitt von Ungleichungen sehr viele (deutlich mehr als eine Darstellung von P) Ungleichungen enthalten kann. Ein weiteres Problem wäre diese Ungleichungen auch algorithmisch vernünftig zu bestimmen.

Ich hätte noch einige Fragen/Bemerkungen ( zum Teil auf Beiträge in späteren Posts):
1. Optimieren mit beliebig vielen Variablen ( "normales Optimieren") oder nur im Spezialfall der Ebene (die Skizze suggeriert dies, dann gelten viele viele viele zusätzliche Vereinfachungen) ?

2. aus Ungleichungen können zum Beispiel durch Einführung von Schlupfvariablen Gleichungen gemacht werden ( ob dies sinnvoll ist, hängt davon ab, was man tun will)

3. was sind die schwarzen Punkte ? ( also ich hoffe auf eine definitionsähnliche Beschreibung , ohne Bild )

4. bei der Suche nach einem Ansatz für ganzzahlige lineare Optimierungsprobleme :
einen "richtigen" Ansatz ( also mittels theoretischer Einsichten in das Problem, zum Beispiel über geometrische Erkenntnisse oder strukureller Erkenntnisse) oder "nur" einen Branch-and-"irgendwas" Ansatz ( wobei die theoretischen Einsichten "nur" für das "irgendwas" gebraucht werden, also im Prinzip ein besseres Raten )

MfG Mirona
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 12 Jan 2005 - 23:06:27    Titel:

Vielen Dank für's Interesse

Zitat:
Ob dieser Ansatz jedoch algorithmisch "vernünftig" ist, ist eine andere Frage.


Meine Vermutung ist, ohne den Algorithmus selbst gesehen zu haben, dass dieser exponentiel in der Anzahl der Zusicherungen ist. Demnach würde der nicht als Teil eines "effizienten" Verfahrens sinnig erscheinen. Es ist jedoch von Rakof nachgewiesen worden, dass Entscheidungsprobleme der Form, auf die ich das Problem anpassen will, bestenfalls doppelt exponentiell sind. Daher käme das ganze jedoch in Frage.

Zitat:
1. Optimieren mit beliebig vielen Variablen ( "normales Optimieren") oder nur im Spezialfall der Ebene (die Skizze suggeriert dies, dann gelten viele viele viele zusätzliche Vereinfachungen) ?


Beliebig viele Variablen, davon beliebig viele in der Zielfunktion, beliebig viele Parameter, beliebig viele Constraints, Constraints sind multivariate ganzzahlige lineare polynome und konjunktiv verknüpft.

Zitat:
2. aus Ungleichungen können zum Beispiel durch Einführung von Schlupfvariablen Gleichungen gemacht werden ( ob dies sinnvoll ist, hängt davon ab, was man tun will)


Das weiss ich, habe aber daran noch nicht gedacht. Das erhöht jedoch die Anzahl der nicht Gleichungs-Zusicherungen und ist daher problemmatisch.

Zitat:
3. was sind die schwarzen Punkte ? ( also ich hoffe auf eine definitionsähnliche Beschreibung , ohne Bild )


Anschaulich sind die schwarzen Punkte, wie @Thomas_Da unglaublich schön festgestellt hat, zulässige ganzzahlige Punkte, mit der Eigenschaft: In der 4-er Nachbarschaft (links rechts oben unten) befindet sich mindestens eine nicht zulässige ganzzahlige Lösung.

Behauptung: Diese Punkte sind Lösungen von Gleichungen, die dadurch entstehen, dass man die simplifizierten Zusicherungen von der Form:

a_1 x_1 + a_2 x_2 + ... + a_n x_n <= / >= k

mit der Eigenschaft ggT{a_i | 1 <= i <= n} = 1 in die Form

a_1 x_1 + a_2 x_2 + ... + a_n x_n = k

umformt.

Zitat:
4. bei der Suche nach einem Ansatz für ganzzahlige lineare Optimierungsprobleme :
einen "richtigen" Ansatz ( also mittels theoretischer Einsichten in das Problem, zum Beispiel über geometrische Erkenntnisse oder strukureller Erkenntnisse) oder "nur" einen Branch-and-"irgendwas" Ansatz ( wobei die theoretischen Einsichten "nur" für das "irgendwas" gebraucht werden, also im Prinzip ein besseres Raten )


Das zweite. Beachte, dass Lösungen, die gewöhnlich angeboten werden versuchen das Problem auf Simplex zurückzuführen. Ich mache ganz was anderes. Ich habe einen Constraintsolver direkt in PrA (also ganze Zahlen mit Ordnung), der theoretisch damit fertig wird. Leider ist es so, dass bei einem doppelt-exponentiellen Verfahren sehr schnell der Speicher wegkommt, sodass, wie auch eigentlich bei anderen Verfahren, schon bei einfachen Eingaben schnell alles vorbei ist.

Was ich glaube eine Relaxation bringt, ist die Einsicht, dass man die Ungleichungen aus der Sicht der prädikatenlogik erster Stufe (das ist wichtig: nicht aus der Sicht von Simplex) durch Gleichungen ergänzen kann. Dadurch bekommt man die Möglichkeit die formalen Lösungen der Gleichungen in die sonstigen Constraints einzusetzen. Das Ergebnis ist für jede Gleichung nur um eine Kongruenz länger:

Beispiel: 2*x > 1 , 2*y > 1 und k(x,y) = x+y

Betrachte die Ränder: x = 1 und y = 1. Die zulässigen Lösungen liegen in der semialgebraischen Menge:

2*x > 1 and 2*y > 1 and (x=1 or y=1)

Eigentlich schon in (x=1 or y=1), aber die ist ja i.A. unbescchränkt, daher braucht man andere. Jetzt kann man das Distributivgesetz anwenden und bekommt:

2*x > 1 and 2*y > 1 and x = 1 or
2*x > 1 and 2*y > 1 and y = 1

Die Existenz der Lösungen beider Teilformeln (der ersten bzgl. x und der zweiten bezgl. y) ist garntiert, wenn gilt:

2* 1 > 1 and 2*y > 1 and 1 = 1 and 1 = 0 (mod 1)

2* x > 1 and 2*1 > 1 and 1 = 1 and 1 = 0 (mod 1)

also

2*y > 1

2*x > 1

Jetzt hat man die Zusicherungen getrennt. Beachte: Es ist nur ein unvollständiger Teil des Verfahrens. Genaueres in

http://www.opus-bayern.de/uni-passau/volltexte/2003/6/pdf/Dolzmann.pdf

Seite 123 (da ist der Satz für reelle QE).[/b]
Mirona
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 13.01.2005
Beiträge: 239

BeitragVerfasst am: 13 Jan 2005 - 21:16:13    Titel: Nur eine kleine Antwort

Hallo,

vielen Dank für den Link, werde (versuchen) mir dies morgen mal zu überfliegen,
deswegen hier nur ein paar kurze Antworten :

Bei dem Gedanken mit der ganzen Hülle ( ja, man nennt diese oben definierte Menge integer hull, obwohl sie zunächst geometrisch kleiner ist) hatte ich keinen "konkreten" Algorithmus im Hinterkopf, aber es gibt sehr viele algorithmische Ansätze, die hierauf aufbauen.
Zum Teil theoretische (deterministisch, endlich, aber im worst case leider zu viele Schritte bzw Ungleichungen) als auch praktisch relevante ( zum Beispiel Gomory-Chavatal-Schnitte bei branch-and-cut Algorithmen oder das "Abrunden" der rechten Seite bei auf TDI (=total dual integrality) Darstellungen basierenden Ansätzen (aus der Ungleichung 3*x+5*y <= 7.5 könnte zum Beispiel bei ganzen x,y die 7.5 abgerundet werden, dieses "Ranschieben" der Hyperebenen kann ein recht mächtiges Werkzeug sein). Es ist auch möglich ganze Klassen von Ungleichungen in einfache Orakel zu codieren ( algorithmisch also ein gutes "unterprogramme"), allerdings braucht man hierfür sehr viel strukturelle Einsichten in die zugehörigen Probleme ( für das TSP wird alle paar Jahre mal soetwas von sehr guten Forschern erreicht).

Gut, von beliebig vielen Variablen, Nebenbedingungen usw. gehe ich auch aus. ( wollte nur darauf hinweisen das im zweidimensionalen dieses ganze theoretische "Zeug" nicht gebraucht wird)

Mhhh, ja, Ungleichungen zu "vernichten" um dann nur noch Gleichungen zu besitzen ist nicht ganz so einfach.

Bei der Sache mit den schwarzen Punkten bin ich mir grad nicht so sicher ( also ob diese Behauptung mit den Richtungen auch im drei und höherdimensionalen gilt), ich denke ganz so einfach ist das nicht.

So, werde mal Versuchen, das Beispiel zu verstehen (klingt auf jeden Fall sehr interessant).

MfG Mirona
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 14 Jan 2005 - 00:38:43    Titel:

Zitat:
Bei der Sache mit den schwarzen Punkten bin ich mir grad nicht so sicher ( also ob diese Behauptung mit den Richtungen auch im drei und höherdimensionalen gilt), ich denke ganz so einfach ist das nicht.


Das war auch der Grund für diesen Thread. Ich bin nur zufällig darauf gestoßen, dass der Simplifier (Vereinfachungstool) für atomare Formeln (also Gleichungen und Ungleichugne usw.) als Ergebnis für Ungleichungen folgendes liefern kann:

a_1 x_1 + ... + a_n x_n <= k <=>
a_1 x_1 + ... + a_n x_n < k or a_1 x_1 + ... + a_n x_n = k,

wobei die Gleichung stets erfüllbar ist. Die Annahme ist nun, dass diese Gleichung eben den Rand beschreibt auf dem die Lösungen liegen.

Wenn Du das Zeug durchgelesen hast, kannst Du Dir das Beispiel genauer anschauen:

Beispiel: 2*x > 1 , 2*y > 1 und k(x,y) = x+y

Formulierung:

exists x exists y (2*x > 1 and 2*y > 1 and z >= x + y)

Mein Vorschlag:

exists x exists y (2*x > 1 and 2*y > 1 and z >= x + y and (x = 1 or y = 1))

<=> (Distributivgesetz)

exists x exists y (2*x > 1 and 2*y > 1 and z >= x + y and x = 1) or
exists x exists y (2*x > 1 and 2*y > 1 and z >= x + y and y = 1)

<=> (Vertauschen von Quantoren in einem existenziellen Block)

exists y exists x (2*x > 1 and 2*y > 1 and z >= x + y and x = 1) or
exists x exists y (2*x > 1 and 2*y > 1 and z >= x + y and y = 1)

<=> (Einsetzen der Formelen Lösungen (Deep Partial Gauss Elimination))

exists y 2*y > 1 and z >= y + 1 or
exists x 2*x > 1 and z >= x +1

<=> (Und das ganze noch einmal)

exists y 2*y > 1 and z >= y + 1 and y = 1 or
exists x 2*x > 1 and z >= x + 1 and x = 1

<=> (Einsetzen der Formelen Lösungen (Deep Partial Gauss Elimination))

z >= 2 or z >= 2

<=>

z >= 2

Durch entsprechende QE mit Antworten kommt da auch für z = 2 das Ergebnis x = 1 and y = 1


[/quote]
Gast







BeitragVerfasst am: 14 Jan 2005 - 16:44:35    Titel:

So, nun noch mal einige Gedanken zu den schwarzen Punkten von mir (hatte mal Zeit darüber nachzudenken).

Ich benutze die Definition von Thomas_Da : ein schwarzer Punkt ist ein zulässtiger, ganzzahliger Punkt, mit der Eigenschaft, das mindestens einer der 2*d Nachbarn nicht zulässig ist.

d ist hierbei die Raumdimension und unter einem Nachbarn verstehe ich einen Punkt, der in der Manhatten-Metrik den Abstand 1 besitzt ( welcher also in genau einer Koordinate sich um +1 oder -1 vom betrachteten Punkt unterscheidet)

Bemerkung 1 :
diese schwarzen Punkte können im "Pechfall" viel zu viele Elemente (sogar alle) enthalten,
die Hoffnung durch diesen Schritt also weniger Punkte betrachten zu müssen, ist trügerisch (zumindestens zu Anfang)

Bsp: in der Ebene seinen alle zulässigen Punkte gegeben durch x-y=0 ( also 2 Ungleichungen gleich zu einer Gleichung zusammen gefasst )
Also alle Punkte der Form (z,z) mit z ganz sind ganzzahlige,zulässige Punkte.
Diese sind ALLE schwarz ( weil es immer nicht-zulässige Nachbarn gibt).

Die Ursache liegt daran, das die zulässige Menge an sich schon niederdimensional sein kann, und prinzipell ist dieses für jedes Polyeder möglich ( man kann es ja immer als niederdimensionales Polyeder in einer Raumdimension höher interpretieren) und einfach im niederdimensionalen zu argumentieren, ist nicht unbedingt so einfach ( im Beispiel war es die "Diagonale" x=y , welche mit den "normalen" 4 Richtungen nicht besonders gut harmoniert).

Bemerkung 2: von Thomas_Da stammt der Vorschlag die 2*d Richtungen als "Verbesserungsrichtungen" zu benutzen und die schwarzen Punkte als "Abbruchbedingungen" für folgendes algorithmisches Grundschema :
starte mit irgendeinem zulässigen, ganzzahligen Punkt; verbessere solange bis man zum "Rand" ( hier war schwarzer Punkt eine erste Charakterisierung) kommt

dieses funktioniert leider nicht ganz so einfach ( nicht nur wegen den schwarzen Punkten - Bemerkung 1), denn die 2*d "Verbesserungsrichtungen" sind im Allgemeinen viel zu wenige.

Bsp: man wähle 2 sich sehr "spitz" schneidene Geraden in der Ebene , welche in der "Spitze" einen ganzzahligen, zulässigen Punkte ( welcher bezüglich einer festen Zielfunktion auch optimal sei) besitzt, so ist keiner der 4 nächsten Nachbarn (oder auch der "diagonalen Nachbarn") zulässig, der obige algorithmische Ansatz würde also den optimalen Punkt nie erreichen können ( ausser man startet dort schon)

Zusatz zur Bemerkung zwei : man kann mit mehr "Verbesserungsrichtungen" den Ansatz von Thomas_Da zu einem richtigen Algorithmus ausbauen , in der Optimierung nennt man dies dann eine Testmenge ( eine endliche Menge von Vektoren , mit der Eigenschaft, das sie für jeden ganzzahligen zulässigen Punkt mindestens eine verbessernde Richtung besitzen oder (falls alle Verbesserungen unzulässig sind) als Nachweis der Optimalität dieses Punktes dienen).
Solche Testmengen existieren (von einigen tech.Spezialfällen mal abgesehen) immer.
Probleme kann es bei der Anzahl der Elemente und/oder bei der algorithmischen Bestimmbarkeit geben.
Gibt ausserdem einen sehr schönen Zusammenhang (der in der Mathematik alle paar Jahre neu entdeckt wird) zwischen den Testmengen und den Gröbner-Basen binomischer Ideale ( insbesondere kann damit der Buchberger-Algorithmus in der ganzzahligen linearen Optimierung benutzt werden).

Bemerkung 3: (bezieht sich auf eine Behauptung von algebrafreak)
Ich glaube die Behauptung ist falsch, einfach "nur" die Ungleichungen durch Gleichungen zu ersetzen ( selbst wenn diese vorher auf eine "Normalform" mit der ggt Bedingung gebracht wurden) liefert nicht immer die genaue Charakterisierung der schwarzen Punkte. (werd aber nochmal drüber nachdenken)

So, musste das nur mal zu den schwarzen Punkten schreiben,
nun werd ich mir mal die Sache mit dem "deep partial gauss eliminator" anschauen.

MfG Mirona
Mirona
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 13.01.2005
Beiträge: 239

BeitragVerfasst am: 14 Jan 2005 - 16:51:19    Titel: Upsa

Der Post oben war von mir.
Irgendwie nicht eingeloggt. Embarassed

Mirona
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Mathe-Forum -> Lineare Optimierung
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Gehe zu Seite Zurück  1, 2, 3  Weiter
Seite 2 von 3

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum