如何使用约束编程优化购物篮？ [英] How to use constraint programming for optimizing shopping baskets?
问题描述
我有一个我想购买的商品列表。项目由不同的商店和不同的价格提供。商店有单独的交付成本。我正在寻找一个最优的购物策略（和一个java库支持它）以最低的总价购买所有的项目。
I have a list of items I want to buy. The items are offered by different shops and different prices. The shops have individual delivery costs. I'm looking for an optimal shopping strategy (and a java library supporting it) to purchase all of the items with a minimal total price.
- Item1在Shop1提供$ 100，在Shop2提供$ 111。
- Item2在Shop1上以$ 90提供，在Shop2以$ 85提供。
- Shop1的交货成本：如果总订单< $ 150; $ 0否则
- Shop2的交货成本：如果总订单< $ 50; $ 0否则
- Item1 is offered at Shop1 for $100, at Shop2 for $111.
- Item2 is offered at Shop1 for $90, at Shop2 for $85.
- Delivery cost of Shop1: $10 if total order < $150; $0 otherwise
- Delivery cost of Shop2: $5 if total order < $50; $0 otherwise
- 如果我在Shop1购买Item1和Item2，总成本是$ 100 + $ 90 + $ 0 = $ 190。
- 如果我在Shop2购买Item1和Item2，总成本是$ 111 + $ 85 + $ 0 = $ 196。
- 如果我在Shop1购买Item1，在Shop2购买Item2，则总成本为$ 100 + $ 10 + $ 85 + $ 0 =
195.
- If I buy Item1 and Item2 at Shop1 the total cost is $100 + $90 +$0 = $190.
- If I buy Item1 and Item2 at Shop2 the total cost is $111 + $85 +$0 = $196.
- If I buy Item1 at Shop1 and Item2 at Shop2 the total cost is $100 + $10 + $85 + $0 = 195.
如果我在Shop1订购Item1和Item2，我得到最低价格：$ 190
I get the minimal price if I order Item1 and Item2 at Shop1: $190
我问过另一个问题到约束编程领域。我看看奶油和 choco ，但我没有想出如何创建一个模型来解决我的问题。 p>
I asked another question before that led me to the field of constraint programming. I had a look at cream and choco, but I did not figure out how to create a model to solve my problem.
| shop1 | shop2 | shop3 | ...
-----------------------------------------
item1 | p11 | p12 | p13 |
item2 | p21 | p22 | p23 |
. | | | |
. | | | |
-----------------------------------------
shipping | s1 | s2 | s3 |
limit | l1 | l2 | l3 |
-----------------------------------------
total | t1 | t2 | t3 |
-----------------------------------------
我的想法是定义这些约束：
My idea was to define these constraints:
- 每个价格p xy 在域（0，c）中定义，其中
是此商店中的商品的价格 - 一行中只有一个价格应为非零。
- 如果从一个商店购买一个或多个项目，且价格的总和低于limit，
- 商店总成本是商店中所有商品的价格之和
- 总成本是所有商品的总价商店总额
- each price "p xy" is defined in the domain (0, c) where c is the price of the item in this shop
- only one price in a line should be non zero
- if one or more items are bought from one shop and the sum of the prices is lower than limit, then add shipping cost to the total cost
- shop total cost is the sum of the prices of all items in a shop
- total cost is the sum of all shop totals
目标是总成本。我想尽量减少这种情况。
The objective is "total cost". I want to minimize this.
在奶油中，我无法表达条件运输成本的if then约束。
In cream I wasn't able to express the "if then" constraint for conditional shipping costs.
在choco中，这些约束存在，但即使对于5个项目和10个商店，程序运行了10分钟，但没有找到解决方案。
In choco these constraints exist, but even for 5 items and 10 shops the program was running for 10 minutes without finding a solution.
我应该如何表达我的约束，使这个问题可解的约束编程解决方案？
How should I express my constraints to make this problem solvable for a constraint programming solver?
推荐答案
我在 MiniZinc 中实现了此问题（高级约束编程语言）： shopping_basket.mzn 。
I have implemented this problem in MiniZinc (a high level constraint programming language): shopping_basket.mzn. It is quite forward and maybe could be used as a model for your Java model.
对于Choco模型，你尝试了不同的搜索策略吗？不同的策略可能更快。
For the Choco model, have you tried different search strategies? A different strategy may be faster.
顺便说一下，你可能想要检查的另一个Java约束编程解算器是 JaCoP 。
By the way, one other Java constraint programming solver you may want to check out is JaCoP.
这篇关于如何使用约束编程优化购物篮？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
