Z3 минимизация и тайм-аут

Question

Я пытаюсь использовать решатель z3 для минимизации проблемы. Я пытался получить тайм-аут и вернуть лучшее решение до сих пор. Я использую Python API, и параметр времени ожидания "smt.timeout" с

set_option("smt.timeout", 1000) # 1s timeout

Это на самом деле истекает примерно через 1 секунду. Однако большее время ожидания не обеспечивает меньшую цель. Я закончил тем, что включил многословие с

set_option("verbose", 2)

И я думаю, что z3 последовательно оценивает большие значения моей цели, пока проблема не будет решена:

(opt.maxres [0:6117664])
(opt.maxres [175560:6117664])
(opt.maxres [236460:6117664])
(opt.maxres [297360:6117664])
...
(opt.maxres [940415:6117664])
(opt.maxres [945805:6117664])
...

Таким образом, у меня есть два вопроса:

• Могу ли я, наоборот, сказать z3 начинать с верхней границы и последовательно возвращать модели с меньшим значением для моей целевой функции (как, например, аннотации Minizinc) indomain_max http://www.minizinc.org/2.0/doc-lib/doc-annotations-search.html)
• Похоже, что решатель возвращает удовлетворительный экземпляр моей проблемы. Как это найти? Если он пытается последовательно оценить большие значения моей цели, он не должен был найти удовлетворительный экземпляр, когда истекает время ожидания...

edit: в журнале opt.maxres верхняя граница никогда не сжимается.

Для записи я нашел более подробное описание опций в источнике здесь opt_params.pyg

Изменить Извините, что беспокою, я недавно еще раз окунулся в это. Во всяком случае, я думаю, что это может быть полезно для других. Я обнаружил, что я на самом деле должен позвонить Optimize.upper метод, чтобы получить верхнюю границу, и модель все еще не та, которая соответствует этой верхней границе. Я смог добавить его в качестве нового ограничения и вызвать решатель (без оптимизации, просто SAT), но это, вероятно, не лучшая идея. Читая это, я чувствую, что должен позвонить Optimize.update_upper после истечения времени ожидания решателя, но у интерфейса python такого метода нет (?). По крайней мере, теперь я могу получить верхнюю границу и соответствующую модель (ценой ненужных вычислений, я думаю).

Answer 1

Z3 находит решения для жестких ограничений и записывает текущие значения для целей и мягких ограничений. Последняя найденная модель (последняя модель с лучшим на данный момент значением для целей) возвращается, если вы запрашиваете модель. Стратегия maxres главным образом улучшает нижние границы мягких ограничений (например, любое решение должно иметь стоимость не менее хх) и, когда это возможно, улучшает верхнюю границу (дополнительное решение имеет стоимость не более yy). Нижние границы не говорят вам слишком много, кроме как сужают диапазон возможных оптимальных значений. Верхние границы доступны по истечении времени ожидания. Вы можете попробовать одну из других стратегий, например, такую ​​как wmax, которая выполняет ветвление и обрезку. Обычно maxres работает значительно лучше, но у вас может быть лучший опыт (в зависимости от проблем) с wmax для улучшения верхних границ.

У меня нет режима, где вы получаете поток моделей. В принципе это возможно, но это потребует некоторой (нетривиальной) реорганизации. Для фронтов Парето вы делаете последовательные вызовы Optimize.check(), чтобы получить последовательные фронты.