Вопрос по z3, performance, encoding, statistics, real-datatype – Z3 реальная арифметика и статистика

1

Учитывая проблему, которая закодирована с использованием действительных значений Z3, какая из статистическихZ3 /smt2 /st Может быть полезно производить, чтобы определить, есть ли у движка reals «проблемы / много работы»?

В моем случае у меня есть две в основном эквивалентные кодировки задачи, обе с использованием реалов. & Quot; маленький & quot; разница в кодировании, однако, имеет большое значение во время выполнения, а именно, то, что кодирование A занимает 2: 30 минут, а кодирование B - 13 минут. Статистика Z3 показывает, чтоconflicts а такжеquant-instantiations в основном эквивалентны, а другие нет, напримерgrobner, pivots а такжеnonlinear-horner.

Две разные статистические данные доступны каксуть.


EDIT (чтобы обратиться к комментарию Льва):

SMT2-кодирование, генерируемое обеими версиями, составляет ~ 30 тыс. Строк, а утверждения, в которых используются вещественные числа, разбросаны по всему коду. Основное различие заключается в том, что кодирование B использует множество недоопределенных констант реального типа из диапазона0.0 в1.0 которые ограничены неравенствами, например0.0 < r1 < 1.0 или же0.0 < r3 < 0.75 - r1 - r2тогда как при кодировании A многие из этих недостаточно указанных констант были заменены фиксированными действительными значениями из того же диапазона, например,0.1 или же0.75 - 0.01, В обоих кодировках используется нелинейная вещественная арифметика, напримерr1 * (1.0 - r2).

Несколько случайных примеров из двух кодировок доступны в видесуть, Все встречающиеся переменные являются заниженными действительными значениями, как описано выше.


PS: вводит псевдонимы для фиксированных реальных значений, например,

(define-sort $Perms () Real)
(declare-const $Perms.$Full $Perms)
(declare-const $Perms.$None $Perms)
(assert (= $Perms.Zero 0.0))
(assert (= $Perms.Write 1.0))

нанести значительный ущерб производительности?

Можно ли опубликовать кодировку A и B? Leonardo de Moura
@Leo: см. Отредактированный вопрос Malte Schwerhoff

Ваш Ответ

1   ответ
4

которые содержат только арифметику. Поскольку в вашей задаче используются квантификаторы, новый нелинейный решатель использоваться не будет. Таким образом, Z3 будет использовать старый подход, основанный на комбинации: Simplex (статистика пивотов), Groebner Basis (статистика Гребнера) и Interval Propagation (статистика хорнеров). Это не полный метод. Более того, исходя из фрагментов, которые вы разместили в гисте, база Гребнера не будет очень эффективной. Этот метод обычно эффективен для задач, которые содержат много равенств. Так что, вероятно, это просто накладные расходы. Вы можете отключить его, используя опциюNL_ARITH_GB=false. Of course, this is just a guess based on the problem fragment you posted.

Различия между кодированиемA а такжеB являются существенными. кодированиеA является по существу линейной проблемой, поскольку несколько констант были зафиксированы для реальных значений. Z3 всегда был полон для линейных арифметических задач. Итак, это должно объяснить разницу в производительности.

Что касается вашего вопроса об псевдонимах, предпочтительный способ ввести псевдонимы:

(define-const $Perms.$Zero $Perms 0.0)
(define-const $Perms.$Write $Perms 1.0)

Z3 также содержит препроцессор, который устраняет переменные, используя линейные уравнения. Этот препроцессор по умолчанию отключен в задачах, которые содержат квантификаторы. Это дизайнерское решение мотивируется инструментами проверки программ, которые широко используют триггеры / шаблоны в квантификаторах. Процесс исключения переменных может изменить тщательно спроектированные триггеры / шаблоны и повлиять на общее время выполнения. Вы можете использовать новую структуру тактики / стратегии в Z3, чтобы заставить его применять этот препроцессор. Вы можете заменить команду

(check-sat)

с

(check-sat-using (then simplify solve-eqs smt))

Эта стратегия говорит Z3 выполнить упрощатель, затем решить уравнения (и исключить переменные) и затем запустить механизм расчета по умолчаниюsmt. You can find more about tactics and strategies in the following руководство.

Это было какое-то время, но я наконец-то нашел время для экспериментов сsmt.arith.nl.gbи его отключение, по-видимому, имеет положительный эффект в нашей проблемной области. Время выполнения всего нашего набора тестов увеличилось на 7% - не идеально, но мы надеемся улучшить это, используя тактику (как вы и предлагали). Malte Schwerhoff
Большое спасибо, Лео! Я попробую ваши предложения и сообщу в случае, если производительность заметно изменится. Malte Schwerhoff

Похожие вопросы