Как использовать программирование ограничений для оптимизации корзин покупок?

Question

У меня есть список предметов, которые я хочу купить. Товары предлагаются в разных магазинах и по разным ценам. В магазинах есть индивидуальные расходы по доставке. Я ищу оптимальную стратегию покупок (и java-библиотеку, поддерживающую ее), чтобы купить все предметы с минимальной общей стоимостью.

Пример:

• Item1 предлагается в Shop1 за 100 долларов, в Shop2 за 111 долларов.
• Item2 предлагается в Shop1 за 90 долларов, в Shop2 за 85 долларов.
• Стоимость доставки Shop1: 10 долларов США, если общая сумма заказа
• Стоимость доставки Shop2: 5 долларов США, если общая сумма заказа

• Если я куплю Item1 и Item2 в Shop1, общая стоимость составит $ 100 + $ 90 + $ 0 = $ 190.
• Если я куплю Item1 и Item2 в Shop2, общая стоимость составит $ 111 + $ 85 + $ 0 = $ 196.
• Если я куплю Item1 в Shop1 и Item2 в Shop2, общая стоимость составит $ 100 + $ 10 + $ 85 + $ 0 = 195.

Я получу минимальную цену, если я закажу Item1 и Item2 в Shop1: $ 190

Что я пробовал до сих пор

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

         | shop1 | shop2 | shop3 | ...
-----------------------------------------
item1    | p11   | p12   | p13   |
item2    | p21   | p22   | p23   |
 .       |       |       |       |
 .       |       |       |       |
-----------------------------------------
shipping | s1    | s2    | s3    |
limit    | l1    | l2    | l3    |
-----------------------------------------
total    | t1    | t2    | t3    |
-----------------------------------------

Моя идея состояла в том, чтобы определить эти ограничения:

• каждая цена "p xy " определяется в домене (0, c), где c - цена товара в этом магазине
• только одна цена в строке должна быть ненулевой
• если один или несколько предметов куплены в одном магазине, а сумма цен ниже предела, то к общей стоимости добавьте стоимость доставки
• Общая стоимость магазина - это сумма цен на все товары в магазине
• общая стоимость - сумма всех сумм магазина

Цель - "общая стоимость". Я хочу минимизировать это.

В креме я не смог выразить ограничение "если тогда" для условных транспортных расходов.

В choco эти ограничения существуют, но даже для 5 предметов и 10 магазинов программа работала в течение 10 минут, не найдя решения.

Вопрос

Как мне выразить свои ограничения, чтобы сделать эту проблему разрешимой для решателя программирования ограничений?

Answer 1

Я реализовал эту проблему в MiniZinc (язык программирования с ограничениями высокого уровня): shopping_basket.mzn . Он довольно прост и, возможно, может быть использован в качестве модели для вашей модели Java.

Для модели Choco, вы пробовали разные стратегии поиска? Другая стратегия может быть быстрее.

Кстати, еще один решатель программирования Java-ограничений, который вы можете попробовать - JaCoP .

Answer 2

То, о чем вы спрашиваете, это, по сути, проблема k-ранца . На странице википедии, которая мне понравилась, есть множество ресурсов по ее решению. Однако эта проблема полностью решается NP-Complete, поэтому вам, возможно, захочется найти решение, близкое к лучшему, через имитированный отжиг или другие формы для поиска в пространстве проблемы.

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

Проблема заключается в том, что вы покупаете по одному предмету. Целью является минимальная цена. Я думаю, то, что у вас есть, довольно хорошо, хотя я не слишком уверен в пунктах пули один и два.

каждая цена "p xy" определяется в домене (0, c), где c - цена товара в этом магазине только одна цена в строке должна быть ненулевой

Я бы посчитал, что амортизация доставки будет превышать стоимость купленных товаров, а не добавляться к общей стоимости при выполнении расчетов.

Answer 3

Я не слишком уверен, что это проблема k-ранца. В вопросе упоминались слова «корзины для покупок», но не указывалось вместимость какой-либо конкретной партии. Если вы указали максимальный размер отгрузки, то проблема начинает больше походить на проблему с рюкзаком.

Проблема на самом деле является просто основной проблемой сетевого потока с затратами на транспортировку дуг и затратами в начале координат. Поскольку у вас есть четкая целевая функция - минимизировать транспортировку + стоимость продукта, а также потому, что, скорее всего, будет только одно решение, CP может оказаться не лучшим подходом.

Рассмотрим решение как задачу линейного программирования:

Мин .: транспорт + стоимость продукта

ST: Всего отгружено товара> = Спрос (для каждого товара)

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