Citeseer/On the Lasserre\Sum-of-Squares Hierarchy with Knapsack Covering Inequalities (2014) 10.1.1.764.6296 — различия между версиями
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| (не показана одна промежуточная версия этого же участника) | |||
| Строка 4: | Строка 4: | ||
доступных алгоритмах аппроксимации. | доступных алгоритмах аппроксимации. | ||
| − | + | ЦЛП емкостного покрытия — это целочисленная программа вида «min{cx : U x ≥ d, 0 ≤ x ≤ b, x ∈ Z+}», где все записи c, U и d неотрицательны. | |
| − | Одна из трудностей аппроксимации задач с емкостным покрытием заключается в том, что отношение оптимального решения IP к оптимальному решению LP может достигать ||d||∞, даже если U состоит из одной строки (то есть задача «Min Knapsack»). | + | Одна из трудностей аппроксимации задач с емкостным покрытием заключается в том, что отношение оптимального решения IP к оптимальному решению LP может достигать <m>||d||_{∞}</m>, даже если U состоит из одной строки (то есть задача «Min Knapsack»). |
В настоящее время самое сильное ослабление линейной программы получается путем добавления (экспоненциально большого числа) допустимых неравенств, введенных Вулси (''Wolsey''), что дает очень мощный способ решения этих проблем. | В настоящее время самое сильное ослабление линейной программы получается путем добавления (экспоненциально большого числа) допустимых неравенств, введенных Вулси (''Wolsey''), что дает очень мощный способ решения этих проблем. | ||
Текущая версия на 15:32, 23 ноября 2021
«On the Lasserre\Sum-of-Squares Hierarchy with Knapsack Covering Inequalities (2014) 10.1.1.764.6296»скачать
«Иерархия Лассерре/Сумма квадратов» — это систематическая процедура усиления релаксаций ЛП путем построения последовательности все более жестких формулировок. Для широкого круга оптимизационных задач этот подход позволяет получить выпуклые релаксации, используемые в лучших доступных алгоритмах аппроксимации.
ЦЛП емкостного покрытия — это целочисленная программа вида «min{cx : U x ≥ d, 0 ≤ x ≤ b, x ∈ Z+}», где все записи c, U и d неотрицательны.
Одна из трудностей аппроксимации задач с емкостным покрытием заключается в том, что отношение оптимального решения IP к оптимальному решению LP может достигать , даже если U состоит из одной строки (то есть задача «Min Knapsack»).
В настоящее время самое сильное ослабление линейной программы получается путем добавления (экспоненциально большого числа) допустимых неравенств, введенных Вулси (Wolsey), что дает очень мощный способ решения этих проблем.
Для задачи «Min Knapsack» мы доказываем, что даже после непостоянного числа уровней «иерархия Лассерра/Сумма квадратов» не улучшает разрыв интегральности 2, подразумеваемый начальными (KC) неравенствами.
Более того, мы показываем, что разрыв интегральности релаксации остается M для особого случая ∑i xi ≥ 1/M при старте со стандартного политопа Min Knapsack.
Мы отмечаем, что Min Knapsack допускает FPTAS, и наши результаты количественно определяют фундаментальную слабость иерархии Лассерра/суммы квадратов для этой базовой задачи.
…»