Problem wykonalności programowania liniowego ze ścisłymi ograniczeniami dodatnimi

15

Istnieje system więzów liniowych . Chciałbym znaleźć ściśle dodatni wektor który spełnia te ograniczenia. Oznacza to, że jest wymagane dla każdego składnika z . Jak mogę użyć solwera LP, aby znaleźć tak ściśle dodatni wektor (lub potwierdzić, że nie istnieje )? Nie mogę po prostu wprowadzić innego systemu ograniczeń ${\bf Ax} \leq {\bf b}$ ${\bf x} > 0$ $x_i > 0$ $x_i$ ${\bf x}$ ${\bf x}$ ${\bf x}$ $x_i > 0$ , ponieważ równość musi być zawsze dozwolona w LP - ale mogę używać solvera LP kilka razy, ze zmieniającymi się funkcjami celu. Myślę, że powinienem użyć metody zmiennej luzu, ale nie wiem jak.

optimization linear-programming sara
źródło

15

Możesz obejść problem wyboru małej $\epsilon>0$ , będąc nieco bardziej ambitnym: spróbuj znaleźć $\mathbf{x}$ tak, że $\mathbf{Ax}\leq \mathbf{b}$ i że najmniejszy wpis w $\mathbf{x}$ jest największy z możliwych.

W tym celu wprowadź nową zmienną

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

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

x

$\mathbf{x}$ było w

R^{n}

$\mathbb{R}^n$ ) i rozwiąż następujący problem za pomocą solwera LP

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}.$

Jest to przeformułowanie następującego problemu:

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}.$

Sztylet
źródło

dobrze zrobione, jest to odpowiednik sztuczki, którą współautorem użyłem właśnie w niedawnym artykule i zdecydowanie przewyższa podejście, które zasugerowałem.

Aron Ahmadia

Zgoda. Dobra gra, proszę pana.

Geoff Oxberry

Przeformułowany problem może mieć nieograniczony cel w przypadkach, w których odpowiedź na pierwotny problem jest trywialna. Na przykład, jeśli system ograniczeń jest tylko

. Jest to w porządku, o ile sprawdzasz, czy jest to wykonalne, optymalne lub nieograniczone w statusie zwracanym twojego solvera lp, lub wyraźnie przypisujesz

.

x \geq - 1

$x \ge -1$

ϵ

$\epsilon$

David Nehme

@DavidNehme: Można dodać ograniczenie

aby uzyskać ograniczony cel.

y_{n + 1} \leq 1

$y_{n+1}\le 1$

Arnold Neumaier

5

W przypadku problemu z wykonalnością LP nie użyłbym standardowego simpleksu. Standardowe pierwotne (lub podwójne) algorytmy simpleksowe odwiedzą tylko wierzchołki możliwego zestawu pierwotnych (lub podwójnych) problemów.

Niech wykonalnym zestawem problemu, który faktycznie chcesz rozwiązać, będzie , i załóżmy, że zamiast tego rozwiązałeś problem ( ): $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}$

