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

Question

У меня есть система, в которой мне нужно рассчитать возможный диапазон значений для каждой переменной (мне не нужно находить решение для системы).Вот иллюстрация примера системы:

Каждая синяя линия - это узел (названный надписью над ним), а серые линии - этокрая между узлами.Имеется начальное ограничение: например, ребро BC может быть любым действительным числом от 0 до 1 включительно, а ребро BE может быть любым числом, большим или равным 9. Узлы не могут пересекать другие узлы.Полезно представить их в виде металлических стержней, которые могут выдвигаться и складываться, толкая синие пластины.

Моя цель - рассчитать для каждого края минимальную и максимальную длину, которой они могут быть.Начальные ограничения устанавливают систему, но конечный результат может быть более ограниченным, чем они.Например, у ребра DF начальная min / max равна (2, ∞), но вы можете видеть, что на самом деле она не может быть короче 3, так как при сжатии она тянет D в E, а E к F, а EF имеетминимум 3. Конечный результат будет следующим:

Предостережение: мне нужен алгоритм, который может масштабироваться до сотен тысячузлов, которые были бы более плотно связаны, чем этот пример.Он не может экспоненциально увеличиваться во время выполнения, поскольку мне также приходится запускать этот алгоритм сотни тысяч раз.

Я попробовал метод, который давал некоторые более ограниченные значения, но не самые ограниченные значения.Чтобы визуализировать метод, я, по существу, вытянул все пластины влево как можно дальше, а затем записал максимальную позицию каждой пластины.Затем я сделал то же самое, потянув их вправо.Затем для каждого ребра я просто нахожу разницу между значениями каждой пластины.Этот метод очень эффективно находит максимальные значения, но проблема в том, что у вас есть ситуация, подобная приведенной в этом примере, когда CD как бы «заблокирован» для BE с помощью BC и DE.Это не может быть 6, так как система только позволяет ему быть на 2 короче, чем 9. Мне нужен способ, который находит истинное минимальное значение 7. Мой метод не фиксирует это «блокирующее» отношение: когда вы тянете C вседо левой стороны, BC равно 0, а когда вы вытягиваете D полностью вправо, DE равно 0, но они не могут быть оба 0, если CD равен 6.

В этом примереЛегко видеть, что CD ограничен BE, но на практике система будет гораздо плотнее и больше, чем в примере, и обнаружение таких ситуаций кажется нетривиальным.Если метод предполагает поиск вокруг него локально, я боюсь, что он будет плохо масштабироваться, но это может быть единственным способом.

Если это смоделировано как задача линейного программирования (AB + BC = AC, AB>1 и т. Д.), Возможно, есть некоторые атрибуты этой системы, которыми можно воспользоваться: тот факт, что все коэффициенты ограничений равны 1, и что в ограничениях есть только сложение и вычитание.

У кого-нибудь есть какие-либо предложения о том, как подойти к этой проблеме?Или есть какие-то идеи о том, на какую сложность во время выполнения я должен реально надеяться?Спасибо!

Answer 1

Хорошо, думаю, я понял это.Спасибо всем, кто откликнулся, это привело меня к некоторым полезным исследованиям.

Я смог воспользоваться тем фактом, что я не запускаю алгоритм каждый раз на другом графике, но на том же самом, чтопостоянно изменяетсяЯ могу сохранить старые значения и обновлять их каждый раз, содержащие обновления для локально измененных областей.Распространение не должно заходить слишком далеко, если новые изменения не слишком радикальны.

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

Посмотрите на картинку и представьте ее как физическую систему: между ними есть синие пластины с полосами, которые могут сжиматься и расширяться.Чтобы найти самую короткую полосу, я потяну все пластины влево как можно больше.Удерживая влево давление на правую пластину штанги, я вытягиваю ее левую пластину к себе как можно больше.Движение распространяет изменение положения на все стержни, связанные с ним.Это потенциально может немного сдвинуть правую пластину назад, что нормально.Энергия движения поглощается дополнительным провалом в окружающих барах.Как только энергия разлетается по системе и успокаивается, я записываю окончательное расстояние между пластинами.

Нахождение самого длинного стержня может быть одинаковым: я перемещаю пластины влево, затемотодвиньте правую пластину от левого как можно дальше.

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

Это технически не линейно, но с моими данными это большую часть времени.

Answer 2

Учитывая

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

вы, похоже, попали в беду.

Это выглядит следующим образомпроблема для меня:

ICSP (проблема удовлетворенности интервалами).«Дан набор E уравнений, относящихся к множеству переменных, связанных с интервальными областями.Уточните области настолько, насколько это возможно, не теряя возможных точных решений E, т. Е. Определите для каждой переменной минимальный непротиворечивый подинтервал в своей области ».

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

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

Посмотрите на

Белотти, Пьетро и соавт.«На технико-экономических обоснованиях ограничения границ».(2012).

, который дает некоторый обзор.

Вы найдете множество ключевых слов, ведущих к различным исследовательским сообществам (Математическая оптимизация, Программирование с ограничениями, AI), таких как:

• Укрепление границ на основе технико-экономического обоснования
• Распространение границ
• ограничение / уменьшение диапазона
• фильтрация / уменьшение домена .

