Подсчет количества удовлетворенных моделей с учетом математических ограничений

Question

Вопрос

Существует множество алгоритмов для решения этой задачи. #СБ проблема, одним из которых является алгоритм DPLL и реализован для всех видов языков программирования.Насколько я видел, все они принимают логическую формулу в CNF в качестве входных данных и выводят количество удовлетворенных интерпретаций.

Математические ограничения, с другой стороны, является другим способом определения экземпляра SAT-задачи и часто используется в дискретной оптимизации, где кто-то пытается оптимизировать некоторую функцию с учетом этих ограничений. Существует ли программа, принимающая математические ограничения в качестве входных данных и выводящая количество удовлетворенных интерпретаций?

Пример

Мы представляем логическую формулу $Q = (a или b) \клин (c или d)$ такие ограничения, как $$a + b \ geq 1 \\ c + d \ geq 1$$ или как матрица $A$ и опорный вектор $b$ $$ A= \begin{bmatrix} 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \конец {bmatrix} \\ b = \начало {bmatrix} 1 & 1 \конец {bmatrix} $$

где все переменные $a,b,c,d \in \{0,1\}$.Мы знаем, что существуют программы, принимающие $Q$ в качестве входных данных и выходных данных указывается количество интерпретаций, но существуют ли программы, принимающие $A$ и $b$ в качестве входных данных (или аналогичной конструкции) и выводит одинаковое количество интерпретаций?

Answer 1

Я знаю два разумных подхода.

Подход №1: Подсчитайте количество целых точек внутри выпуклого многогранника.

Приведенный вами набор линейных неравенств вместе с неравенствами $0 \le a,b,c,d \le 1$, определяет выпуклый многогранник.Теперь вы хотите подсчитайте количество целых точек, попадающих в этот многогранник.

Для этого существуют стандартные алгоритмы, которые вы могли бы применить непосредственно.Если вы выполните поиск по "подсчету целых точек в многограннике" или "подсчету точек решетки в многограннике", вы найдете множество исследовательских работ.Смотрите, например, https://cstheory.stackexchange.com/q/22280/5038, Нахождение всех решений задачи целочисленного линейного программирования (ILP).

Подход №2: Преобразуйте в CNF, затем используйте решатель #SAT.

Вы всегда можете преобразовать свои ограничения в формулу CNF.Каждое линейное неравенство может быть преобразовано в набор предложений CNF.Линейное неравенство вида $x_i + \ точки + x_j \ge 1$ непосредственно соответствует пункту CNF $(x_i или точки или x_j)$.Для более общего линейного неравенства вида $x_i + \ точки + x_j \ge c$, вы хотите выразить ограничение , которое по крайней мере $c$ из $k$ переменные $x_i,\точки,x_j$ являются правдой.Существует множество стандартных способов кодирования этого.Видишь https://cstheory.stackexchange.com/q/23771/5038, Сведите следующую проблему к SAT, Ограничение кодирования 1-out-of-n для решателей SAT,

(Один из подходов заключается в преобразовании логической схемы, которая вычисляет $x_i + \ точки + x_j$ и сравнивает это с $c$, затем преобразуйте логическую схему в CNF , используя Преобразование Цейтина.Вы можете создать такую логическую схему, используя стандартные схемы сумматора и компаратора.Однако есть много и других способов.)

Как только у вас есть формула CNF, эквивалентная набору ограничений, вы можете использовать любой готовый решатель #SAT для подсчета количества решений этой формулы CNF.

---

Трудно сказать, какой из этих двух подходов будет работать лучше;возможно, вам придется попробовать их оба в тех случаях, с которыми вы имеете дело, чтобы знать наверняка.Я бы ожидал, что если у вас есть линейные неравенства вида $x_i + \ точки + x_j \ge c$ где $c$ является большим, тогда Подход № 1 может быть более эффективным;но если $c$ как правило, невелик, тогда подход № 2 может быть более эффективным.

Answer 2

Вы можете реализовать DPLL, используя напрямую, используя ограничения вместо пунктов.Это требует модификации структуры данных и алгоритма распространения, но он работает все равно.

Как только все переменные ограничения установлены, кроме одного, могут возникнуть распространение устройства.

Как только все переменные ограничения установлены, могут возникнуть конфликт.

Остальная часть алгоритма остается прежней.

Ограничение над булевыми переменными - это просто коллекция скрытых пунктов CNF (потенциально экспоненциально много пунктов, в зависимости от ограничений).

Answer 3

Вопрос был Отвечено On.stackexchange для программного обеспечения смешанного целочисленного программного обеспечения с примерами существующего программного обеспечения и скриптов (CPLEX, SCIP, ...).

Это более похоже на алгоритм CDCL, чем DPLL: когда найден новый раствор, добавляется новое ограничение, чтобы запретить им, а поиск возобновляет, пока проблема не станет невозможной.