Экспресс булевых логических операций в целочисленном линейном программировании (ILP)

У меня есть целочисленная линейная программа (ILP) с некоторыми переменными , которые предназначены для представления логических значений. В х I «ы ограничены целыми числами и держать либо 0 или 1 ( 0 ≤ х я ≤ 1 ).$x_i$$x_i$$0 \le x_i \le 1$

Я хочу выразить логические операции над этими 0/1-значными переменными, используя линейные ограничения. Как я могу это сделать?

Более конкретно, я хочу установить (логическое И), у 2 = х 1 ∨ х 2 (логическое ИЛИ), и у 3 = ¬ х 1 (логическое НЕ). Я использую очевидную интерпретацию 0/1 как логические значения: 0 = ложь, 1 = истина. Как мне написать ограничения ILP, чтобы гарантировать, что y i связаны с x i по желанию?$y_1 = x_1 \land x_2$$y_2 = x_1 \lor x_2$$y_3 = \neg x_1$$y_i$$x_i$

(Это можно рассматривать как запрос на сокращение от CircuitSAT до ILP или запрос на способ выразить SAT как ILP, но здесь я хочу увидеть явный способ кодирования логических операций, показанных выше.)

Логическое И: Используйте линейные ограничения $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$ ограничено целым числом. Это навязывает желаемые отношения. (Довольно здорово, что вы можете сделать это с помощью линейных неравенств, а?)

Логическое ИЛИ: Используйте линейные ограничения $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$ ограничено целым числом.

Логическое НЕ: используйте $y_3 = 1-x_1$ .

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

$x_1 \Rightarrow x_2$$x_1 \le x_2$$x_1$$x_2$

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

---

И, в качестве бонуса, еще один метод, который часто помогает при формулировании задач, которые содержат смесь нулевых (булевых) переменных и целочисленных переменных:

$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$$|x|$

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

---

Для некоторых отличных практических задач и проработанных примеров я рекомендую формулировать целочисленные линейные программы: A Rogues 'Gallery .

$$y_1\geq x_1+x2−1,\qquad y_1\leq x_1,\qquad y_1\leq x_2\,,$$ $$0 \leq x_1 + x_2-2y_1 \leq 1\,.$$ $$0 \leq 2y_1 - x_1 - x_2 ≤ 1\,.$$

Для НЕ, такое улучшение не доступно.

$y=x_1 \land x_2 \land \dots \land x_n$$n$

$$0 \leq \sum x_i -ny \leq n-1\,.$$ $$0 \leq ny -\sum x_i \leq n-1\,.$$

Я нашел более короткое решение для XOR y = x1⊕x2 (x и y двоичные 0, 1)

только одна строка: x1 + x2 - 2 * z = y (z - любое целое число)