Существует простой подход 2n LP-solving, но, учитывая ваши цифры, этого будет недостаточно, кажется, неважно, если Simplex- или используются методы внутренней точки.

В статье также представлен подход с одним LP, но он, вероятно, не будет масштабироваться.

В зависимости от того, насколько важна эта проблема для вас, сколько вы хотите инвестировать и каковы ваши точныецель, если глобальный выбор невозможен (учитывая некоторый временной интервал), вы можете изучить эту статью, ее ссылки и ключевые слова и, возможно, проверить, что находится внутри решателей математической оптимизации (ссылки указывают на эту основную проблему):

• Couenne (что несколько связано с бумагой; хотя реализованный метод может отличаться от бумаги)
• SCIP
  • (лицензия! -> не для коммерческого использования)
• Clp

и другие, где каждый из нихдолжен включать некоторый подход с ограничением границ (для линейных равенств).В целом, я ожидаю, что глобальные решатели, такие как Куэнн, будут тратить больше времени на этот шаг;поскольку оставшаяся оптимизация обычно доминирует над этим легко по сравнению с LP-решателями, такими как Clp.

Answer 3

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

Простые временные сети [1] - это сети ограничений с переменными решения t_i (они соответствуют вашейузлы / метки) и ограничения вида: L_ij <= t_j-t_i <= U_ij (где L_ij и U_ij - известные границы между некоторыми парами узлов, например, в вашем примере: 6 <= DC <= + oo).И проблема состоит в том, чтобы найти самые узкие границы для каждой дуги (то есть для каждой t_j-t_i), которая совместима с ограничениями. </p>

Эти проблемы были тщательно изучены во временных рассуждениях и планировании.

В частности, ваша проблема является полиномиальной.Простой метод - запустить алгоритм Флойд-Варшалла для вычисления кратчайшего пути из всех пар, как показано в [1].Но он будет работать в O (n ^ 3), что, вероятно, слишком дорого для вас.Также существуют более эффективные алгоритмы, такие как, например, предложенный в [2].

[1] Dechter, R .;Мейри, я .;и Pearl, J. 1991. Сети временных ограничений.Искусственный интеллект 49 (1–3): 61–95.

[2] Планкен Л.;де Вердт М .;и ван дер Крогт Р. P3C: новый алгоритм для простой временной задачи.Материалы восемнадцатой Международной конференции по автоматизированному планированию и планированию (ICAPS 2008).

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

Answer 4

Похоже, что теория удовлетворенности по модулю будет полезна здесь.Приведите ваши ограничения длины в качестве начальных аксиом (т. Е. 0 <= BC <= 1 и т. Д.) С теорией, которая позволяет добавлять расстояния (т. Е. AB + BC = AC для всех A, B, C) и разрешать SMT-решатель.вычислить ограничения, которые он может вывести из этого.Я бы не удивился, если бы «оптимальные» ограничения, которые вы ищете, были найдены в почти линейное время, так как они, кажется, довольно легко вывести. </p>

Обратите внимание, однако, что решатели SMT построены с SAT вразум, который является NP-сложным, поэтому у вас не будет никаких субэкспоненциальных теоретических гарантий на время выполнения.Если то, что вам нужно, - это фактическое время выполнения, чтобы быть приемлемым, фактические решатели SMT (с созданным вручную условием остановки) были бы моим лучшим предположением, потому что они очень эффективны на практике, даже если их сложность в худшем случае экспоненциальная.Если вам также нужны теоретические гарантии времени выполнения в наихудшем случае, я бы предложил написать свой собственный SMT-подобный генератор доказательств и доказать верхнюю границу для числа не избыточных ограничений, которые может генерировать ваша модель, что также кажется выполнимым, но можетоказывается экспоненциальным.

Вы упомянули линейное программирование, и поиск экземпляра, который удовлетворяет вашим ограничениям, действительно является проблемой LP.Однако здесь вас интересует не решение ограничений, а действительные ограничения с оптимальной затяжкой.Это говорит о том, что LP - это не то, что вы ищете здесь (или не как минимум).Проблемы LP имеют форму, которую вы упомянули, но дают решения, которые удовлетворяют заданным ограничениям, и, кажется, довольно трудно превратить это обратно в ограничения без исчерпывающего перечисления решений, которые вам не нужны.Удовлетворенность, с другой стороны, пытается вывести скрытые ограничения, подразумеваемые первоначальными ограничениями, и надеется найти что-то, что не может быть выполнено (в этом случае он просто возвращает UNSAT).Если ваши ограничения действительно выполнимы, то созданные «скрытые ограничения» будут более жесткими, чем ваши первоначальные ограничения, и вам нужно будет только извлечь подмножество их, которые вас интересуют.

Именно поэтому я быпредлагаю копаться в SMT, а не в LP.Имейте в виду, что эта проблема может быть сложнее, чем кажется, так как в ней можно кодировать SAT, что означает, что вам придется платить экспоненциальное время за наихудший случай, но вы, возможно, сможете найтиприблизительные решения в разумные сроки или убедитесь, что средняя сложность все еще приемлема.