Почему использование линейного целочисленного программирования (ILP), хотя оно NP-Complete?

Вопрос может быть глупым, но это действительно меня смущает в течение длительного времени.Почему использование линейного целочисленного программирования (ILP), хотя оно NP-Complete?

Я прочитал много документов в беспроводной сети датчиков. Многие исследователи моделируют свои проблемы в форме ИЛП. Однако ILP является NP-Complete, поэтому он неэффективен для решения проблемы.

Итак, почему люди пишут свои проблемы в форме ИЛП? Они делают это, чтобы сделать свою проблему понятной и понятной? Или я ошибаюсь в понимании отношений между ILP и NPC?

Я очень благодарен, что вы можете помочь мне решить этот вопрос.

источник

2016-02-12 Ruisong

Один факт о непрерывном LP: Алгоритм Simplex является экспоненциальным временем в худшем сценарии ([Klee-Minty cube] (https://en.wikipedia.org/wiki/Klee%E2%80%93Minty_cube)), тогда как Interior Точечный метод известен как полиномиальный алгоритм времени. Тем не менее, Simplex на практике намного быстрее, чем внутренняя точка. «Трудно теоретически» не означает «медленное на практике», например Cplex реализует многие эвристики, стратегии поиска, предварительную обработку, прежде чем перейти к самому процессу решения. –

Хотя вопрос может быть рассмотрен не по теме, в основном есть несколько вопросов.

Вы правы, что общее целочисленное линейное программирование - это NP -hard.
Если нужно решить определенную проблему, и общее целочисленное линейное программирование является наиболее конкретным способом ее формулировки, то о ней ничего нельзя сделать; некоторые проблемы просто трудно решить.
В некоторых случаях можно использовать релаксацию LP, либо в качестве эвристического, либо некоторого приближающего отношения можно доказать.

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

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

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

источник

2016-02-12 11:59:21 Codor

Привет, Кодор. Спасибо за вашу помощь, и ваш ответ действительно заставит меня получить еще более глубокое понимание. – Ruisong

В некоторых документах люди сравнивают результаты своих эвристических алгоритмов с результатами, полученными от ILP. Неужели их просто хотят показать, что их результаты могут приблизиться к оптимальным? Кстати, что вы имеете в виду, сортируя? – Ruisong

_sorting_ Я имею в виду перегруппировку записей для удовлетворения некоторого предопределенного порядка, как в _Quicksort_. Мой комментарий немного преувеличен, чтобы сообщить, что если модель для представления проблемы может быть выбрана произвольно простой, то в первую очередь не будет проблем. – Codor

NP-hard относится к сложности алгоритмов в худшем случае. Для большинства NP-жестких проблем у нас есть эффективные алгоритмы (эвристические или точные), которые хорошо выполняют , даже если они плохо работают в худшем случае. Таким образом, ILP - очень полезный инструмент на практике, даже если есть некоторые проблемы, из-за которых он плохо справляется.

У меня есть молоток. Есть несколько заданий, в которых мой молоток просто не годится, или займет очень много времени. Но это все еще очень полезный инструмент, потому что он может очень много работать для меня.

ILP - это, во многом, то же самое.

источник

2016-02-13 00:37:20 grendelsdad

Почему использование линейного целочисленного программирования (ILP), хотя оно NP-Complete?

ответ

Смежные вопросы