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

58

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 ( ).xixi0xi1

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 ?y1=x1x2y2=x1x2y3=¬x1yixi

(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.)

DW
źródło

Odpowiedzi:

66

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?)y1x1+x21y1x1y1x20y11y1

Logiczne OR: Użyj ograniczeń liniowych , , , , gdzie jest ograniczone liczbą całkowitą.y2x1+x2y2x1y2x20y21y2

Logiczne NOT: Użyj .y3=1x1

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ą.y4=(x1x2)y4=¬x1x2y41x1+x2y41x1y4x20y41y4

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).x1x2x1x2x1x2

XOR: Aby wyrazić (wyłączne lub z i ), użyj nierówności liniowych , , , , , gdzie jest ograniczone do liczby całkowitej.y5=x1x2x1x2y5x1+x2y5x1x2y5x2x1y52x1x20y51y5


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 tutajxyy=1x0y=0x=00xU0y1yxxUyx|x|UUxUU. 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ślixx0t0y1yxt=xytnx1,,xnyi=1xi1 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).yi=0xi=0nt1,,tn0yi1yixiti=xiyit1++tn


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

DW
źródło
który solver programowania liniowego może to rozwiązać? ponieważ w formacie * .lp lub * .mps jedna strona ograniczenia musi być stałą liczbą całkowitą, a nie zmienną.
boxi
4
@boxi, nie wiem nic o formacie * .lp lub * .mps, ale każdy solver programowania liniowego powinien być w stanie to rozwiązać. Zauważ, że jeśli masz coś takiego jak , jest to równoważne , który może być w żądanym formacie. xyyx0
DW
-i sprawdził to ponownie. lp_solve może to rozwiązać, ale na przykład qsopt nie. nie wiem dlaczego. ale dzięki <3
boxi
@boxi, właśnie sprawdziłem graficzny interfejs użytkownika apletu QSopt i może on obsłużyć tego rodzaju ograniczenia po zmianie na , więc nie jestem pewien, co się dzieje. (Użyłem formatu * .lp.) Byłbym zaskoczony, gdyby jakikolwiek solver ILP nie był w stanie obsłużyć tych systemów. Jeśli masz dodatkowe pytania dotyczące QSopt, prawdopodobnie powinieneś je zabrać na fora wsparcia QSopt. xyxy0
DW
1
@Pramod, dobry połów! Dziękujemy za wykrycie tego błędu. Masz całkowitą rację. Zadałem nowe pytanie, w jaki sposób modelować tę skrzynkę, i zaktualizuję tę odpowiedź, gdy otrzymamy odpowiedź na to.
DW
19

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:

y1x1+x21,y1x1,y1x2,
0x1+x22y11.
02y1x1x21.

NIE, nie ma takiej poprawy.

Ogólnie dla ( -way AND) ograniczenie będzie wynosić: Podobnie dla OR: y=x1x2xnn

0xinyn1.
0nyxin1.
Abdelmonem Mahmoud Amer
źródło
Bardzo podobne podejście znajduje się w tym dokumencie: ncbi.nlm.nih.gov/pmc/articles/PMC1865583
Abdelmonem Mahmoud Amer
3

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ą)

Bysmyyr
źródło
Aby wyrazić równość w ILP, potrzebujesz dwóch nierówności. Ponadto, aby uniknąć rozwiązania , potrzebujesz jeszcze dwóch nierówności, . Ta odpowiedź ma cztery nierówności i dodatkową zmienną w porównaniu do sześciu nierówności w odpowiedzi DW. x1=1,x2=0,z=200,y=1990y1
JiK
Aby wyrazić równość w ILP wystarczy tylko jedno równanie, dotyczy to zarówno teorii LP, jak i oprogramowania takiego jak Gurobi lub CPLEX. @jk, myślę, że masz na myśli, że „wyrażanie” a ”wymaga dwóch nierówności.”b
whitegreen 18.01.18