Интегральность в выпуклой оболочке линейного программирования

Question

Как можно сформулировать выпуклую оболочку задачи линейного программирования (ЛП) как интегральную? Существуют ли общие методы для этого?

Answer 1

Чтобы добавить немного к ответу Мартина выше (я думаю, что это слишком долго для комментария):

1. Существует известная мне общая процедура, называемая процедурой Хватала-Гомори, которая позволяет в конечном итоге описать выпуклую оболочку путем добавления разрезов Гоморри. Это очень интересно теоретически; Тем не менее, есть хорошо известный пример, где эта процедура занимает n шаг (параметр в LP) для задачи с двумя переменными и двумя ограничениями, т. е. количество добавленных разрезов не может быть ограничено размером задачи.

2. Полностью унимодулярная матрица часто встречается в задачах, возникающих в теории графов, но это, безусловно, не "общий" метод: вы можете убедить себя, просто определив, что коэффициент A матрица должна быть 0, 1 или -1 в матрице TU, что, конечно, обычно не имеет место в ILP.

Конечно, поскольку решение LP является полиномиальным, а решение ILP является NP-полным, нельзя ожидать, что существует общий эффективный метод для выполнения того, что вы ожидаете, поскольку это почти снизит ILP до LP!

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

Я могу предоставить дальнейшие ссылки в конце недели, если вы заинтересованы.

Answer 2

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

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

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

Это алгоритмы для вычисления выпуклых оболочек целочисленных точек (или из общих многогранников), но они не простые и не "быстрые". Программное обеспечение, которое может помочь вам, вероятно, Porta или Polymake.

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

Надеюсь, это поможет:)

С уважением,

Мартин