Как использовать программирование с использованием ограничительного языка для оптимизации корзин покупок?
У меня есть список изделий, которые я хочу купить. Объекты предлагаются различными магазинами и различными ценами. Магазины имеют отдельные стоимости доставки. Я ищу оптимальную стратегию покупок (и библиотека Java, поддерживающая его) для покупки всех товаров с минимальной общей стоимостью.
Пример:
- Item1 предлагается в Shop1 за 100$ в Shop2 за 111$.
- Item2 предлагается в Shop1 за 90$ в Shop2 за 85$.
- Стоимость доставки Shop1: 10$, если общий порядок <150$; 0$ иначе
- Стоимость доставки Shop2: 5$, если общий порядок <50$; 0$ иначе
- Если я покупаю 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$
Что я попробовал до сих пор
Я задал другой вопрос, прежде чем это привело меня к полю программирования с использованием ограничительного языка. Я взглянул на сливки и choco, но я не выяснял, как создать модель для решения моей проблемы.
| 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 минут, не находя решение.
Вопрос
Как я должен выразить свои ограничения для создания этой проблемы разрешимой для решателя программирования с использованием ограничительного языка?
3 ответа
Я реализовал эту проблему в MiniZinc (язык программирования с ограничениями высокого уровня): shopping_basket.mzn . Это довольно перспективно, и, возможно, его можно было бы использовать в качестве модели для вашей модели Java.
Пробовали ли вы разные стратегии поиска для модели Choco? Другая стратегия может быть быстрее.
Кстати, вы можете попробовать еще одну программу решения Java-ограничений для программирования ограничений - JaCoP .
То, о чем вы спрашиваете, по сути, является проблемой k-knapsack. На странице Википедии, которая мне понравилась, есть множество ресурсов по ее решению. Однако проблема является NP-полной для решения целиком, поэтому вы можете искать близкое к наилучшему решение с помощью имитации отжига или других форм поиска в пространстве задач.
Первое, что нужно помнить, это то, что в проблемах с ограничениями вы, вероятно, потратите значительную часть времени на генерацию решения. В вашем предыдущем примере, хотя пять товаров и десять магазинов кажутся небольшими, на самом деле это порождает большое проблемное пространство (порядка 1e5, не считая усложнения в виде условного ценообразования, которое еще больше усложняет проблему).
Ограничения задачи заключаются в том, что вы покупаете по одной единице каждого товара. Цель - минимальная цена. Я думаю, что то, что у вас есть, довольно хорошо, хотя я не очень уверен в пунктах 1 и 2.
каждая цена "p xy" определена в области (0, c), где c - цена товара в этом магазине только одна цена в строке должна быть ненулевой
я бы рассмотрел возможность амортизации доставки по стоимости купленных товаров, а не добавлять ее как общую стоимость при вычислениях.
Я не слишком уверен, что это проблема k-knapsack. В вопросе упоминаются слова "корзины", но не указывается вместимость какого-либо груза. Если бы вы указали максимальный размер груза, то проблема стала бы больше похожа на задачу о ранце.
На самом деле эта проблема - просто базовая проблема сетевого потока с затратами на транспортировку по дугам и затратами в начале координат. Поскольку у вас есть четкая целевая функция - минимизировать стоимость транспортировки + стоимость продукта, и поскольку, скорее всего, существует только одно решение, CP может быть не лучшим подходом.
Рассмотрим решение как задачу линейного программирования:
Мин: Транспорт + Стоимость продукта
ST: Общее количество отгруженного продукта >= Спрос (для каждого продукта)
Возможно, вам придется разработать несколько кусочно-линейных уравнений для стоимости транспортировки, но это не должно быть проблемой.