lineare (Un)Gleichungssysteme lösen

30/05/2015 - 08:21 von Jan Bruns | Report spam
Tag.

Um mir so ein wenig Überblick über die Zusammenhànge rund um
die lineare Optimierung, und eigentlich insbesondere den
Übergang von ganzzahlig-linearen Optimierungsproblemen zur
schlichten kombinatorischen Optimierung zu verschaffen, habe
ich mich in den letzten Tagen etwas mit kontinuierlichen,
linearen Ungleichungssystemen beschàftigt.

Dabei bin ich einer Eigenartigkeit begegnet, die irgendwie
so zwischen blödem Implementationsfehler und realer
Fehleinschàtzung anzusiedeln sein wird, daß ich da grad
irgendwie mit überfordert bin, weiterzugucken.

Also ausgehend von einem um Gleichungen bereinigten
linearen (Un)Gleichungssystem der Form

+a1*x1 +a2*x2 ... an*xn >= a0
+b1*x1 +b2*x2 ... bn*xn >= b0
...
+z1*x1 +z2*x2 ... zn*xn >= z0

mit auf Einheitslànge normalisierten Koeffzienten mache ich,
ab einem zufàllig gewàhlten Startpunkt P etwa sowas

http://abnuto.de/jan/code/lp/linfail1.svg

um einen Folgepunkt P2 zu finden, der nàher am Lösungs-
Hyperpolyeder liegt (P2 ist demnnach P, verschoben um die
Hyper-Flàchennormale (bestehend aus den oben schon erwàhnten,
normalisierten Koeffizenten) der am stàrksten verletzten
Ungleichung, gerade so weit, daß diese nicht mehr verletzt
wird). Sowas in der Art. So weit ok.

Weiter überprüfe ich in jedem Schritt, ob nicht einige von P
ausgehende Strahlen vielleicht das Lösungshyperpolyeder
kreuzen. Das ist schliesslich, was ich letzlich haben will:
einen Punkt P, von dem aus beliebige Strahlen P+k*raydir im
Bereich k_min <= 0 bis 0 <= k_max im Lösungspolyeder liegen.

Möglicherweise kann man noch für Fàlle, in denen die
Strahlrichtung raydir parallel zu einer Hyperbene liegt
(also Sklarprodukt raydir.normale=0) noch irgendwelche
Gleichungen gewinnen, was ich aber erstmal nicht versuche
(ich verwende erstmal "vollgefüllte" Richtungen).

Das seltsame ist jetzt:
Trotz enorm guter Annàherung von P an das Lösungpolyeder
(ich bekomme teils Ausgaben mit Abstànden wie 1.0e-100,
also numerisch làngst weit im Rahmen der Rechengenauigkeit
von IEEE Floats) mag nicht einer von tausenden Strahlen ab
P des Polyeder kreuzen. Und ich bin jetzt irgendwie hin- und
hergerissen, ob ich eher meinen soll, daß das natürlich
passieren kann, oder doch eher meinen soll, daß das
unwahrscheinlich ist.

Fàllt euch dazu was ein?

Gruss

Jan Bruns


PS:
Hier eine JavaScript Implementation:
http://abnuto.de/jan/code/lp/test_mps.html

Beispieleingaben (von netlib/lp):

Funktioniert meist:
http://abnuto.de/jan/code/lp/adlittle.emps.mps

Zeigt das beschriebene Problemverhalten:
http://abnuto.de/jan/code/lp/recipe.emps.mps
 

Lesen sie die antworten

#1 Jan Bruns
30/05/2015 - 10:14 | Warnen spam
Jan Bruns:

Fàllt euch dazu was ein?



Nachdem ich das jetzt gepostet habe, fàllt mir ein, waoran es liegen
könnte:

In dem Ungleichungssystem können Gleichungen versteckt sein.
Also z.B. sowas:

+x+y >= a
-x-y >= -a

Wenn dann z.B. a=0 und y=0, dann kann x beliebig nahe an 0 angenàhert
werden, ohne daß beide Gleichungen erfüllt sind, was dann wohl auf
Strahlen, die diese Hyperebenen schneiden, nicht anders aussieht.

Gruss

Jan Bruns



PS:
Der Link auf den eigentlichen Quelltext fehlte noch, der
ist dadurch, daß das in einen WebWorker-Thread eingebunden
war, etwas im Quelltext der HTMLSeite versteckt gewesen:

http://abnuto.de/jan/code/lp/mpsread.js

Ähnliche fragen