如何使用约束编程来优化购物篮？

Question

我有一份我想买的物品清单.这些物品由不同的商店和不同的价格提供.商店有个人送货费用.我正在寻找最优购物策略(以及支持它的java库)以最低的总价购买所有商品.

例:

• Shop1在Shop1以100美元的价格在Shop2以111美元的价格提供.
• 商品2在Shop1以90美元的价格在Shop2以85美元的价格提供.
• Shop1的运费:如果总订单<$ 150,则需要10美元; 否则为$ 0
• Shop2的运费:如果总订单<$ 50则需要5美元; 否则为$ 0

• 如果我在Shop1购买Item1和Item2,总成本为100美元+ 90美元+ 0美元= 190美元.
• 如果我在Shop2购买Item1和Item2,总成本为111美元+ 85美元+ 0美元= 196美元.
• 如果我在Shop1购买Item1,在Shop2购买Item2,则总成本为100美元+ 10美元+ 85美元+ 0美元= 195美元.

如果我在Shop1订购Item1和Item2: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是该商店中商品的价格
• 一行中只有一个价格应该不为零
• 如果从一个商店购买一件或多件商品且价格总和低于限额,则将运费增加到总成本中
• 商店总成本是商店中所有商品价格的总和
• 总费用是所有商店总数的总和

目标是"总成本".我想尽量减少这个.

在奶油中,我无法表达有条件运费的"if then"约束.

在choco中存在这些限制,但即使对于5个项目和10个商店,程序运行10分钟而没有找到解决方案.

题

我应该如何表达我的约束以使约束编程求解器能够解决这个问题？

Answer 1

我已经在MiniZinc（一种高级约束编程语言）中实现了这个问题：shopping_basket.mzn。它非常先进，也许可以用作 Java 模型的模型。

对于Choco模型，你尝试过不同的搜索策略吗？不同的策略可能会更快。

顺便说一下，您可能想要查看的另一个 Java 约束编程求解器是JaCoP。