Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

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


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 08 Jan 2005 - 19:48:05    Titel: Lineare Optimierung

Hallo zusammen.

Es ist wohl bekannt, dass man auf der Suche nach Lösungen eines linearen Optimierungsproblems auf dem "Rand" des induzierten Polytops zu suchen braucht (eigentlich sogar nur auf den Ecken, aber die Abschwächung ist hier wichtig). Für den ganzzahligen Fall gibt es sowas wie Ecken (als Schnittpunkte meherer Halbräume) nicht, da die formalen Schnittpunkte womöglich nicht ganzzahlig sind.

Frage: Kennt hier jemand einen ähnlichen Satz, wie oben, für den ganzzahligen Fall?

Vorschlag: Der Rand eines Halbraumes ist ein affiner Unterraum (kein VR, sondern einfach die Lösungsmenge einer Gleichung), die die Grenze davon beschreibt. Die Lösungen eines ganzzahligen linearen Optimierungsproblems liegen auf den Rändern der Halbräume.

Beispiel: Halbraum {(x,y} | y > -2 x + 1}. Ist offensichtlich dasselbe, wie {(x,y) | y >= -2x + 2}. Darstellende Gerade y = -2x + 2. Somit Rand {(x,y) | y = -2x+2}.

Ich habe gesehen, dass hier viele sich mit Simplex auskennen. Ich freue mich über JEDE Anmerkung, egal wie weit sie von Thema weg ist.

Anmerkung: Sollte sich obiges (und noch ein paar Sachen mehr) bestätigen, so könnte ich womöglich einen NEUEN Ansatz für's effiziente Lösen von ILP's angeben.
Thomas_Da
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 21.11.2004
Beiträge: 352
Wohnort: Darmstadt

BeitragVerfasst am: 08 Jan 2005 - 20:14:58    Titel:

Mhm, da ich meine Aufzeichnungen gerade nicht parat habe kann ich nicht so viel dazu sagen. (Ich schaue aber noch mal nach.)

Es gibt da aber sicherlich einige Überlegungen zu, z.B. gibt es einen Namen für die Teilmenge (auch ein Polytop) eines Polytops, das alle ganzzahligen Lsg. des Ursprungspolytops enthält und dessen Ecken ganzzahlige Lsg sind. Im Grunde suchst Du ja genau das. Aber ich glaube, da gab es kein Verfahren, um die "Ränder" (Gleichungen) zu bestimmen.

Wie Du sicherlich weisst, löst man solche Aufgaben durch Branch & Bound.
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 08 Jan 2005 - 20:30:29    Titel:

Zitat:
ganzzahligen Lsg. des Ursprungspolytops enthält und dessen Ecken ganzzahlige Lsg sind. Im Grunde suchst Du ja genau das


Die Idee hinter dem, was ich will ist, dass ich nicht nur "und"-Verknüpfungen, sondern auch "oder"-Verknüpfungen anschauen kann. Demnach kann ich das Innere vom Polytop (auch im Reelen) "rausschmeissen", indem ich eine Disjunktion der Ränder konjunktiv an das Problem anknüpfe. Dann habe ich mein "Branch & Bound".

Zitat:
Aber ich glaube, da gab es kein Verfahren, um die "Ränder" (Gleichungen) zu bestimmen.


Meinst Du, das ist algorithmisch nicht lösbar? Der Witz ist, dass jede starke Un-Gleichung in in Z zu einer schwachen Gleichung äquivalent ist. Und diese kann man auf eine Normalform bringen, sodass der Rand nicht leer ist.

Beispiel: 3 x + 6 y < 7. Man bekommt x + 2*y <= 2. Dabei ist der Rand x+2*y = 2 und ist nicht leer.

Zitat:
Wie Du sicherlich weisst, löst man solche Aufgaben durch Branch & Bound


Ich habe mir dazu schon einiges angeschaut. Ich sollte vielleicht noch mehr anschauen. Smile

Es ist sicherlich klar, dass man in diesem Bereich heutzutage nichts wirklich neues erfinden kann. Ich wende eine ganz spezielle Art der "Gauss-Elimination" (wenn man das überhaupt so nennen kann) auf Systeme von (Un-) Gleichungen an, so dass man "um's Eck" Lösungen von ILP's bekommt.

Vielen Dank.

