Rzut na boolean, dla programowania liniowego liczb całkowitych

Chcę wyrazić następujące ograniczenie w całkowitym programie liniowym:

y = {\begin{cases} 0 & if x = 0 \\ 1 & if x \neq 0. \end{cases}

$y = \begin{cases} 0 &\text{if } x=0\\ 1 &\text{if } x\ne 0. \end{cases}$

Mam już zmienne całkowite i obiecuję, że . Jak mogę wyrazić powyższe ograniczenie w formie odpowiedniej do użycia z całkowitym programem do programowania liniowego? $x,y$ $-100 \le x \le 100$

Będzie to prawdopodobnie wymagało wprowadzenia dodatkowych zmiennych. Jakie nowe zmienne i ograniczenia muszę dodać? Czy można to zrobić czysto za pomocą jednej nowej zmiennej? Dwa?

Równolegle jest to pytanie, jak wymusić ograniczenie

y \neq 0 if and only if x \neq 0.

$y \ne 0 \text{ if and only if } x \ne 0.$

w kontekście, w którym mam już ograniczenia sugerujące i . $|x| \le 100$ $0 \le y \le 1$

(Moim celem jest naprawienie błędu w https://cs.stackexchange.com/a/12118/755 .)

linear-programming integer-programming

— DW
źródło

Czego próbowałeś? Czy próbowałeś przeanalizować kilka przykładów, aby zobaczyć, czy widzisz wzór? Jeśli tak, czy próbowałeś zgadywać, a następnie próbowałeś to udowodnić?

— Brika,

Heh! Widzę, co tam zrobiłeś , @Brika. Jeśli jesteś ciekawy, co próbowałem, zobacz tutaj, a także wyjaśnienie, dlaczego tak naprawdę było źle . Jeśli chcesz zobaczyć moją kolejną próbę, zobacz moją odpowiedź . Dziękuję za przeczytanie moich starych pytań i jeśli można je poprawić w przyszłości, chętnie usłyszę wszelkie sugestie!

— DW

To jest bardzo dobre. ;)

— Brika,

Odpowiedzi:

Myślę, że mogę to zrobić za pomocą jednej dodatkowej zmiennej binarnej : $\delta \in \{0,1\}$

- 100 y \leq x \leq 100 y

$-100y \le x \le 100 y$

0.001 y - 100.001 δ \leq x \leq - 0.001 y + 100.001 (1 - δ)

$0.001y-100.001\delta \le x \le -0.001y+100.001 (1-\delta)$

Aktualizacja

Zakłada się, że jest zmienną ciągłą . Jeśli ograniczymy do wartości całkowitej , wówczas drugie ograniczenie można uprościć do: $x$ $x$

y - 101 δ \leq x \leq - y + 101 (1 - δ)

$y-101\delta \le x \le -y+101 (1-\delta)$

— Erwin Kalvelagen
źródło

Sprawdziłem to poprawnie, testując go wyczerpująco za pomocą małego programu. Dziękuję za rozwiązanie!

— DW

@ErwinKalvelagen, czy mógłbyś wyjaśnić swoją logikę za pomocą zmiennej binarnej delta, dla bardziej ogólnego przypadku, na przykład, jeśli y = {a: x> 0, b: x <0}.

— Nick

@Nick Zmienna binarna służy do modelowania konstrukcji „OR”. Zobacz tutaj na odpowiedź na swoje pytanie.

— Erwin Kalvelagen,

@ErwinKalvelagen, świetna odpowiedź, próbowałem zastosować twoje podejście do mojego pytania tutaj cs.stackexchange.com/questions/64794/… .

— Nick

x

$x$

x

$x$

$0 \leq x \leq N$ $N=100$

$0 \leq z_1, z_2, z \leq 1$
$x - N(1-z_1) \leq 0$
$-x -Nz_1 \leq -1$
$-x -N(1-z_2) \leq 0$
$x -Nz_2 \leq -1$
$z_1 + z_2 - 1 \leq z$
$z \leq z_1$
$z \leq z_2$

$z_1 = 1 \iff x \leq 0$ $z_2 = 1 \iff x \geq 0$ $z = z_1 \land z_2$

— Pramod
źródło

z = 1 - y

$z=1-y$

x = 100

$x=100$

y = 1

$y=1$

z = 0

$z=0$

z_{1}, z_{2}

$z_1,z_2$

x - N z_{2} \leq - 1

$x-Nz_2 \le -1$

x < N

$x<N$

x \leq 99

$x \le 99$

x = 99

$x=99$

y = 1

$y=1$

y = 0

$y=0$

x

$x$

- N \leq x \leq N

$-N \le x \le N$

0 \leq x \leq N

$0 \le x \le N$

$t,u$ $t=1$ $x \ge 0$ $u=1$ $x \le 0$ $y=\neg(t \land u)$

\begin{aligned} 0 & \leq t, u, y \leq 1 \\ 1 + x & \leq 101 t \leq 101 + x \\ 1 - x & \leq 101 u \leq 101 - x \\ t + u - 1 & \leq 1 - y \\ 1 - y & \leq t \\ 1 - y & \leq u \end{aligned}

$\begin{align*} 0 &\le t,u,y \le 1\\ 1+x &\le 101t \le 101 + x\\ 1-x &\le 101u \le 101-x\\ t+u-1 &\le 1-y\\ 1-y &\le t\\ 1-y &\le u \end{align*}$

— DW
źródło

x \leq 99

$x \leq 99$

x \leq 100

$x \leq 100$

x \geq - 99

$x \geq -99$

@TLW, dziękuję za złapanie tego! Zredagowałem swoją odpowiedź, aby naprawić błąd. Przetestowałem to wyczerpująco za pomocą małego programu i myślę, że teraz powinno być poprawne.

— DW