Durchführbarkeitsproblem der linearen Programmierung mit strengen Einschränkungen der Positivität

15

Es gibt ein System linearer Bedingungen . Ich möchte einen streng positiven Vektor , der diese Bedingungen erfüllt. Das heißt, wird für jede Komponente von . Wie kann ich einen LP-Solver verwenden, um einen solchen streng positiven Vektor (oder um zu bestätigen, dass kein existiert)? Ich kann nicht einfach ein anderes System von Bedingungen einführen , da die Gleichheit in einer LP immer zulässig sein muss - aber ich kann den LP-Solver mit wechselnden Zielfunktionen mehrmals verwenden. Ich denke, ich sollte die Slack-Variable-Methode verwenden, aber ich weiß nicht wie. ${\bf Ax} \leq {\bf b}$ ${\bf x} > 0$ $x_i > 0$ $x_i$ ${\bf x}$ ${\bf x}$ ${\bf x}$ $x_i > 0$

optimization linear-programming Sara
quelle

15

Sie können das Problem der Auswahl einer kleinen umgehen, indem Sie etwas ehrgeiziger vorgehen: Versuchen Sie, $\epsilon>0$ $\mathbf{x}$ so zu finden, dass $\mathbf{Ax}\leq \mathbf{b}$ und der kleinste Eintrag in $\mathbf{x}$ größte ist.

y = [\begin{matrix} x \\ ϵ \end{matrix}] \in R^{n + 1}

$\mathbf{y} = \begin{bmatrix} \mathbf{x}\\ \epsilon\end{bmatrix}\in\mathbb{R}^{n+1}$

x

$\mathbf{x}$

R^{n}

$\mathbb{R}^n$

max_{y} [0 \dots 0 1] \cdot y s.t. [A 0] y \leq b and 0 \leq [\begin{matrix} 1 & 0 & \dots & 0 & - 1 \\ 0 & 1 & \dots & 0 & - 1 \\ ⋱ & ⋮ \\ 0 & \dots & 1 & - 1 \end{matrix}] y .

$\max_y [0 \dots 0\ 1]\cdot \mathbf{y}\quad \text{s.t.}\quad [A\ \mathbf{0}]\mathbf{y}\leq\mathbf{b}\quad \text{and}\quad \mathbf{0}\leq \begin{bmatrix}1 & 0 & \cdots & 0 & -1 \\ 0 & 1 & \cdots & 0 & -1 \\ & \ddots & &\vdots \\ 0 & \cdots & & 1 & -1 \end{bmatrix}\mathbf{y}.$

Dies ist eine Neuformulierung des folgenden Problems:

max ϵ s.t A x \leq b and x \geq ϵ 1 .

$\max \epsilon \quad\text{s.t}\quad \mathbf{Ax\leq b}\quad\text{and}\quad \mathbf{x}\geq\epsilon\mathbf{1}.$

Dolch
quelle

Gut gemacht, das ist gleichbedeutend mit einem Trick eines Mitautors, den ich kürzlich in einer Veröffentlichung verwendet habe und der von mir vorgeschlagenen Vorgehensweise definitiv überlegen ist.

Aron Ahmadia

Einverstanden. Gut gemacht, Sir.

Geoff Oxberry

Das neu formulierte Problem kann ein unbegrenztes Ziel haben, wenn die Antwort auf das ursprüngliche Problem trivial ist. Zum Beispiel, wenn das System der Einschränkungen nur

. Das ist in Ordnung, solange Sie prüfen, ob der Rückgabestatus Ihres LP-Solvers machbar, optimal oder unbegrenzt ist, oder das

explizit

.

x \geq - 1

$x \ge -1$

ϵ

$\epsilon$

David Nehme

@DavidNehme: Man kann die Bedingung

hinzufügen , um ein beschränktes Ziel zu erhalten.

y_{n + 1} \leq 1

$y_{n+1}\le 1$

Arnold Neumaier

5

