Integer Linear Programming Problem oder nicht?



  • Hi.

    Ich habe die Gleichung y=An\vec{y} = A \vec{n}, bei der n\vec{n} ein Vektor aus ganzen Zahlen ist. Ich suche fuer diese Gleichung jetzt alle Loesungen n\vec{n}, bei denen y\vec{y} in einem bestimmten, vorgegebenen, kompakten Gebiet liegt. Dieses Gebiet kann man durch eine Reihe von linearen Constraints angeben, also im Prinzip y_iminy_i<yimaxy\_i^\text{min} \le y\_i \lt y_i^\text{max}.

    Wie loest man dieses Problem am elegantesten? Ich habe das Gefuehl, dass ich mir eine unnoetig komplizierte Loesung erdacht habe. Mein Ansatz waere, eine kuenstliche lineare Optimierungsbedingung einzubauen, durch die ich praktisch die minimal abweichende Loesung zu einer bestimmten Flaeche suche. Dann suche ich nach der zweitbesten Loesung, indem ich noch ein Constraint hinzufuege, das den minimalen Abstand zu der Flaeche erhoeht und so weiter. Ich bastel mir da also kuenstlich eine Folge von Integer Linear Programming Problems draus. Diese zusaetzliche Optimierungsbedingung ist aber etwas, was mich eigentlich nicht interessiert und ich frage mich, ob ich hier nicht einen ganz einfachen, eleganten Ansatz uebersehe.

    Hat einer von Euch eine gute Idee, wie man das Problem angehen koennte?



  • Als ich mal ein ähnliches Problem hatte, bin ich vorgegangen wie folgt:

    1. alle Constraints aufsteigend nach ihrer Länge (d.h. Zahl der Summanden) sortiert
    2. eine Zuordnung VariableListe der referenzierenden Constraints angelegt (unter Beibehaltung der in Schritt 1 erlangten Reihenfolge)
    3. den gesamten Definitionsbereich durchprobiert, dabei für jeden Lösungskandidaten alle Constraints in der angegebenen Reihenfolge überprüft
    4. (für deinen Anwendungsfall nicht relevant) falls eine Lösung gefunden wurde, ggf. die Kostenfunktion evaluieren und das Ergebnis mit früheren Lösungen vergleichen

    Das ist immer noch brute force, aber sowohl in meinen Tests (z.B. mit diesem schönen Rätsel) als auch im realen Einsatz führte das zu vernachlässigbaren Rechenzeiten. Entscheidend für die Effizienz ist der erste Punkt. Allerdings war ich an der besten Lösung interessert und nicht an allen Lösungen; je nachdem wie groß die Lösungsmenge ist, kann das natürlich länger dauern.



  • Naja, den gesamten Definitionsbereich kann ich nicht so gut durchscannen. n\vec{n} ist schliesslich ein Vektor mit Elementen aus den ganzen Zahlen. Aber ich naehere mich gedanklich irgendwie einer Loesung an, die in diese Richtung geht. Und zwar kann ich vielleicht ueber eine Lattice Reduction den fuer mich relevanten Teil des Definitionsbereichs fassbar machen.



  • audacia schrieb:

    Das ist immer noch brute force, aber sowohl in meinen Tests (z.B. mit diesem schönen Rätsel) als auch im realen Einsatz führte das zu vernachlässigbaren Rechenzeiten.

    Integer Linear Programming Problems sind im Allgemeinen NP schwer. ...ebenso wie die eben erwaehnte Lattice Reduction. Es koennte also inherent an der Problemstellung liegen, dass nichts wesentlich besseres als Brute Force moeglich ist. Die einzige Frage ist, ob meine Problemstellung nicht noch einige Einschraenkungen liefert, die mich aus dieser Komplexitaetsklasse rausbringen.

    ...zum Glueck ist meine Problemgroesse nicht gross (AA ist eine 3x3 Matrix).



  • Stimmt, ich hatte vergessen zu erwähnen, daß ich von beschränkten Zahlenbereichen ausgehen konnte, d.h. ni{a,a+1,...,b}n_i \in \{a, a+1, ..., b\}. Wenn du das nicht kannst, wirds schwieriger.

    Weißt du sonst nichts über y\vec{y} und die Einträge in AA? Sind das auch ganze Zahlen?



  • audacia schrieb:

    Weißt du sonst nichts über y\vec{y} und die Einträge in AA? Sind das auch ganze Zahlen?

    Oh, das ist ein guter Punkt. Bei ILPPs sind sie das eigentlich. Bei mir aber nicht. Die Eintraege von y\vec{y} und AA sind reellwertig. Ich sehe zwar nicht auf den ersten Blick, dass man damit etwas anfangen kann, aber ich kenne mich mit diesen Problemstellungen auch nicht so sehr aus. Ich sollte wohl etwas recherchieren, wie das jetzt genau zu klassifizieren ist.

    EDIT: Es sieht so aus, als ob diese Groessen nur bei den ILPPs auf Wikipedia ganzzahlig sind. In meinem Buch wird da nicht unterschieden. Insofern wird man an dieser Stelle nichts rausholen koennen. Haette mich auch ueberrascht.



  • Gregor schrieb:

    EDIT: Es sieht so aus, als ob diese Groessen nur bei den ILPPs auf Wikipedia ganzzahlig sind. In meinem Buch wird da nicht unterschieden. Insofern wird man an dieser Stelle nichts rausholen koennen. Haette mich auch ueberrascht.

    Ich weiß auch nichts Genaueres, aber ich denke schon, daß rationale Koeffizienten das Problem erleichtern. Dazu folgende Überlegung:

    Das Gleichungssystem y=An\vec{y} = A \vec{n} für niQn_i \in \mathbb{Q} sei oBdA unterbestimmt (hätte A vollen Rang, gäbe es nur eine Lösung, die du direkt berechnen könntest). Dann kannst du ein reduziertes Gleichungssystem angeben, in dem du einen oder zwei Parameter n_1,n_2n\_1, n\_2 frei wählen kannst und sich die verbleibenden Parameter durch die Gleichungen ergeben. Waren alle Koeffizienten rational, Aij,yiQA_{ij}, y_i \in \mathbb{Q}, so sind auch alle Koeffizienten des reduzierten Gleichungssystems rational. Wählst du dann für deine freien Parameter ganze Zahlen, die Vielfache der Nenner aller ihrer Koeffizienten in den Gleichungen sind, so bekommst du ganzzahlige Lösungen. Allerdings hättest du am Aufzählen aller Lösungen keine Freude, weil es immer noch unendlich viele sind 🙂

    Die ganze Überlegung ging freilich davon aus, daß y\vec{y} bekannt ist. Für rationale Grenzen, y_imin,y_imaxQy\_i^\mathrm{min}, y\_i^\mathrm{max} \in \mathbb{Q}, sollte sich obiges Vorgehen aber leicht erweitern lassen.

    Edit: Fehler in der Erklärung oben korrigiert. Außerdem wird die Sache dadurch, daß für y\vec{y} nicht konkrete Werte, sondern nur Wertebereiche vorgegeben sind, viel unangenehmer, als ich zuerst dachte. Ich habe schon länger nicht mehr über ILP nachgedacht und hatte nur Lineare Algebra im Kopf 🙄



  • Wenn das Lösungspolytop (und das relaxierte Polytop ohne Ganzzahligkeitsbedingungen) nicht zu entartet aussieht in deinem Anwendungsfall, würde ich mit einer ganz simplen Idee anfangen: Bestimme untere und obere Grenzen für alle nin_i mit min/maxni s.t. AnymaxAnymin\min / \max n_i \text{ s.t. } An \leq y^{\max} \wedge -An \leq -y^{\min} (also sechs LPs, nicht ILPs) und teste alle Punkte im entstehenden Würfel, ob sie im Lösungspolytop liegen.



  • Ich meine natürlich einen Quader und keinen Würfel. Man muss dafür auch keine sechs LPs lösen, sondern muss nur A1ymaxA^{-1}y^{\max} und A1yminA^{-1}y^{\min} ausrechnen. Wenn man den Ansatz verfeinern will, kann man dann zuerst Minimum und Maximum für n_1 bestimmen, alle möglichen Werte für n_1 durchiterieren und für n_2 dasselbe bei fixiertem n_1-Wert machen. Hat man dann n_1 und n_2 fixiert, bleibt vom ILP nur noch eine Ungleichung für n_3 übrig.


Log in to reply