P.S: Weisst Du, was geil wäre: Wenn Du vielleicht Literatur wüsstest, auf die Ihr in eurer Vorlesung verwiesen worden seid.
Thomas_Da
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 21.11.2004
Beiträge: 352
Wohnort: Darmstadt

BeitragVerfasst am: 08 Jan 2005 - 21:09:17    Titel:

Ich bin nicht so vertraut mit den mathematischen Begriffen und habe wenig mit Herleitungen und Beweisen von Lösungsalgorithmen zu tun. Deshalb musst Du für mich das noch einfacher erklären.


Was meinst Du mit ...

... '"und"-Verknüpfungen, sondern auch "oder"-Verknüpfungen', also auch nichtkonvexe Polytope?
... 'das Innere vom Polytop (auch im Reelen) "rausschmeissen"'
... 'Disjunktion der Ränder konjunktiv an das Problem anknüpfe'
... 'starke Un-Gleichung in in Z'
... 'schwachen Gleichung'
... 'Und diese kann man auf eine Normalform bringen, sodass der Rand nicht leer ist.'

Wenn ich Dein Problem verstehen soll, dann musst Du mir wohl etwas "Nachhilfe" geben. (Ich weiss noch nicht, was Du genau suchst.)

Und kannst Du mal für das Beispiel 4x + 7y < 28 den Rand angeben.

Unser Operation Research Prof. hat da sein eigenes Buch, die Verfahren und so aber sicherlich nicht erfunden, ich kann morgen Abend mal nachschauen.


PS: Mit kniffeligen Aufgaben beschäftige ich mich doch gerne, insbesondere, wenn ich dann noch etwas lernen kann.
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 08 Jan 2005 - 21:42:42    Titel:

Das Ziel ist einen schnellen Ansatz für ILP's zu finden, der nicht (wie die meisten) schon für zahlen mit Betrag 10 abkackt.

Zitat:
... '"und"-Verknüpfungen, sondern auch "oder"-Verknüpfungen', also auch nichtkonvexe Polytope?


Wenn q1,...,qn deine Constraints sind und k deine Kostenfunktion, so ist die Menge der zulässigen Lösungen M durch die "Formel":

F = q1 und q2 und ... und qn

gegeben. D.h. M = { (x1,...,xl) | x1,...,xl erfüllen F}. Und ein (minimierendes) LP ist durch die (quantifizierte) Formel:

F' = (x1,...,xl) erfüllen F und für alle (y1,...yl) gilt [(y1,...,yl) erfüllt F => k(x1,...,xl) <= k(y1,...yl)]

gegeben.

Das ist eine naive algebraische Formulierung von LP. Z.B. für das triviale Problem:

Minimiere x+y
Unter
2*x > 1
2*y > 1

2x > 1 and 2*y > 1 and forall u forall v [(2u > 1 and 2v > 1) impl x+y <= u+v].

Der Vorteil von dieser Betrachtungsweise ist, dass ich nicht nur auf "und"-Kombinationen von Zusicherungen beschränkt bin, sondern auf beliebige Modifikationen davon mit "oder" und sogar "nicht" zurückgreifen kann.

Ich verfüge über ein Verfahren, dass aus Formeln wie oben äquivalente Formeln ohne Quantoren macht, die dann, wenn man das Problem gut formuliert hat sowas rauswefen, wie:

x = 1 and y = 1

Zitat:
... 'das Innere vom Polytop (auch im Reelen) "rausschmeissen"'


Für das Polytop ist ja das Innere bei LP's (zumindest im Reellen) uninteressant. Was man machen kann, ist Folgendes (q1,q2,...,qn) Constraints. (r1,r2,...,rn) "Ränder" der Constraints:

F := q1 and q2 and ... and qn and (r1 or r2 or ... or rn).

Wenn man etwas nachdenkt, so hat F als Lösungsmenge die Hülle des Polytops.

Zitat:
... 'Disjunktion der Ränder konjunktiv an das Problem anknüpfe'


siehe obiges. Ich habe (r1 or r2 or ... or rn) mit einem and angehängt und innen
sind laute or's.

Zitat:
... 'starke Un-Gleichung in in Z'


Stark bedeutet mit einem < oder >. Schwach mit einem <= oder >=

... 'Und diese kann man auf eine Normalform bringen, sodass der Rand nicht leer ist.'