Für ein LP-Machbarkeitsproblem würde ich kein Standard-Simplex verwenden. Standard-Simplex-Algorithmen für Primzahlen (oder Dual-Simplex-Algorithmen) ermitteln nur die Eckpunkte der möglichen Menge der Primzahlen (oder Dual-Simplex-Probleme).

Nehmen wir an, dass die realisierbare Menge des Problems, das Sie tatsächlich lösen möchten, ist und dass Sie stattdessen das Problem lösen sollten ( ): $F = \{\mathbf{x}: \mathbf{Ax} \leq \mathbf{b}, \mathbf{x} > \mathbf{0}\}$ $F_{\varepsilon}$

\begin{aligned} min_{x} 0 \\ s.t. & A x \leq b \\ x \geq ε \cdot 1 . \end{aligned}

$\begin{alignat}{1} & \min_{\mathbf{x}} \quad 0 \\ \textrm{s.t.} & \quad \mathbf{Ax} \leq \mathbf{b} \\ & \quad \mathbf{x} \geq \varepsilon \cdot \mathbf{1}. \end{alignat}$

Die nächste Annäherung an das Problem, das Sie lösen möchten, ist , das etwas zu viele Punkte zulässt. Das Problem ist , dass die Grenze des positiven Orthanten (dh die Menge Teil der Grenze der zulässigen Menge von Make - up konnte . Wir würden möchte diese Punkte ausschließen. Eine Möglichkeit, dies zu tun, besteht darin, das zu tun, was Aron vorgeschlagen hat, nämlich zu setzen $F_{0}$ $B = \{\mathbf{x}: \mathbf{x} \geq 0, \exists{i}: x_{i} = 0\}$ $F_{0}$ $\varepsilon$ auf einen kleinen positiven Wert und verwenden Sie dann einen beliebigen Standard-LP-Algorithmus. Diese Strategie ist gut und wird wahrscheinlich in einer Vielzahl von Situationen funktionieren. Es wird jedoch versagen, wenn epsi ; nicht durchführbar ist. Wir wissen, dass für alle (um die Notation zu missbrauchen und auf eine durchführbare Menge durch das entsprechende Problem Bezug zu nehmen), und es ist möglich, dass der LP-Löser auch dann anzeigt , wenn Sie kleine positive Werte von auswählen dass deine LP nicht machbar ist. $F_{\varepsilon}$ $F_{0} \subset F \subset F_{\varepsilon}$ $\varepsilon > 0$ $\varepsilon$

Für einen LP-Solver würde ich einen beliebigen Algorithmus für interne Punkte für LPs verwenden, der mit einem machbaren Punkt beginnt und machbar bleibt. Dies ist eine weitere Möglichkeit, Punkte in auszuschließen . Sie müssen für diese Algorithmen keinen praktikablen Punkt angeben. Standardlöser erledigen das für Sie. Methoden wie affine Skalierung, Potentialreduktion und Barrieremethoden stellen zusätzliche LPs auf, die praktikable Lösungen finden, und die Iterationen für diese Algorithmen durchlaufen das Innere des praktikablen Bereichs. Sie müssen nur einen Punkt in Ihrer realisierbaren Region lokalisieren. Solange die von den LP-Lösern verwendeten Hilfsprobleme einen realisierbaren Punkt für Ihr Problem lokalisieren und dieser realisierbare Punkt absolut positiv ist, sollten Sie in Ordnung sein. Wenn die Lösung von epsi; für kleine positive Werte von fehlschlägt $B$ $F_{\varepsilon}$ $\varepsilon$ können Sie diese Methoden möglicherweise weiterhin verwenden, um einen streng positiven realisierbaren Punkt innerhalb von zu lokalisieren . $F_{0}$

Verwenden Sie jedoch kein Simplex, da nur die Eckpunkte von , was genau das ist, was Sie vermeiden möchten. $F_{\varepsilon}$

Geoff Oxberry
quelle

4

Machbarkeitsprobleme sind ein etwas kniffligeres Spiel als allgemeine lineare Probleme, die Sie bemerkt haben. Wenn Sie eine Näherungslösung durchführen (mithilfe einer Gleitkommadarstellung des Gleichungs- und Beschränkungssystems), ist es zulässig, zu fordern , wobei ein sehr kleiner Zahlenwert ist, der groß genug ist, um sicherzustellen, dass tatsächlich ist lebt in , ist aber so klein, dass eine Lösung an der Grenze nicht in Betracht gezogen wird. $x_i >= \epsilon$ $\epsilon$ $x_i$ $\Re_+$

Möglicherweise müssen Sie einstellen und Ihre Lösung wird auf „innerhalb eines Faktors von qualifiziert sein “, aber dies für viele Situationen ausreichend ist. $\epsilon$ $\epsilon$

Aron Ahmadia
quelle

2

Die Antwort von aeismail ist sorgfältig zu lesen, siehe lp

$\max( x_1 + x_2)$

st

$x_1 + x_2 \le 1$

$x_1,x_2 \ge 0$

Es hat Lösungen und sowie andere (entartet). Die Allgemeinheit der Frage impliziert, dass auch diese Fälle behandelt werden müssen. $(1,0)$ $(0,1)$

Da Sie Ihre Zielfunktion auswählen können, können Sie versuchen, sie iterativ zu ändern. ZB Beginnen Sie mit allen Koeffizienten für alle Variablen gleich eins, und prüfen Sie, ob Sie eine geeignete Lösung erhalten. Wenn eine Variable Null ist, erhöhen Sie den Koeffizienten und beginnen Sie erneut ...

Ich kann jedoch keinen mathematischen Beweis dafür liefern, dass dies funktioniert (oder ein genau definiertes Verfahren zum Ändern der Zielfunktion). Ich hoffe das hilft :)

