问题标签 [constraint-programming]

编辑：这个谜题也被称为“爱因斯坦之谜”

谁拥有 Zebra（您可以在此处尝试在线版本）是一组经典难题的示例，我敢打赌 Stack Overflow 上的大多数人都可以用笔和纸解决它。但是程序化解决方案会是什么样子？

根据下面列出的线索...

• 有五间房子。
• 每个房子都有自己独特的颜色。
• 所有房主都是不同国籍的。
• 他们都有不同的宠物。
• 他们都喝不同的饮料。
• 他们都抽不同的香烟。
• 英国人住在红房子里。
• 瑞典人有一条狗。
• 丹麦人喝茶。
• 绿房子在白房子的左边。
• 他们在温室里喝咖啡。
• 抽 Pall Mall 的人有鸟。
• 在黄色的房子里，他们抽登喜路。
• 在中间房子里，他们喝牛奶。
• 挪威人住在第一间房子里。
• 抽 Blend 的男人和猫一起住在房子旁边的房子里。
• 在他们有一匹马的房子旁边的房子里，他们抽登喜路。
• 抽蓝大师的人喝啤酒。
• 德国人抽王子烟。
• 挪威人住在蓝屋旁边。
• 他们在抽Blend的房子旁边的房子里喝水。

...谁拥有斑马？

寻找开始使用约束编程的技巧、教程、书籍和其他资源。

我需要解决一个工作做作的问题，我想找到最好的有效算法来解决这个问题。

假设有一些工人可以完成多种任务。我们还有一个每周必须完成的任务池。每个任务都需要一些时间。每项任务都必须由某人承担。每个工人每周必须工作 N 到 P 小时。

问题的第一部分似乎是约束规划算法的一个很好的候选者。

但这里是复杂的：因为工人可以做不同的任务，他们也可能有偏好（或愿望）。如果一个人想要满足所有人的所有愿望，那么问题就没有解决方案（约束太多）。

所以我需要一个算法来解决这个问题。如果完美的轮子已经存在，我不想重新发明轮子。

该算法必须是公平的（如果可以定义这个词），例如，我应该能够添加一个约束，例如“尝试满足每个人至少一个愿望”。我不确定这个问题是否可以通过此处描述的约束层次结构方法来解决：约束层次结构。事实上，我不确定“公平”和愿望是否可以通过此类算法的有效约束来表达。

有约束规划专家给我一些建议吗？我是否需要开发一个带有一些启发式的新轮子而不是使用高效的 CP 算法？

谢谢 ！

我必须使用Java Constraints Library解决CSP逻辑问题。现在我已经设法表示了问题的一些约束，其中大多数基于“等于”和“不等于”二元约束。我的疑问是，如何表示基于加法的约束？例子：

• variable1 属于 DomainA
• 变量2属于域B
• variable3 属于 DomainA
• 变量4属于域B

现在的约束：

• variable1 和 variable2 之和大于 variable3 和 variable4 之和。

观察：这些变量代表金钱，所以可以相加。

我正在开发一个交互式作业调度应用程序。给定一组具有相应容量/可用性配置文件的资源，一组要在这些资源上执行的作业，以及一组确定作业顺序和作业的最早/最晚开始/结束时间的约束，我想让用户手动移动周围的工作。本质上，我希望用户能够“抓住”工作网络的一个节点并及时向前/向后拖动而不违反任何约束。

该图显示了一个简单的示例配置。最后的三角形作业表示所有作业的最晚完成时间，作业之间的连接线对作业施加顺序，灰色/绿色条表示资源可用性和负载。

您可以拖动任何作业来压缩计划。请注意，由于容量配置文件不同，作业的长度会发生变化。

我已经实现了一个有点工作的临时算法。但是，仍然存在失败并违反某些约束的情况。然而，由于工作车间调度是一个研究得很好的领域，有很多算法和启发式方法可以找到一般 NP-hard 问题的最佳（或相当好的）解决方案 - 我认为解决方案应该存在于我更容易的子集。我研究了约束编程主题，甚至研究了基于物理的解决方案（通过静态关节连接的刚体），但到目前为止找不到任何合适的东西。对我有任何指示/提示/提示/搜索关键字吗？

我正在开发一个 Java 应用程序，它需要做一些复杂的逻辑规则推导作为其功能的一部分。我想用 Prolog 或其他一些逻辑/约束编程语言而不是 Java 来编写我的逻辑推导，因为我相信生成的代码会更简单且更易于维护。

我在 Prolog 上搜索了嵌入式 Java 实现，并找到了它们的数量，每个都只有很少的文档。我的（适度的）选择标准是：

• 应该可以嵌入到 Java 中（例如可以与我的 java 包捆绑在一起，而不需要在外部程序上进行任何本机安装）
• 从 Java 中使用的简单接口（用于启动扣除、检查结果和添加规则）
• 至少提供一些关于如何使用它的示例
• 不一定必须是 Prolog，但具有上述标准的其他逻辑/约束编程语言也可以满足我的需求。

我有哪些选择，它们的优点和缺点是什么？

我正在尝试从Coin-Or的Cgl（切割生成库）中提取 Cgl Gomory 切割，以下是我用来提取切割的代码 -

其中 sym 是 OsiSymSolverInterface（Symphony 的 OsiSolverInterface）的一个实例。不幸的是，就我能够使用 gdb 确定的情况而言，代码在方法内部某处的 generateCuts 处出现段错误。

CglProbing 切割的提取同样在 CglProbing 类的 generateCuts 方法中再次出现段错误。

所有其他削减似乎工作正常。

如果有人可以对此有所了解甚至更好，使用这些剪辑或某种教程发布/链接到示例文件，那就太好了。如果有一个示例/教程用于从 SCIP 等其他求解器中提取切口而不是 Coin-OR，那也可以。

谢谢

在阅读约束逻辑编程时，我不禁注意到与 SQL 编程的明显关系。SQL 是“约束逻辑编程”的一个例子吗？

我正在尝试使用 Microsoft Solver Foundation 2 来解决一个相当复杂的情况，但是即使我尽可能地简化模型，我也会遇到 UnsupportedModelException 。
有谁知道我做错了什么？
以下是重现问题行为所需的最少示例。

请考虑我的实际模型在完成后应该包括一些约束，形式为 a a + b a <= someValue，所以如果我最终愿意做的事情不受支持，请提前告诉我。如果是这种情况，我也会感谢其他一些具有我可以使用的 .NET 友好界面的求解器的建议（请仅使用知名的商业软件包）。

提前致谢

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

例子：

• 商品 1 在 Shop1 的售价为 100 美元，在 Shop2 的售价为 111 美元。
• Item2 在 Shop1 的售价为 90 美元，在 Shop2 的售价为 85 美元。
• Shop1的运费：如果总订单<$150，则为$10；$0 否则
• Shop2的运费：如果总订单<50美元，则为5美元；$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 订购商品 1 和商品 2，我将获得最低价格：190 美元

到目前为止我尝试了什么

在此之前我问了另一个问题，这使我进入了约束编程领域。我看了cream和choco，但我不知道如何创建一个模型来解决我的问题。

我的想法是定义这些约束：

• 每个价格“p xy ”在域 (0, c) 中定义，其中c是该商店中商品的价格
• 一行中只有一个价格不应该为零
• 如果从一家商店购买一件或多件商品并且价格总和低于限额，则将运费添加到总成本中
• 商店总成本是商店中所有商品价格的总和
• 总成本是所有商店总和的总和

目标是“总成本”。我想尽量减少这种情况。

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

在 choco 中存在这些限制，但即使对于 5 件商品和 10 家商店，该程序也运行了 10 分钟而没有找到解决方案。

问题

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