В чем точное значение NumConflicts в CP-Sat?

Интересно, что конкретно означает информация solver.Response.NumConflicts. В документации (ах) я нашел такие утверждения, как

Возвращает количество конфликтов с момента создания решателя. (https://developers.google.com/optimization/reference/python/sat/python/cp_model#numconflicts)

Это не совсем удовлетворяет мои вопросы. Говорит ли это что-нибудь о том, сколько раз было повреждено ограничение? Или это какой-то показатель точности решения? Хотя для оптимальных решений это не ноль.

И связанный вопрос: что может быть наиболее убедительной информацией о качестве решения?

Спасибо


optimization or-tools constraint-programming sat
person The Random Forum Guy    schedule 21.02.2020    source источник

Ответы (1)


arrow_upward
2
arrow_downward

См .: https://github.com/google/or-tools/issues/1398#issuecomment-508396143

Число конфликтов возвращает количество конфликтов, сгенерированных во время поиска. Грубо говоря, конфликт - это тупик в дереве поиска.

person Stradivari    schedule 21.02.2020
comment
Ура, дружище! Однако мне удалось не найти этот пост ... И есть ли у вас представление о моем связанном вопросе (не знаю, является ли это плохой практикой, чтобы соединять вопросы таким образом !?) - person The Random Forum Guy; 21.02.2020
comment
Лучшая информация, которую вы получите, - это разрыв между значением решения и наилучшей целевой границей (также известной как нижняя граница целевого значения при минимизации). Вы имеете в виду что-то другое? - person Laurent Perron; 21.02.2020
comment
Да я вижу. Для меня это имеет смысл, спасибо. Я все еще думаю о том, какую информацию об исследуемой системе вы можете получить по значению NumConflicts. Представьте, что у вас есть электрическая система с поставщиками и потребителями, а также хранилища энергии. Если бы задача состояла в том, чтобы использовать всю периодически производимую энергию (например, ветряными турбинами или аналогичными) и удовлетворять постоянные потребности потребителей. Могут ли NumConflicts рассказать что-нибудь о качестве размеров элементов системы? (Например, нулевые конфликты, потому что предоставленные уровни мощности хорошо совпадают, что приводит к отсутствию мертвых ветвей) - person The Random Forum Guy; 21.02.2020
comment
Нет, это просто говорит о том, как сложно было найти решение. Он говорит о качестве модели, а не о качестве решения. - person Laurent Perron; 21.02.2020
comment
Итак, связанный с описанным сценарием, это каким-то образом процесс между измерением компонентов реального мира и решением. Большое вам спасибо за вашу быструю реакцию почти каждый день и в ночное время! Когда я стану немного более опытным, я бы хотел улучшить документацию. - person The Random Forum Guy; 22.02.2020