Dan
quelle

Wenn Sie jedoch eine große Anzahl von entarteten Lösungen haben, wie würden Sie numerisch damit umgehen? Wird nicht so ziemlich jeder numerische Löser eine Warnung (oder noch schlimmer) über die Lösung dieses Problems ausgeben?

Aeismail

Nein, werden sie nicht; Sie geben nur die erste optimale Lösung zurück. Sie können weiterhin Lösungen generieren, indem Sie Schnittebenen (oder andere Einschränkungen) hinzufügen, die zuvor berechnete optimale Lösungen ausschließen. In diesem Fall können Sie durch Hinzufügen solcher Schnittebenen eine diskrete Approximation der unendlichen Menge optimaler Lösungen zurückgeben.

Geoff Oxberry

Ich würde das als seltsame Programmierentscheidung ansehen; Warum möchten Sie dem Benutzer nicht mitteilen, dass die Zielfunktion in der Nähe der berichteten Lösung etwas Seltsames getan hat? Für einen nichtlinearen Löser könnte es ein Problem geben, herauszufinden, was vor sich geht. Aber sollte das mit einem linearen System nicht einfacher zu sagen sein?

Aeismail

Ich müsste darüber nachdenken, wie man Entartung erkennt, indem man tatsächlich Probleme erstellt. In der Regel möchten Benutzer jedoch eine optimale Lösung. Die wichtigste Information für eine LP ist daher, dass sie zurückgegeben wird, wenn die Lösung optimal, machbar (aber nicht optimal) ist. undurchführbar oder unbegrenzt. (Diese Zustände sind in der Tat das, was ein Löser wie CPLEX zurückgeben würde.) Entartung ist in erster Linie ein theoretisches Problem; Der einzige Grund, warum dies in einem numerischen Kontext diskutiert wird, liegt entweder im Algorithmus-Design oder in der Praxis, um festzustellen, dass die Entartung einen Löser typischerweise verlangsamt.

Geoff Oxberry

Durchführbarkeitsproblem der linearen Programmierung mit strengen Einschränkungen der Positivität

Antworten: