Еще одна идея, которая приходит на ум, это многогранная оптимизация .По сути, линейное программирование - это эффективный способ решения задач оптимизации, включающих линейные неравенства и непрерывные переменные, но ограничение переменных целыми числами приводит к NP-сложной задаче оптимизации в целом.Это прискорбно, потому что огромное количество проблем может быть выражено как задачи целочисленного программирования.
Обычный подход состоял в том, чтобы исчерпывающе перечислить все возможные решения и выбрать лучшее, возможно, используя ответвление и привязку кобрезать части пространства поиска, которые не могут быть оптимальными.Иногда это может работать довольно хорошо, но новый многогранный подход часто значительно лучше.
Метод, который я понимаю лучше всего, - это метод плоскости разреза , в котором линейная релаксацияпроблема решена (например, с помощью симплексного алгоритма);если решение оказывается интегральным, у нас есть ответ и для целочисленного ограничения задачи.Если это не так, то ищется плоскость, которая отделяет найденное нецелое решение от допустимой области целочисленных решений.Эта плоскость затем добавляется к задаче в качестве ограничения, и новая проблема решается снова с использованием линейного программирования.Это продолжается до тех пор, пока не будет получено интегральное решение.
Ясно, что такая плоскость должна существовать;кроме того, существует универсальный алгоритм для их поиска (хотя его производительность обычно очень слабая).Исследователи посвятили много времени поиску лучших алгоритмов для решения этой «проблемы разделения» для конкретных типов проблем.Самым известным примером является задача коммивояжера, где увеличение вычислительной выполнимой задачи на является ничем иным, как ошеломляющим .
Подход с использованием плоскостей резания обеспечивает лучшую производительность, одновременно ограничивая количество ограничений.на рассмотрении;альтернативный подход - генерация столбцов , в котором число одновременно оптимизируемых переменных ограничено.
Не уверен, действительно ли это соответствует вашим критериям алгоритма неявного графа, но это, безусловно, увлекательнонеочевидный подход я думаю!