Ist überhaupt nicht kompliziert. Man kann den ggT der Koef. von Variablen rausdividieren, und den konstanten Anteil so anpassen. Z.B. oben

3 x + 6 y < 7 wäre ja sowas, wie
x + 2 y < 7/3

und

7/3 ist 3.5 also runterrunden 3

Im Falle 4x+7y < 28 kann man nichts machen. Der Rand ist

4x + 7y = 27

-------------------------------------------

Der Witz an den ganzzahligen Problemen ist, dass man einerseits unmittelbar in Kongruenzen "versinkt" und andererseits keine dichte Menge hat, sodass man im bösen Fall alles durchprobieren muss. Die Lösungsmenge der (in R) schönen Gleichung

10 x + b = 0

bzgl. x ist in Z total hässlich. Es muss zusätlich

b = 0 (mod 10)

gelten. Es stellt sich heraus, dass für Gleichungen das ganze absolut easy ist. Und die Idee ist irgendwie aus Ungleichungen Gleichungen zu machen. In dem Fall z.B. dadurch, dass man das Innere rausscneidet und sich nur auf Seiten bewegt.
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 08 Jan 2005 - 22:04:06    Titel:

Ich habe eine kleine Skizze erstellt.



-Kreuze sind Punkte, die keine Sau interessieren
-Schwarze Punkte sind die Ränder
-Weisse Punkte sind "nicht zulässigen" Ränder
-Komischer Punkt ist z.B. die Lösung für die Zielfunktion x+y
-Geraden sind die reellen Ränder
Thomas_Da
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 21.11.2004
Beiträge: 352
Wohnort: Darmstadt

BeitragVerfasst am: 08 Jan 2005 - 23:18:53    Titel:

algebrafreak hat folgendes geschrieben:
F = q1 und q2 und ... und qn
...
Der Vorteil von dieser Betrachtungsweise ist, dass ich nicht nur auf "und"-Kombinationen von Zusicherungen beschränkt bin, sondern auf beliebige Modifikationen davon mit "oder" und sogar "nicht" zurückgreifen kann.

Anstelle der "und" könnten nach deiner Idee bei F auch "oder" sowie "nicht" in einer beliebigen Schachtelung verwendet werden?
Zitat:
Ich verfüge über ein Verfahren, dass aus Formeln wie oben äquivalente Formeln ohne Quantoren macht, die dann, wenn man das Problem gut formuliert hat sowas rauswefen, wie:
x = 1 and y = 1

Mit Quantoren meinst Du wohl die Verknüfung durch "und", "oder" sowie "nicht" in F? Eine "Formel wie oben" ist dann in diesem Fall das F?
Kannst Du mal ein Bsp. aufführen (auch ohne Weg) mit "Formel wie oben" und Formel ohne Quantoren?
Zitat:
F := q1 and q2 and ... and qn and (r1 or r2 or ... or rn).

Deine rj sind die Geraden, wie in deinem Bild und nicht Teilmengen der ganzzahligen Randpunkte, oder?
Zitat:
Der Witz an den ganzzahligen Problemen ist, dass man einerseits unmittelbar in Kongruenzen "versinkt"

Was heißt das?
Zitat:
Es stellt sich heraus, dass für Gleichungen das ganze absolut easy ist. Und die Idee ist irgendwie aus Ungleichungen Gleichungen zu machen. In dem Fall z.B. dadurch, dass man das Innere rausscneidet und sich nur auf Seiten bewegt.

Was meinst Du damit genau?

Du suchst also eine Möglichkeit alle schwarz gefärbten Punkte zu ermitteln?
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 08 Jan 2005 - 23:35:29    Titel:

Zitat:
Anstelle der "und" könnten nach deiner Idee bei F auch "oder" sowie "nicht" in einer beliebigen Schachtelung verwendet werden?


Ja. Allerdings soll das natürlich der Endlösung dienlich sein Smile Der Benutzer gibt sein ILP oder LP nach wie vor als eine Liste von Zuseicherungen und Kostenfunktion ein. Ich versuche das Problem so zu formalisieren im inneren der Software, dass ich es mit meinen Mitteln leichter verarbeiten kann. Und das benötigt Gleichungen. Bei denen ist "relativ" egal, ob sie in einem "und" oder in einem "oder" stehen.

