如何使用约束规划来优化购物篮？

StackOverflow https://stackoverflow.com/questions/2822082

题

我有一个我想买的物品清单。这些商品由不同的商店提供，价格也不同。商店有单独的送货费用。我正在寻找最佳的购物策略（以及支持它的java库），以最低的总价购买所有商品。

例子：

  • 商品 1 在 Shop1 的售价为 100 美元，在 Shop2 的售价为 111 美元。
  • 商品 2 在 Shop1 的售价为 90 美元，在 Shop2 的售价为 85 美元。
  • 店铺1的配送费用：如果订单总额 < 150 美元，则为 10 美元；否则为 0 美元
  • Shop2的送货费用：如果订单总额 < 50 美元，则为 5 美元；否则为 0 美元
  • 如果我在 Shop1 购买商品 1 和商品 2，总成本为 100 美元 + 90 美元 + 0 美元 = 190 美元。
  • 如果我在 Shop2 购买商品 1 和商品 2，总成本为 111 美元 + 85 美元 + 0 美元 = 196 美元。
  • 如果我在 Shop1 购买 Item1，在 Shop2 购买 Item2，则总费用为 $100 + $10 + $85 + $0 = 195.

如果我在 Shop1 订购商品 1 和商品 2，我会得到最低价格：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 分钟而没有找到解决方案。

问题

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

有帮助吗？

解决方案

我已经实现了这个问题 迷你锌 （高级约束编程语言）： 购物篮.mzn. 。它非常先进，也许可以用作 Java 模型的模型。

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

顺便说一句，您可能想要查看的另一种 Java 约束编程求解器是 雅各布.

其他提示

你所问的本质上是 k-背包问题. 。我喜欢的维基百科页面有丰富的解决方案资源。然而，这个问题是 NP-Complete 来完全解决的，所以你可能希望做的是通过以下方式寻找接近最佳的解决方案 模拟退火 或用于搜索问题空间的其他形式。

首先要记住的是，在约束问题中，您可能最终会花费大量时间来生成解决方案。在您之前的示例中，虽然五个商品和十个商店看起来很小，但实际上会产生很大的问题空间（大约为 1e5，不包括条件定价的额外复杂性，这进一步加剧了问题）。

该问题的限制是您每件商品都买一件。目标是最低价格。我认为你所拥有的相当不错，尽管我不太确定第一点和第二点。

  • 每个价格“p xy”在域 (0, c) 中定义，其中 c 是该商店中商品的价格
  • 一行中只有一个价格不为零

    • 在进行计算时，我会考虑将运费分摊到所购买商品的成本上，而不是将其添加为总价值。

    我不太确定这是一个 k-背包问题。该问题确实提到了“购物篮”一词，但没有具体说明任何给定货物的容量。如果您指定了最大装运尺寸，那么问题开始看起来更像是背包问题。

    这个问题实际上只是一个基本的网络流量问题，涉及弧段上的运输成本和始发地的成本。因为您有一个明确的目标函数 - 最小化运输+产品成本，并且因为可能只有一种解决方案，CP 可能不是最好的方法。

    考虑将其求解为线性规划问题：

    分钟：运输+产品成本

    英石：已发货产品总数 >= 需求（针对每种产品）

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

    许可以下： CC-BY-SA 和 归因
    不隶属于 StackOverflow
    scroll top