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

Question

我有一份我想买的物品清单。这些商品由不同的商店和不同的价格提供。这些商店有单独的送货费用。我正在寻找一个最优的购物策略(以及一个支持它的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美元。
• 如果我在Shop1买Shop1，在Shop2买Item2，总成本是$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“都是在域(0，c)中定义的，其中c是本店商品的价格。
• 一条线上只有一种价格是非零的。
• 如果从一家商店购买了一件或多件商品，且价格之和低于限额，则在总成本中加上运输成本。
• 商店总成本是指商店内所有商品的价格之和。
• 总成本是所有商店总数的总和。

目标是“总成本”。我想把这件事降到最低。

在奶油中，我无法表达条件运输成本的“如果那样”约束。

在巧克力中，这些限制是存在的，但是即使对5件物品和10家商店来说，程序运行了10分钟也没有找到解决方案。

问题

我应该如何表达约束，以使约束编程解决程序可以解决这个问题？

Answer 1

我在MiniZinc (一种高级约束编程语言)：basket.mzn中实现了这个问题。它是相当向前的，也许可以用作Java模型的模型。

对于Choco模型，您是否尝试过不同的搜索策略？另一种策略可能会更快。

顺便说一句，您可能希望签出的另一个Java约束编程解决程序是JaCoP。

Answer 2

您所询问的本质上是K-背包问题。我喜欢的维基百科页面拥有丰富的解决方案资源。然而，问题是NP-完全解决整体，所以您可能希望做的是寻找一个接近最好的解决方案通过模拟退火或其他形式的搜索通过问题空间。

首先要记住的是，在约束问题中，您可能会花费大量时间来生成解决方案。在前面的示例中，虽然五个项目和十个商店看起来很小，但实际上它会产生一个很大的问题空间(在1e5的范围内，不包括进一步解决问题的附加复杂的条件定价)。

问题的制约因素是你买了每件东西中的一件。目标是最低的价格。我认为你所拥有的是相当好的，虽然我不太确定第一点和第二点。

每个价格"p“都是在域(0，c)中定义的，其中c是本店商品的价格。 一条线上只有一种价格是非零的。

在计算时，我会考虑将运费摊销到所购物品的费用上，而不是将其作为总价值计算。

Answer 3

我不太确定这是个背包问题。问题中确实提到了“购物篮”一词，但没有具体说明任何特定货物的运力。如果您指定了最大货件大小，那么问题开始看起来更像是背包问题。

这个问题实际上只是一个基本的网络流问题，传输成本在弧上，成本在原点。因为您有一个明确的目标函数--最小化运输+产品成本，并且由于可能只有一个解决方案，CP可能不是最好的方法。

考虑作为线性规划问题进行求解：

Min:运输+产品成本

ST:产品总发货量>=需求(每种产品)

你可能需要建立一些关于运输成本的分段线性方程，但这不应该是个问题。