Zitat:
Mit Quantoren meinst Du wohl die Verknüfung durch "und", "oder" sowie "nicht" in F? Eine "Formel wie oben" ist dann in diesem Fall das F?
Kannst Du mal ein Bsp. aufführen (auch ohne Weg) mit "Formel wie oben" und Formel ohne Quantoren?


Nicht ganz. Ein Quantor ist von der Form "exists var" oder "forall var". Eine Formel exists var formel" bedeutet: Es gibt ein var, dass formel erfüllt. Analog für forall. Das kennst Du bestimmt aus Grundlagenvorlesungen.

Beispiel: Im reellen ist

exists x a*x =b

zu einer quantorenfreien Formel

(a = 0 and b=0) or a <> 0

äquivalent. Obiges sagt aus: es gibt für a*x = b eine erfüllende belegung in a und b. Das ist eben genau dann, wenn beides a und b gleich 0 sind, oder a ungleich null (1 Nullstelle).

Ein Optimierungsproblem ist eben, wie oben ein quantifiziertes Problem.
Zitat:

Deine rj sind die Geraden, wie in deinem Bild und nicht Teilmengen der ganzzahligen Randpunkte, oder?


Doch. War wohl scheisse formuliert. Im reellen wären das die Geraden. Im ganzzahligen will ich gerade die schwarzen Punkte anstatt der Geraden nehmen. Und da hoffe ich, dass ich die eben leicht finden kann.

Aber vor allem hoffe ich, dass die Lösugnen nur auf den schwarzen Punkten aufzufinden sind.

Zitat:
Was heißt das?


In kongruenzen versinken, bedeutet, dass man so viele davon bekommt, dass man sich nicht mehr auskennt. Obiges beispiel:

exists x 10 x = b

Im reellen äquivalent zu true. In Z äquivalent zu

b = 0 (mod 10)

Und wenn man das iteriert macht (also für exists x exists y exists z blah), dann hat man unmengen an Kongruenzen. Sad

Zitat:
Was meinst Du damit genau?


Für Gleichungen läuft die Sache auf einen Spezieallfall, der heisst "deep partial Gauss-(Quantifier)-Elimination". Für diesen Speziallfall vergrössert sich die Formel im wesentlichen nur um eine Kongruenz (übrigens Beispiel wäre oben).

Wenn es zutreffen sollte, dass die Lösungen nur auf "schwarzen Punkten" sind, so kann man eben alles auf diesen Speziallfall zurückführen.

Zitat:

Du suchst also eine Möglichkeit alle schwarz gefärbten Punkte zu ermitteln?


Ich hoffe ich kann das bereits. Ich möchte wissen ob die Überlegungen von oben richtig sind. D.h. Die Lösungen eines ILP's sind auf schwarzen Punkten. Wenn das gilt, muss man nur noch ein wenig mit Kongruenzen kämpfen Smile
Thomas_Da
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 21.11.2004
Beiträge: 352
Wohnort: Darmstadt

BeitragVerfasst am: 08 Jan 2005 - 23:54:51    Titel:

Zunächst möchte ich mich für die ausführlichen Erklärungen bedanken.
algebrafreak hat folgendes geschrieben:
Ich möchte wissen ob die Überlegungen von oben richtig sind. D.h. Die Lösungen eines ILP's sind auf schwarzen Punkten. Wenn das gilt, muss man nur noch ein wenig mit Kongruenzen kämpfen Smile

Ja die optimale Lösung muss in einem der schwarzen Punkte liegen, wenn die Zielfunktion linear ist. Das ist einfach zu beantworten und für einen Mathematiker vielleicht auch einfach zu beweisen. (Für mich also nicht Wink )
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 09 Jan 2005 - 00:17:35    Titel:

Vielen Dank für die Mühe.

Zitat:
Ja die optimale Lösung muss in einem der schwarzen Punkte liegen, wenn die Zielfunktion linear ist. Das ist einfach zu beantworten und für einen Mathematiker vielleicht auch einfach zu beweisen. (Für mich also nicht Wink )


Jo. Denke ich auch. Sonst hätte ich mir den Tumult gespart. Wie zeigt man sowas? Hmmm. Ich habe den reellen Beweis nur überflogen, muss mir den wohl nochmal reinziehen.
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 1, 2, 3  Weiter
Seite 1 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