Как реализовать «вложенную» функцию стоимости в Gecode?

Question

Я новичок в геокодировании и программировании ограничений в целом.

До сих пор у меня не было особых проблем с выбором геокода, это здорово.Но мне было интересно, как лучше всего выполнить «вложенную» функцию стоимости.В частности, я стремлюсь минимизировать X, но в пространстве решений, для которых X равен, предпочитаете решения, которые минимизируют Y?Я мог бы, вероятно, взломать это, определив функцию стоимости, которая выглядит как X * large_number + Y, но я бы предпочел сделать это правильно, если есть хорошее решение.

Если кто-то может указать мне, чтобы объяснить, как реализоватьэто в Gecode, это было бы очень полезно.Спасибо!

Answer 1

Вы можете определить любой вид критериев оптимизации, используя член ограничения в пространстве в Gecode. См. Раздел 2.5 в Моделирование и программирование с Gecode для примера. В вашем случае прямым путем было бы добавить член ограничения, который добавляет лексикографическое ограничение между предыдущим ответом наилучшего решения и текущим пробелом.

При этом, как правило, оптимизация на основе лексикографического порядка может быть расточительной (слишком много поиска). Часто может быть лучше сначала запустить поиск, оптимизирующий первый компонент (в вашем случае X). После этого повторите поиск с фиксированным значением первого компонента (для X установлено наилучшее возможное значение) и оптимизируйте второе значение (в вашем случае Y). Итерация по мере необходимости для всех элементов в стоимости.