Ekspresowe operacje logiczne typu boolowskiego w programowaniu liniowym całkowitym zero-jeden (ILP)

Mam całkowity program liniowy (ILP) z niektórymi zmiennymi które mają reprezentować wartości boolowskie. Wartości muszą być liczbami całkowitymi i zawierać 0 lub 1 ( ).$x_i$$x_i$$0 \le x_i \le 1$

Chcę wyrazić operacje boolowskie na tych zmiennych o wartości 0/1, używając ograniczeń liniowych. Jak mogę to zrobić?

Mówiąc dokładniej, chcę ustawić (boolean AND), (boolean OR), a (boolean NOT). Używam oczywistej interpretacji 0/1 jako wartości boolowskich: 0 = fałsz, 1 = prawda. Jak napisać ograniczenia ILP, aby upewnić się, że są odpowiednio powiązane z ?$y_1 = x_1 \land x_2$$y_2 = x_1 \lor x_2$$y_3 = \neg x_1$$y_i$$x_i$

(Może to być postrzegane jako prośba o redukcję z CircuitSAT do ILP lub prośba o sposób wyrażenia SAT jako ILP, ale tutaj chcę zobaczyć wyraźny sposób kodowania operacji logicznych pokazanych powyżej.)

Logiczne AND: Użyj więzów liniowych , , , , gdzie jest ograniczone liczbą całkowitą. Wymusza to pożądany związek. (Całkiem fajne, że można to zrobić przy pomocy liniowych nierówności, co?)$y_1 \ge x_1 + x_2 - 1$$y_1 \le x_1$$y_1 \le x_2$$0 \le y_1 \le 1$$y_1$

Logiczne OR: Użyj ograniczeń liniowych , , , , gdzie jest ograniczone liczbą całkowitą.$y_2 \le x_1 + x_2$$y_2 \ge x_1$$y_2 \ge x_2$$0 \le y_2 \le 1$$y_2$

Logiczne NOT: Użyj .$y_3 = 1-x_1$

Implikacja logiczna: Aby wyrazić (tj. ), możemy dostosować konstrukcję do logicznego OR. W szczególności użyj wiązań liniowych , , , , gdzie jest ograniczone liczbą całkowitą.$y_4 = (x_1 \Rightarrow x_2)$$y_4 = \neg x_1 \lor x_2$$y_4 \le 1-x_1 + x_2$$y_4 \ge 1-x_1$$y_4 \ge x_2$$0 \le y_4 \le 1$$y_4$

Wymuszona implikacja logiczna: Aby wyrazić, że musi zostać utrzymany, po prostu użyj ograniczenia liniowego (zakładając, że i są już ograniczone do wartości boolowskich).$x_1 \Rightarrow x_2$$x_1 \le x_2$$x_1$$x_2$

XOR: Aby wyrazić (wyłączne lub z i ), użyj nierówności liniowych , , , , , gdzie jest ograniczone do liczby całkowitej.$y_5 = x_1 \oplus x_2$$x_1$$x_2$$y_5 \le x_1 + x_2$$y_5 \ge x_1-x_2$$y_5 \ge x_2-x_1$$y_5 \le 2-x_1-x_2$$0 \le y_5 \le 1$$y_5$

Jako bonus, jeszcze jedna technika, która często pomaga przy formułowaniu problemów, które zawierają mieszankę zmiennych zerowych (boolowskich) i zmiennych całkowitych:

Rzut na boolean (wersja 1): Załóżmy, że masz zmienną całkowitą i chcesz zdefiniować , aby jeśli i jeśli . Jeśli dodatkowo wiesz, że , możesz użyć nierówności liniowych , , ; Działa to jednak tylko wtedy, gdy znasz górną i dolną granicę . Lub, jeśli wiesz, że (czyli ) dla jakiegoś stałego , wtedy możesz użyć metody opisanej tutaj$x$$y$$y=1$$x \ne 0$$y=0$$x=0$$0 \le x \le U$$0 \le y \le 1$$y \le x$$x \le Uy$$x$$|x| \le U$$-U \le x \le U$$U$. Ma to zastosowanie tylko, jeśli znasz górną granicę.$|x|$

Rzuć na boolean (wersja 2): Rozważmy ten sam cel, ale teraz nie znamy górnej granicy . Załóżmy jednak, że wiemy, że . Oto, w jaki sposób możesz wyrazić to ograniczenie w systemie liniowym. Najpierw wprowadź nową zmienną całkowitą . Dodaj nierówności , , . Następnie wybierz funkcję celu, aby zminimalizować . Działa to tylko wtedy, gdy nie masz jeszcze funkcji celu. Jeśli masz nieujemnych zmiennych całkowitych i chcesz rzutować wszystkie z nich na booleany, tak aby jeśli$x$$x \ge 0$$t$$0 \le y \le 1$$y \le x$$t=x-y$$t$$n$$x_1,\dots,x_n$$y_i=1$$x_i\ge 1$ i jeśli , to możesz wprowadzić zmiennych z nierównościami , , i zdefiniować funkcję celu aby zminimalizować . Ponownie, to działa tylko nic innego, nie trzeba definiować funkcji celu (jeśli oprócz rzutów na wartość logiczną planujesz po prostu sprawdzić wykonalność wynikowej ILP, nie próbuj minimalizować / maksymalizować niektórych funkcji zmiennych).$y_i=0$$x_i=0$$n$$t_1,\dots,t_n$$0 \le y_i \le 1$$y_i \le x_i$$t_i=x_i-y_i$$t_1+\dots + t_n$

W przypadku problemów z doskonałą praktyką i sprawdzonych przykładów polecam Formułowanie całkowitych programów liniowych: Galeria Rogue'a .

Logiczną relację AND można modelować w jednym ograniczeniu zakresu zamiast w trzech ograniczeniach (jak w drugim rozwiązaniu). Więc zamiast trzech ograniczeń można go zapisać za pomocą ograniczenia pojedynczego zakresu Podobnie w przypadku logicznego OR:

NIE, nie ma takiej poprawy.

Ogólnie dla ( -way AND) ograniczenie będzie wynosić: Podobnie dla OR: $y=x_1 \land x_2 \land \dots \land x_n$$n$

Znalazłem krótsze rozwiązanie dla XOR y = x1⊕x2 (xiy są binarne 0, 1)

tylko jedna linia: x1 + x2 - 2 * z = y (z jest dowolną liczbą całkowitą)