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

Вопрос может и глупый но он реально меня давно смущает.

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

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

Я очень ценю, что вы можете помочь мне решить этот вопрос.


integer-programming np-complete
person Ruisong    schedule 12.02.2016    source источник
comment
Один факт о непрерывном LP: симплексный алгоритм имеет экспоненциальное время в худшем случае (Klee– Minty cube), тогда как известно, что метод внутренних точек является алгоритмом с полиномиальным временем. Тем не менее, Simplex на практике намного быстрее, чем внутренняя точка. «Сложно в теории» не означает «медленно на практике», например, Cplex реализует множество эвристик, стратегий поиска, предварительной обработки, прежде чем перейти к самому процессу решения.   -  person serge_k    schedule 12.02.2016

Ответы (2)


arrow_upward
2
arrow_downward

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

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

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

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

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

person Codor    schedule 12.02.2016
comment
Привет, Кодор. Спасибо за вашу помощь, и ваш ответ действительно заставляет меня глубже понять. - person Ruisong; 12.02.2016
comment
В какой-то статье люди сравнивают результаты своих эвристических алгоритмов с результатами, полученными в ILP. Они просто хотят показать, что их результаты могут быть приближены к оптимальным? Кстати, что вы имеете в виду под сортировкой? - person Ruisong; 12.02.2016
comment
Под сортировкой я подразумеваю перестановку записей в соответствии с некоторым предопределенным порядком, как в быстрой сортировке. Мой комментарий немного преувеличен, чтобы сообщить о том, что если модель для представления проблемы может быть выбрана произвольно простой, то, во-первых, проблемы не будет. - person Codor; 12.02.2016

arrow_upward
0
arrow_downward

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

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

ILP во многом одно и то же.

person LarrySnyder610    schedule 13.02.2016