Zählen Sie einige extreme Punkte in der Nähe der optimalen Lösung auf

Question

Ich bin auf der Suche nach einem einfachen Weg, um viele "gute" Lösungen in einem LP-Problem (nicht MIP) mit CPLEX, und nicht nur (eine der) optimale Basislösung (s). Mit "guten" Lösungen meine ich, dass die entsprechenden objektiven Werte nicht so weit vom wirklichen optimalen Wert entfernt sind. Solch ein Lösungspool könnte dem Entscheider helfen ...

Genauer gesagt, wenn man eine bestimmte Polyeder Ax < = b mit x> = 0 und eine Zielfunktion z = cx will, möchte ich maximieren, nachdem ich die LP ausgeführt habe, Ich kann den optimalen Wert z * erhalten. Dann möchte ich alle Extrempunkte des Polyeders durch den Satz von Einschränkungen

Ax <= b 
cx >= z* - epsilon 
x >= 0 

gegeben aufzuzählen, wenn epsilon eine gegebene Toleranz ist.

Ich weiß, dass CPLEX Möglichkeit bietet, Lösung Pool zu generieren (siehe here), aber es wird nicht funktionieren, da diese Methode für MIP ist: es zählt alle Lösungen einer IP (oder eine Lösung für jede gegebene Menge von festen Ganzzahl Variablen, wenn das Problem ein MIP ist).

Ein interessanter effizienter Weg ist es, die benachbarten Lösungen der optimalen Basislösung zu betrachten, dh alle benachbarten Extrempunkte: wenn das Polyeder nicht degenerativ ist, für jedes Paar Basisvariable x_B und nicht-Basisvariable x_N, Ich berechne die grundlegende Lösung, die erhalten wird, wenn x_B die Basis verlässt und x_N in die Basis eintritt. Dann werfe ich die Lösungen mit cx < z * -epsilon, und für die anderen wiederhole ich den Vorgang. [Ich weiß, dass ich diesen Algorithmus verbessern könnte, aber das ist die allgemeine Idee].

Die routine CPPXpivot der Callable Library könnte helfen, diese Schwenkoperation zu tun, aber ich fand keine Entsprechung in der C++ API (Concert-Technologie). Weiß jemand, ob ein solches Äquivalent existiert oder könnte er mir einen anderen Weg vorschlagen, mein ursprüngliches Problem zu lösen?

Vielen Dank :)!

Rémi L.

Answer 1

Es ist eine interessante Möglichkeit, diese geeignet mit der Cplex Lösung Pool zum zu machen. Verwenden Sie binäre Variablen, um die aktuelle Basis zu codieren, z. basis[k] = 0 bedeutet nonbasic und basis[k] = 1 angibt, Variable (oder Zeile) k ist grundlegend. Natürlich haben wir sum(k, basis[k]) = m (Anzahl der Zeilen). Schließlich haben wir x[k] <= basis[k] * upperbound[k] (d. H. Wenn nichtbasisch dann Null - positive Variablen vorausgesetzt). Wenn wir dies zu dem LP-Modell hinzufügen, erhalten wir eine MIP und können (alle oder einige, optimale oder nahezu optimale) Basen unter Verwendung des Cplex-Lösungspools aufzählen. Siehe here und here.