如何使用约束规划来优化购物篮？
我有一个我想买的物品清单。这些商品由不同的商店提供，价格也不同。商店有单独的送货费用。我正在寻找最佳的购物策略（以及支持它的java库），以最低的总价购买所有商品。
示例：
- 商品 1 在商店 1 的售价为 100 美元，在商店 2 的售价为 111 美元。
- 商品 2 在 Shop1 的售价为 90 美元，在 Shop2 的售价为 85 美元。
- 商店 1 的配送费用：如果总订单 < 10 美元150 美元；否则为 0 美元
- Shop2 的送货费用：如果总订单 < 5 美元50 美元；否则为 0 美元
- 如果我在 Shop1 购买商品 1 和商品 2，总成本为 100 美元 + 90 美元 + 0 美元 = 190 美元。
- 如果我在 Shop2 购买商品 1 和商品 2，总成本为 111 美元 + 85 美元 + 0 美元 = 196 美元。
- 如果我在 Shop1 购买商品 1，在 Shop2 购买商品 2，则总成本为 $100 + $10 + $85 + $0 = 195.
如果我在 Shop1 订购 Item1 和 Item2，我会得到最低价格：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 分钟而没有找到解决方案。
问题
我应该如何表达我的约束才能使约束编程求解器可以解决这个问题？
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.
Example:
- 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
- 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.
I get the minimal price if I order Item1 and Item2 at Shop1: $190
What I tried so far
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:
- 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.
In cream I wasn't able to express the "if then" constraint for conditional shipping costs.
In choco these constraints exist, but even for 5 items and 10 shops the program was running for 10 minutes without finding a solution.
Question
How should I express my constraints to make this problem solvable for a constraint programming solver?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
我已经在 MiniZinc （一种高级约束编程语言）中实现了这个问题：shopping_basket.mzn。它非常先进，也许可以用作 Java 模型的模型。
对于Choco模型，你尝试过不同的搜索策略吗？不同的策略可能会更快。
顺便说一句，您可能想要查看的另一个 Java 约束编程求解器是 JaCoP。
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.
For the Choco model, have you tried different search strategies? A different strategy may be faster.
By the way, one other Java constraint programming solver you may want to check out is JaCoP.
您所问的本质上是k-knapsack问题。我喜欢的维基百科页面有丰富的解决方案资源。然而，这个问题是 NP 完全解决的，所以你可能希望做的是通过 模拟退火或其他形式用于搜索问题空间。
首先要记住的是，在约束问题中，您可能最终会花费大量时间来生成解决方案。在前面的示例中，虽然五个商品和十个商店看起来很小，但实际上会产生很大的问题空间（大约为 1e5，不包括条件定价的额外复杂性，这进一步加剧了问题）。
该问题的限制是您每件商品都买一件。目标是最低价格。我认为你所拥有的相当不错，尽管我不太确定第一点和第二点。
我会考虑将运费分摊到所购买商品的成本上而不是在进行计算时将其作为总值相加。
What you are asking about is in essence the k-knapsack problem. The wikipedia page I liked has a wealth of resources on solutions for it. The problem is however NP-Complete to solve in entirety, so what you may wish to do is look for a close to best solution through simulated annealing or other forms for search through the problem space.
The first thing to remember is that in constraint problems you will probably end up taking a good chunk of time to generate a solution. In your previous example, though five items and ten stores seems small it, in reality, generates a large problem space (on the order of 1e5 not including the added complication of the conditional pricing which further engrosses the problem).
The constraints on the problem are that you buy one of each item. The goal is minimal price. I think what you have is fairly good, though I'm not too sure about bullet points one and two.
I would consider amortizing the shipping over the cost of the items bought rather than adding it on as a total value when doing the calculations.
我不太确定这是一个 k-背包问题。该问题确实提到了“购物篮”一词，但没有具体说明任何给定货物的容量。如果您指定了最大装运尺寸，那么问题开始看起来更像是背包问题。
这个问题实际上只是一个基本的网络流量问题，涉及弧段上的运输成本和始发地的成本。因为您有一个明确的目标函数 - 最小化运输+产品成本，并且因为可能只有一种解决方案，CP 可能不是最好的方法。
考虑将其求解为线性规划问题：
Min：运输 + 产品成本
ST：运输的总产品 >= 需求（对于每种产品）
您可能需要为运输成本开发一些分段线性方程，但这应该不是问题。
I'm not too sure this is a k-knapsack problem. The question did mention the words "shopping baskets" but did not specify a capacity to any given shipment. If you specified a maximum shipment size, then the problem starts looking more like a knapsack problem.
The problem is really just a basic network flow problem with transporation costs on the arcs and costs at the origin. Because you have a clear objective function - minimize transportation + product cost and because there is likely to be only one solution, CP may not be the best approach.
Consider solving as linear programming problem:
Min: Transportation + Product Cost
ST: Total product shipped >= Demand (for each product)
You might need to develop some piecewise linear equations for the transportation cost, but that shouldn't be a problem.