Ищите модель, чтобы представить эту проблему, которая, я подозреваю, может быть NP-полной - PullRequest
Новая
       63

Ищите модель, чтобы представить эту проблему, которая, я подозреваю, может быть NP-полной

3 голосов
/ 23 августа 2010

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

Существует группа складов, каждый из которых способен хранить и распределять 200 различных продуктов из 1000 возможных продуктов, которые производит Компания А.Каждый склад снабжен 200 товарами и назначенными заказами, которые они затем должны выполнить из своих запасов в наличии.

Проблема заключается в том, что каждый склад должен быть самодостаточным.Будет заказ на произвольное количество товаров (обычно 5-10), которое назначается на склад.Затем склад пакует необходимые для заказа продукты и отправляет их вместе.Для любого товара, которого нет на складе, товар должен быть доставлен на склад отдельно, прежде чем заказ может быть отправлен.

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

Например (с использованием продуктов, каждый из которых представлен буквой, и складов, способных хранить 5 линий продуктов): 

Warehouse 1: [A, B, C, D, E]
Warehouse 2: [A, D, F, G, H]

Order: [A, C, D] -> Warehouse 1
Order: [A, D, H] -> Warehouse 2
Order: [A, B, E, F] -> Warehouse 1 (+1 separately ordered)
Order: [A, D, E, F] -> Warehouse 2 (+1 separately ordered)

Цель состоит в том, чтобы использовать исторические данные, чтобы минимизировать количество индивидуально заказанных продуктов в будущем.Как только склады будут настроены определенным образом, программа просто определит, какой склад сможет обработать заказ с минимальными накладными расходами.

Это сразу вызывает у меня проблему стиля машинного обучения.Это также выглядит как комбинация некоторых известных проблем NP-Complete, хотя ни одна из них, похоже, не подходит должным образом.

Существует ли модель, которая представляет проблему такого типа?

Ответы [ 2 ]

2 голосов
/ 23 августа 2010

Если я правильно понимаю, вам нужно разделить задачи:

  • Предсказать, что каждый склад должен предварительно купить
  • Получить лучший склад для заказа

Что касается первой проблемы, я указываю вам на приз netflix : это была почти та же проблема, и были предложены отличные решения.(Мой справочник по обработке данных находится дома, и я не могу вспомнить точное ключевое слово для Google, извините. Попробуйте "временной ряд интеллектуального анализа данных")

Во втором случае это проблема для Пролога.

  • Установите стоимость для отдельного заказа товара
  • Установите стоимость, например, близость к клиенту
  • Установите стоимость для уже владеющего продуктом 0
  • Создайте правило для получения продукта: купите его, если у вас его нет, получите его, если сделаете
  • Установите правило для получения всех продуктов: foreach product, правило выше
  • получите стоимость этого правила
  • Осторожно попросите Пролога найти решение.Если он недостаточно хорош, спросите больше.

Если вы не хотите использовать Prolog, есть несколько библиотек ограничений.Просто Google "библиотека ограничений <insert your programming language here>"

1 голос
/ 23 августа 2010

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

Как только у вас есть данные о совместном вхождении, которыми вы довольны, вам все еще остается назначение предметов на склады.Это немного похоже на проблему покрытия множеств, но не совсем то же самое.Эта проблема NP-сложная.

...