Integer Variablen

Computer: Software & Programmierung Programmierung allgemein
#1

Hallo zusammen,

ich habe ein etwas spezielles Problem. In einem bisher recht unbekannten Programm (LPL) soll eine Lineare Optimierung durchgeführt werden. Hierbei müssen zwei von vier Variablen ganzzahlig sein. Wenn ich die Variablen als „integer“ definiere, kann der Solver das Problem nicht mehr lösen (Simplex, etc…). Jetzt als die Frage:
Taucht dieses Problem in etwas dichter befahrenen Gebieten der Informatik auch auf? Wenn ja, wie schafft man es Variablen ganzzahlig zu halten, ohne sie als integer zu definieren.
(allgemeine Formulierung wäre prima)
Dankeschön!

Philipp

#2

Moien

Wenn ich die Variablen als „integer“
definiere, kann der Solver das Problem nicht mehr lösen
(Simplex, etc…).

Simplex* und Co gehen von einer kontinuierlichen Bewertungsfunktion aus. Wenn 2 Variablen Integer sind ist das nicht mehr der Fall.

Beispiel: Das Simplex testet bei 4 Variablen immer 5 Funktionswerte. Sagen wir (Startpunkt 1/4, 1/4, 1/4, 1/4, Schrittweite 0.1):

0.25, 0.25, 0.25, 0.25
0.35, 0.25, 0.25, 0.25
0.25, 0.35, 0.25, 0.25
0.25, 0.25, 0.35, 0.25
0.25, 0.25, 0.25, 0.35

Deine Integer-Vorgabe macht da draus:

0.25, 0.25, 0, 0
0.35, 0.25, 0, 0
0.25, 0.35, 0, 0
0.25, 0.25, 0, 0
0.25, 0.25, 0, 0

Und damit hat das System keine mehr Möglichkeit jemals vom Wert 0 für die 2 Integer weg zu kommen. Wählst du aber eine Schrittweite von 5 sollte es am Anfang zumindest ein bisschen laufen. Gewonnen hast du wenn der Optimiercode eine minimale Schrittweite von 1 definieren kann.

Taucht dieses Problem in etwas dichter befahrenen Gebieten der
Informatik auch auf?

Noch dichter als die Optimierung wird eigentlich nichts befahren… Ausser evtl. noch Spiele.

cu

* Welches Simplex-Verfahren meinst du eigentlich, es gibt da 2 … ?

#3

Hallo zusammen,

ich habe ein etwas spezielles Problem. In einem bisher recht
unbekannten Programm (LPL) soll eine Lineare Optimierung
durchgeführt werden. Hierbei müssen zwei von vier Variablen
ganzzahlig sein.

Hallo Philipp,

wenn Du vorschreibst, dass die Zahlen ganzzahlig sein sollen,
wird das Problem im allgemeneinen NP-Vollständig und damit nicht effizient lösbar, siehe „Integer Programming“.

Ausweg mit Linearer Optimierung: „Randomized Rounding“. Am Ende werden die gebrochenen Zahlen zufällig auf oder abgerundet; gibt natürlich nicht das optimale Ergebnis.

Ansonsten könntest Du versuchen, das Problem als Flussproblem hinzuschreiben. Die lassen sich effizient lösen, sind aber weniger ausdrucksstark, siehe http://de.wikipedia.org/wiki/Fluss_(Graphentheorie).

Welches Problem soll denn genau optimiert werden?

Viele Grüße
Thorsten

#4

Hallo zurück,

Das Problem ist das Jacob- Modell, recht komplizierte Sache!
Ich habe ein, zwei Beispiele in der Literatur gefunden, die einfach vollmundig behaupten, es sei mit geeigneter Software zu lösen und man müsse Ganzzahligkeit vorgeben. Wird dann einfach gerundet?

Dankeschön,

Phil

#5

Hallo zurück,

Das Problem ist das Jacob- Modell, recht komplizierte Sache!

Das Problem kenn ich leider nicht.

Ich habe ein, zwei Beispiele in der Literatur gefunden, die
einfach vollmundig behaupten, es sei mit geeigneter Software
zu lösen und man müsse Ganzzahligkeit vorgeben. Wird dann
einfach gerundet?

Die Frage ist, ob das Problem exakt gelöst werden muss,
oder ob eine gute Lösung ausreichend ist?

Exakte Lösung -> lange Rechenzeit mit Algorithmen, die den gesammten Lösungsraum absuchen bzw. intelligent ausschliessen.

Wenig Rechenzeit -> nur ne gute Lösung -> Suchheuristiken / evolutionäre Algorithem.

Hier ein interessanter Link:
http://www-unix.mcs.anl.gov/otc/Guide/faq/linear-pro…

Wahrscheinlich ist es am besten, nach

Mixed integer (MILP or MIP)

zu suchen, ob es da Software gibt, die das Lösen können. (Matlab /MOSEK) Kenn ich mich aber nicht mit aus.

Wieviele Variablen hat den das Problem?

Grüße
Thorsten

Dankeschön,

Phil

#6

Hallo noch mal,

es hat sich mittlerweile rausgestellt, dass das Programm nicht die Solver mitgeliefert bekommen hat, die im Reference Manual angegeben wurden, man musste erst noch einen zusätzlichen Solver herunterladen, der das Ding dann als MIP erkennt.
Das Modell an sich ist sehr umfangreich und besteht aus vier Variablen und zwanzig konstanten, die als Matrizen oder Vektoren vorliegen.
Interessanterweise kommt die Lösung ohne Integer- Variablen sehr nah an die Musterlösung heran, das ganze als MIP könnte nicht weiter weg sein.
(Endwert bei ca. -80000 anstelle von ca. 300000, von den anderen Variablen ganz zu schweigen) Ist das normal? Ich hatte das selbe Problem bei einem ganz einfachen Modell, es kann also nicht wirklich an meiner Modellierung liegen.

Danke schon mal!

#7

Interessanterweise kommt die Lösung ohne Integer- Variablen
sehr nah an die Musterlösung heran, das ganze als MIP könnte
nicht weiter weg sein.
(Endwert bei ca. -80000 anstelle von ca. 300000, von den
anderen Variablen ganz zu schweigen) Ist das normal? Ich hatte
das selbe Problem bei einem ganz einfachen Modell, es kann
also nicht wirklich an meiner Modellierung liegen.

Die Fitnessfunktion eines LP ist schön konvex, wohingegen bei NP-vollständigen Problem (z.B. MIP) es auf die Eingabe ankommt. Es gibt natürlich auch einfache Eingaben, oder die Fitnesslandschaft sieht aus die Berge in den Alpen. D.h., es kann durchaus sein, dass Lösungen mit gleicher Fitness weit auseinander liegen und dazwischen sich schlechtere Lösungen befinden. Konkrete Erfahrungen mit MIP hab ich allerdings nicht.

Wie sind den die Fitnesswerte, wenn man die Lösungen in die optimierende Hyperebene bzw. Nebenbedingunen einsetzt?

Grüße
Thorsten