Najbliższym przybliżeniem problemu, który chcesz rozwiązać, jest , który przyznaje nieco za dużo punktów. Problem polega na tym, że granica dodatniej ortant (tj. Zbiór może stanowić część granicy możliwego zestawu . jak wykluczyć te punkty. Jednym ze sposobów jest zrobienie tego, co sugerował Aron, czyli ustawienie $F_{0}$ $B = \{\mathbf{x}: \mathbf{x} \geq 0, \exists{i}: x_{i} = 0\}$ $F_{0}$ $\varepsilon$ do niewielkiej dodatniej wartości, a następnie użyj dowolnego standardowego algorytmu LP. Ta strategia jest dobra i prawdopodobnie będzie działać w wielu różnych sytuacjach. Jednak zawiedzie, jeśli jest nieosiągalny. Wiemy, że dla wszystkich (do nadużywania notacji i odwoływania się do możliwego zestawu przez odpowiadający jej problem), i możliwe jest, że nawet jeśli wybierzesz małe dodatnie wartości , solver LP wskaże że twoje LP jest niemożliwe. $F_{\varepsilon}$ $F_{0} \subset F \subset F_{\varepsilon}$ $\varepsilon > 0$ $\varepsilon$

Dla solver LP, chciałbym użyć dowolnego algorytmu punkt wewnętrzny do płyt, które rozpoczyna się możliwym momencie i pozostaje wykonalne, co jest kolejnym sposobem, aby wykluczyć punkty . Nie musisz przedstawiać wykonalnego algorytmu; standardowe solwery zrobią to za Ciebie. Metody takie jak skalowanie afiniczne, redukcja potencjału i metody barierowe tworzą pomocnicze LP, które znajdą możliwe rozwiązania, a iteracje tych algorytmów przemierzają wnętrze wykonalnego regionu. Musisz tylko zlokalizować jeden punkt w twoim możliwym regionie, więc dopóki problemy pomocnicze używane przez solwery LP zlokalizują wykonalny punkt dla twojego problemu, a ten wykonalny punkt jest ściśle pozytywny, powinieneś być w porządku. Jeśli rozwiązanie nie powiedzie się dla małych dodatnich wartości $B$ $F_{\varepsilon}$ $\varepsilon$ , nadal możesz być w stanie użyć tych metod do zlokalizowania ściśle pozytywnego możliwego punktu w obrębie . $F_{0}$

Nie używaj simpleksu, ponieważ będzie on badał tylko wierzchołki , co jest dokładnie tym, czego chcesz uniknąć. $F_{\varepsilon}$

Geoff Oxberry
źródło

4

Problemy wykonalności są nieco trudniejszą grą niż ogólne problemy liniowe, które zauważyłeś. Jeśli rozwiązujesz w przybliżeniu (używając reprezentacji zmiennoprzecinkowej układu równań i ograniczeń), uzasadnione jest wymaganie , gdzie jest bardzo małą wartością liczbową, wystarczająco dużą, aby zapewnić, że faktycznie mieszka w , ale na tyle mały, że rozwiązanie na granicy nie jest brane pod uwagę. $x_i >= \epsilon$ $\epsilon$ $x_i$ $\Re_+$

Być może będziesz musiał dostosować , a twoje rozwiązanie zostanie zakwalifikowane do „w granicach ”, ale jest to wystarczające w wielu sytuacjach. $\epsilon$ $\epsilon$

Aron Ahmadia
źródło

2

Odpowiedź udzielona przez eeismail należy przeczytać uważnie, patrz pp

$\max( x_1 + x_2)$

św

$x_1 + x_2 \le 1$

$x_1,x_2 \ge 0$

Ma rozwiązania i a także inne (zdegenerowane). Ogólny charakter tego pytania sugeruje, że te przypadki również muszą być traktowane. $(1,0)$ $(0,1)$

Ponieważ możesz wybrać funkcję celu, możesz spróbować iteracyjnie ją zmodyfikować. Np. Zacznij od wszystkich współczynników dla wszystkich zmiennych równych jedności, sprawdź, czy uzyskasz odpowiednie rozwiązanie. Jeśli jedna zmienna ma wartość zero, zwiększ jej współczynnik i zacznij od nowa ...

Chociaż nie mogę dać matematycznego dowodu, że to działa (lub dobrze zdefiniowana procedura modyfikowania funkcji celu). Mam nadzieję, że to pomoże :)

Dan
źródło

Jeśli jednak masz dużą liczbę zdegenerowanych rozwiązań, jak poradziłbyś sobie z tym liczbowo? Czy prawie żaden numeryczny solver nie wyśle ostrzeżenia (lub gorzej) o rozwiązaniu tego problemu?

aeismail

Nie zrobią tego; zwrócą tylko pierwsze napotkane optymalne rozwiązanie. Generowanie rozwiązań polega na dodawaniu płaszczyzn cięcia (lub innych ograniczeń), które wykluczają wcześniej obliczone optymalne rozwiązania. W takim przypadku dodanie takich płaszczyzn cięcia umożliwi zwrócenie dyskretnego przybliżenia nieskończonego zestawu optymalnych rozwiązań.

Geoff Oxberry

Uważałbym to za dziwną decyzję programową; dlaczego nie chcesz powiedzieć użytkownikowi, że funkcja celu działała dziwnie w sąsiedztwie zgłaszanego rozwiązania? W przypadku rozwiązania nieliniowego widziałem problem z ustaleniem, co się dzieje; ale czy nie powinno to być łatwiejsze do odróżnienia w przypadku systemu liniowego?

aeismail

Musiałbym pomyśleć o tym, jak można wykryć zwyrodnienie, faktycznie konstruując problemy, ale zazwyczaj użytkownicy chcą optymalnego rozwiązania, więc najważniejszą informacją dla LP jest zwrot, jeśli rozwiązanie jest optymalne, wykonalne (ale nie optymalne), niemożliwy lub nieograniczony. (Te statusy są w rzeczywistości tym, co powróciłby solver taki jak CPLEX.) Degeneracja jest przede wszystkim zagadnieniem teoretycznym; jedynym powodem, dla którego zostanie to omówione w kontekście liczbowym, jest albo projektowanie algorytmu, albo w praktyce, aby zauważyć, że degeneracja zwykle spowalnia solver.

Geoff Oxberry

Problem wykonalności programowania liniowego ze ścisłymi ograniczeniami dodatnimi

Odpowiedzi: