如何使用约束编程优化购物篮？
我有一份我想买的物品清单。 这些物品由不同的商店和不同的价格提供。 商店有个人送货费用。 我正在寻找最优购物策略（以及支持它的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分钟而没有找到解决方案。
题
我应该如何表达我的约束以使约束编程求解器能够解决这个问题？
我在MiniZinc （一种高级约束编程语言）中实现了这个问题： shopping_basket.mzn 。 它非常前瞻，可能可以用作Java模型的模型。
对于Choco模型，您尝试过不同的搜索策略吗？ 不同的策略可能更快。
顺便说一句，您可能想要检查的另一个Java约束编程解算器是JaCoP 。
你所询问的实质上是k-背包问题 。 我喜欢的维基百科页面有很多关于解决方案的资源。 然而，问题是NP-Complete要完全解决，所以您可能希望通过模拟退火或其他forms寻找接近最佳的解决方案来搜索问题空间。
首先要记住的是，在约束问题中，您可能最终会花费大量时间来生成解决方案。 在您之前的示例中，虽然五个项目和十个商店看起来很小，但实际上，它会产生一个大的问题空间（大约1e5，不包括条件定价的额外复杂性，这进一步影响了问题）。
问题的限制是你购买每件物品中的一件。 目标是最低价格。 我认为你所拥有的是相当不错的，尽管我对第一点和第二点都不太确定。
每个价格“p xy”在域（0，c）中定义，其中c是该商店中商品的价格 一行中只有一个价格应该是非零
我会考虑将运费摊销超过所购物品的成本，而不是在计算时将其作为总价值加上。
我不太确定这是一个k-背包问题。 这个问题确实提到了“购物篮”这个词，但未指明任何特定货物的容量。 如果您指定了最大出货量，那么问题就会开始变得更像是背包问题。
问题实际上只是一个基本的网络流量问题，其中弧线的转换成本和原点的成本。 因为您有一个明确的目标函数 – 最小化运输和产品成本，并且因为可能只有一个解决方案，CP可能不是最好的方法。
考虑解决线性规划问题：
最低：运输+产品成本
ST：出货总量> =需求（每种产品）
您可能需要为运输成本开发一些分段线性方程，但这应该不是问题。