Программирование ограничений по целочисленным переменным

Я использую GeCode для создания программного обеспечения для решения конкретной задачи. Я смоделировал свою проблему, используя переменные целочисленного набора и некоторые ограничения на эти переменные. Но что касается этого вопроса, давайте рассмотрим более простой случай.

Скажем, у меня есть три заданных переменных, домены которых являются [{}, ..., {1,2,3}], то есть {}, {1}, {2}, {3}, {1,2}, {1 , 3}, {2,3}, {1,2,3} и что мои единственные ограничения - пересечение (var_i, var_j) пусто для всех i и j, а i отличается от j.

Очевидно, если я хорошо понимаю свою логику, она должна давать как минимум var_1 = {1}, var_2 = {2} и var_3 = {3}. Но он также может дать var_1 = {1,2,3} и var_2 = var_3 = {}. Действительно, запуск GeCode с этими переменными и ограничениями дает только один результат: var_1 = var_2 = var_3 = все возможные подмножества {1,2,3}, предполагая, что существуют разные решения (предполагая, что я мог бы выбрать одно подмножество в var_1 и мог бы найти подмножества двух других переменных, удовлетворяющих ограничениям.

Мой вопрос в том, как я могу заставить GeCode перечислять различные комбинации. Потому что, очевидно, моя окончательная модель будет состоять из большего количества целых чисел в наборах и, следовательно, большего количества подмножеств. Таким образом, я не могу позволить себе делать выбор вручную, задавая переменные самостоятельно, поскольку я теряю все преимущества, которые может предложить решатель ограничений.

Есть ли возможность, которая могла бы помочь мне решить эту проблему?


person Nightzus    schedule 18.01.2015    source источник


Ответы (1)


Немного смущает вопрос, но похоже, вы пытаетесь понять, как работает общая согласованность дуги. Вы хотите прояснить, почему Gecode предоставляет вам все возможные подмножества, или вы ищете сам Gecode, чтобы выводить эти подмножества для анализа?

person Kyle Booth    schedule 18.01.2015
comment
Спасибо, что ответили. На самом деле, если бы вы могли пояснить почему, это помогло бы мне. Хотя я думаю, что могу понять, почему gecode выводит это, но не может выразить это формально / подробно ... Но я изначально думал, что с помощью поисковика DFS он будет выводить несколько результатов, а не только один со всеми этими возможными подмножествами. Мне действительно нужно получить одно возможное решение, удовлетворяющее поставленным мною ограничениям, и поэтому я не совсем удовлетворен тем, что я получаю в результате работы GeCode. - person Nightzus; 18.01.2015
comment
Подумайте об этом так: если вы исправите значение var_1 на ЛЮБОЕ значение в его домене, var_2 и var_3 смогут принимать значения для удовлетворения вашего ограничения. Таким образом, в соответствии с вашим ограничением var_1 может быть любым значением. Тот же аргумент применяется к var_2 и var_3, и, таким образом, вы получаете результат каждой комбинации. Если вы добавите дополнительное ограничение, например var_2 ›var_1, то вы увидите, что пространство решений становится меньше. - person Kyle Booth; 18.01.2015
comment
Хорошо, сейчас я понимаю. Но есть ли способ для Gecode автоматически выводить только одно возможное решение из возможных комбинаций (скажем, var_1 = {1}, var_2 = {2} и var_3 = {3})? Как я уже сказал, если бы я сделал это сам по гораздо более крупной проблеме, это было бы не масштабируемо. - person Nightzus; 18.01.2015
comment
Если вы работаете с AMPL, попробуйте проверить, что вам нужно: amp.com/ продукты / solvers / gecode-options - person Kyle Booth; 18.01.2015