Как определить фиксированные и нефиксированные переменные в решениях экземпляра целочисленной выполнимости?

У меня есть (выполнимая) (линейная) целочисленная проблема выполнимости. Задача содержит, помимо прочего, набор переменных с логическими значениями, назовем их x1...xn, причем одним из ограничений является сумма (x< sub>1...xn) = C. Я хочу определить, какие из этих переменных являются фиксированными, и фиксированные значения указанных переменных (например: какая из этих переменных принимает определенное значение (0 или 1, так как они снова имеют логическое значение) во всех возможных решениях).

У меня есть рабочее решение, просто оно медленное (мягко говоря):

  1. Добавьте ограничение, что x1 == 0
  2. Проверьте, решаема ли проблема
  3. Удалите ограничение, добавленное на шаге 1.
  4. Добавьте ограничение, что x1 == 1
  5. Проверьте, решаема ли проблема
  6. Удалите ограничение, добавленное на шаге 4.
  7. Утверждают, что хотя бы одно из 2 и 5 выполнено успешно.
  8. Если оба выполнены успешно, переменная не фиксируется. В противном случае переменная фиксируется для любого ограничения, при котором проблема все еще была разрешима.
  9. Повторите 1...8 для x2...xn

Проблема в том, что это медленно. В частности, требуется решить задачу O(n), а точнее 2*n раз. (Я передаю предыдущее решение для теплого запуска решателя, но только запуск решателя занимает почти все время.)

Есть ли более быстрый метод? В частности, тот, который требует вызова решателя меньше раз?

Что-то, о чем я думал, что, к сожалению, не работает как есть, состоит в том, чтобы превратить это в проблему ILP и решить ее дважды, один раз с целью максимизации sum(x1...x n), один с целью минимизировать одно и то же и проверить, какие переменные изменяются. К сожалению, это не работает в целом. Для (встречного) примера: логические переменные x и y, где x+y=1. Максимизация и минимизация могут дать одно и то же, даже если ни одна из переменных не является фиксированной.


linear-programming integer-programming constraint-satisfaction
person TLW    schedule 26.06.2014    source источник

Ответы (2)


arrow_upward
2
arrow_downward

То, что вы описываете в своем вопросе о том, что вы делаете для переменной, обычно называется зондированием в сообществе MILP (смешанное целочисленное линейное программирование), и, к сожалению, на самом деле нет ничего теоретически лучше, чем вы можете сделать. На практике, однако, вы можете немного ускорить процесс.

Как вы отметили в своем собственном ответе, для каждой переменной вы можете отслеживать, видели ли вы эту переменную как False и True в каком-либо решении, и тестировать только тот параметр, который вы раньше не видели. (Обратите внимание, что самое первое решение, которое вы получите при исправлении x_1, установит один из SeenFalse или SeenTrue для каждой переменной, сокращая количество экземпляров для решения вдвое.)

Вы можете сделать еще больше. Когда вы смотрите на конкретный экземпляр (т. е. когда, например, SeenFalse_i не установлен, а вы устанавливаете x_i на False), вы можете превратить ILSAT в ILP, используя случайную цель. Наличие цели имеет несколько целей

  • используя разные случайные цели в каждом случае, который вы должны решить, надеюсь, вы получите широкий спектр решений, и вы сможете установить много виденных... флагов.
  • Используя оптимальное значение решения для этой ILP и LP-релаксацию ILP, вы можете выполнить фиксацию сниженной стоимости, т. е. на основе сниженной стоимости булевых переменных, выходящих за рамки базисных, вы сможете доказать, что они могут. t принимают любое другое значение, кроме того, в котором они находятся в данный момент, что потенциально позволяет установить больше видимых... флагов.
person LaszloLadanyi    schedule 27.06.2014

arrow_upward
0
arrow_downward

Казалось бы, у меня есть решение моего собственного вопроса. Это не идеально, и поэтому я бы принял другие ответы, но вот:

  1. Превратите ILSAT в ILP.
  2. Для каждой проверяемой переменной установите seenTrue и seenFalse для этой переменной на False.
  3. Установите целевую функцию, чтобы максимизировать сумму переменных, которые, как было замечено, равны False, но не True, за вычетом суммы переменных, которые, как было замечено, равны True, но не False.
  4. Решите ИЛП.
  5. Если ни одно из значений, о которых известно, что они неизвестны, не изменилось с момента последней итерации, перейти к 8.
  6. Для каждой переменной в решении установите seenTrue или seenFalse на True, в зависимости от того, является ли переменная True или False.
  7. Перейти к 2
  8. Для каждой переменной, если было замечено только одно из True или False, переменная фиксируется на этом значении. В противном случае (было замечено и то, и другое) он не фиксируется.

Фактически то, что я делаю, всегда пытаюсь максимизировать количество переменных, для которых заданы значения, которые они еще не установили.

person TLW    schedule 27.06.2014
comment
Я не думаю, что этот алгоритм будет работать. Настроенная вами ILP вполне может иметь несколько альтернативных оптимальных решений. Таким образом, выскакивая из 5, можно утверждать, что переменная должна быть зафиксирована одним способом, хотя на самом деле существует альтернативное решение, доказывающее обратное. - person LaszloLadanyi; 27.06.2014
comment
Я согласен; это выглядит неправильно. Я думаю, что лучший подход состоит в том, чтобы изменить вашу исходную программу, чтобы просмотреть каждое решение и отметить, изменились ли значения переменных между ним и предыдущим решением. В зависимости от того, какие решения будут найдены, вам может потребоваться запустить решатель всего несколько раз. Кроме того, запишите решение как новое ограничение, чтобы больше никогда его не найти. т.е. если решение было x1 !x2 x3 x4, добавьте требование (!x1 или x2 или !x3 или !x4), которое гарантирует, что вы никогда не увидите одно и то же решение дважды при тестировании каждой переменной. - person Kyle Jones; 27.06.2014
comment
Можете ли вы привести контрпример? Потому что это дает ожидаемые результаты для меня в каждом экземпляре, который я тестировал до сих пор. Цель в основном сводится к изменению как можно большего количества переменных по сравнению с прошлым разом, когда мы еще не знаем, что они не фиксированы. Известно, что оно не фиксировано, поэтому все оставшиеся переменные фиксированы. - person TLW; 27.06.2014