NP Complete или NP трудные проблемы в реальной жизни

17

Есть ли у кого-нибудь примеры из реальной жизни, когда они регулярно решают сложные задачи NP или сложные задачи NP (с помощью эвристики, или выбирая неоптимальное решение или что-то еще) в своей работе? Я знаю, что они встречаются в планировании, планировании, проектировании СБИС и т. Д., Но я пытаюсь понять основные отрасли, в которых сегодня работают программисты или инженеры, которые регулярно делают это. Если бы кто-то развивал опыт или библиотеку, скажем, комбинаторную оптимизацию, где можно было бы использовать это как часть работы по программированию?

Есть ли личные счета?

высокая пропускная способность
источник
Что вы подразумеваете под «регулярно»
Конрад Фрикс,
@ Конрад, я думаю, это субъективная идея. Я бы сказал, что более 5-10% усилий сосредоточено на решении np-complete или np-hard проблем.
highBandWidth
Я считаю, что программирование ИИ в играх может быть NP-завершенным.
Майкл К
Существует множество проблем NP-hard (планирование и планирование с ограниченными ресурсами, как правило, NP-hard). Однако комбинаторная оптимизация - неправильный путь. Возможность генерировать 100! Комбинации настолько быстро, насколько это возможно, гораздо менее полезны, чем возможность применения эвристики, зависящей от предметной области.
Дэвид Торнли
@ Давид, я не имел в виду создание комбинаций с помощью комбинаторной оптимизации. Я имел в виду класс проблем, таких как k-SAT или Задача коммивояжера и т. Д.
highBandWidth

Ответы:

8

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

  • Среды разработки для языков и компиляторов. Такие вопросы, как: генерирует ли эта грамматика неоднозначный язык? (Эта проблема на самом деле неразрешима!)
  • Восстановление данных. Повторная сборка частично потерянных пакетов данных или восстановление фрагментированных файлов. (Факторная сложность)
  • Программная безопасность. Оценка всех возможных путей выполнения через часть программного обеспечения, чтобы определить, можно ли приписать некоторое наблюдаемое поведение. (Проблема остановки?)
  • Логистика. Оптимизация использования транспортов на основе пакетов для транспортировки, их размера и куда они должны идти. (Хотя бы экспоненциальный)

Существует множество стандартных примеров, таких как поиск кратчайшего маршрута, планирование работы медсестры и т. Д., Но если вы увлекаетесь комбинаторной оптимизацией, вы знаете о них все :)

Декард
источник
Так есть ли программисты, работающие в логистических компаниях, которые на самом деле посвящены решению этих проблем оптимизации, или большинство этих операций обычно решаются один раз и просто повторяются для большинства компаний? +1 за ряд примеров. Принимал ли ты участие в этом?
highBandWidth
Первые два я написал для инструментов, третий - это то, над чем работают коллеги. Я ожидаю, что крупные логистические компании активно проводят исследования в этой области, поскольку это может сэкономить им миллионы долларов, если они достигнут дополнительной производительности на пару процентов с помощью какого-то нового алгоритма :)
Deckard,
Я взял интервью для роли коммивояжера. У крупной материнской компании была целая комната докторов наук, которые работали в надежде получить улучшение своей маршрутизации на несколько десятых процента. Что стоило бы им несколько миллионов долларов ... каждый день. Так что эти места существуют. Маршрутизация и составление расписаний - вот две важные вещи. Представьте, что у вас 1000 человек и фабрика, которая работает в две или три смены. Теперь назначьте всем работу на следующий месяц, помня об этих 200 правилах и предпочтениях каждого ...
9

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

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

Марк Бут
источник
2
Это классно. Но я думал, что у каждой панели будет один и тот же шаблон, и вы просто решите проблему один раз, а не снова и снова для каждого виджета. Почему вы должны были решить это каждый раз?
highBandWidth
2
Идеальный рисунок был одинаковым для каждой панели, но механическое выравнивание панели, положение предыдущих слоев в процессе и мозаичный характер лазерной скребковой головки означало, что для каждой панели должен был быть рассчитан динамический набор вспомогательных образцов. индивидуально и затем optmised. Это была интересная проблема, особенно из-за нехватки времени.
Марк Бут
7

Я работаю (прямо сейчас) над проблемой биоинформатики множественного локального выравнивания последовательности ДНК. Дело в том, что если множество последовательностей из генов с некоторым общим свойством (схожий профиль экспрессии или связывание одного и того же фактора транскрипции в эксперименте с чип-чипом) в какой-то момент сильно совпадают, то вы, вероятно, нашли причину их общего свойство. Опять же, меня больше интересуют статистические аспекты проблемы. Несмотря на то, что это NP-хард, вы не теряете много, используя эвристику на практике. ИМХО интересная часть проблемы - проблема отношения сигнал / шум.

dsimcha
источник
1
Вы используете классические комбинаторные / аи подходы или статистические. В некотором смысле, все современные nlp, кластеризация, машинное обучение имеют дело с np-complete проблемами, но обычно подвергаются атакам со статистической точки зрения. Тем не менее, это интересно и актуально. Это в академии или промышленности?
highBandWidth
@highBandWidth: мой подход статистический. Я в академии. Весь смысл исследования, которое я провожу, заключается в том, что если вы игнорируете статистические проблемы и просто сосредотачиваетесь на комбинаторной проблеме, происходят плохие вещи.
Дсимча
3

Я на самом деле не знаю, что означает NP Complete / Hard, но я думаю, что автопланирование поставок является своего рода.

Вам необходимо составить план на 90 дней вперед для 100 наименований продукции: пиво! 100 наименований продукции поступают из:

  • есть 10-15 видов сырья 1-го уровня, сваренного в больших банках, и это занимает один день;
  • после заваривания необходимо добавить некоторые материалы (закваска?), и это должен быть отдых в течение 10-15 дней, тогда вы получите 15-20 видов 2-го уровня;
  • наконец, когда все будет готово, нужно добавить некоторые материалы, это материал 3-го уровня, называемый пригодным для питья пивом. 30 сортов пива;
  • пиво может быть разлито в бутылки как 3 дл, 5 дл, иногда оно получает специальное ожерелье (уровень 4), затем оно может быть упаковано в коробку 5х4, 6 упаковок (уровень 5).

Есть машинные «линии» для каждой операции: от заваривания до упаковки. Машины могут выполнять больше операций, скажем, некоторые упаковочные машины могут производить 6 и 3 упаковки, а другие могут делать только 6 упаковок. Есть ограничения, например, скорость, или большой варочный котел предназначен для варки мин. 6000, максимум, 8000 л пива (но если пиво светлого типа, то минимальное значение составляет 5000 л, а максимальное - 7000 л). И так далее, на каждом уровне.

Задача: как я уже говорил, есть план спроса на 100 уровень 5-го уровня (в бутылках, в упаковке). Составьте оптимальный план изготовления для всех 5 уровней, всех машин. Минимизируйте машинные выключатели (например, разлив в бутылки .5, .5, .5, .3, .3, .3 лучше, чем .3, .5, .3, .5, .3, .5, меньше меньше, меньше мертвого времени для разливочных машин). Расстановка приоритетов по заказу: некоторые клиенты требуют отгружать пиво только с более чем 50% срока годности. И т. Д.

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

Это достаточно сложно, или я должен рассказать вам, как работает текстильная фабрика ?

(Личное замечание: Интернет, банк и логистика - сложные области, но они - детские игрушки по сравнению с производственными проблемами.)

Отказ от ответственности: цифры искажены по соображениям безопасности, порядок величины является действительным.

ern0
источник
Вы работаете над чем-то вроде этого или инструментом для решения таких проблем для своего работодателя?
highBandWidth
1
Ну, производство - это логистика. Определенно сложнее, чем финансы в этом отношении. Но, по крайней мере, это касается определенных задач, а не случайных уравнений и слабо определенных порядков работы!
Майкл К
1
Любой вид алгоритма планирования с наилучшим соответствием ресурсов, вероятно, эквивалентен проблеме ранца , которая является NP-полной.
Скотт Уитлок
Мой друг создал систему DP / SP в Excel + VB несколько лет назад. Он не содержит автопланирование, приложение слишком толстое для Excel. Итак, мы только что сделали основанную на MySQL / PHP / AJAX совместную расширяемую структуру (см .: поток данных - так называемый подход на основе потоков - подход) - структуру электронных таблиц (я) и приняли бизнес-логику из XLS-версии (друг) , Мы также реализовали автопланирование (друг). Это была сумасшедшая идея написать электронную таблицу, но она работает. Лучшая часть: XLS-> SQL-переключатель несколько замечательный! Мы можем делать с данными все что угодно (например, автоплан), используя любой инструмент / платформу (PHP, Java, что мы хотим).
ern0
@ ern0, NP-complete / NP-hard в основном относится к тому, как мало ярлыков вы можете даже предположить, что сможете использовать вместо того, чтобы пробовать все возможности по одному. Теоретики тратят много усилий, чтобы найти короткие пути, которые, например, говорят, что если мы знаем, что путь ABC всегда будет длиннее, чем AC напрямую, мы можем сделать его быстрее и оказаться в пределах 50% от оптимального значения. И т.д.