标签: constraint-programming

我正在寻找一个可用的基于 GPU 的约束求解器来解决学校的受限时间表。约束问题是课程时间表。

http://docs.jboss.org/drools/release/latestFinal/optaplanner-docs/html_single/#curriculumCourse

JaCoP 是另一个约束求解器https://github.com/radsz/jacop

我正在尝试了解 MiniZincsgeost约束，这在 docs的打包约束部分中进行了描述。我正在尝试使用旋转来实现矩形的 2D 包装：所以我想将矩形放在给定长度和宽度的板上，但我很难理解预期的输入格式。

我有以下模型，我在其中读取了要放入nParts. nShapes是这些矩形可以采用的形状数。

include "globals.mzn";

int: nParts;
set of int: PARTS = 1..nParts;

int: nShapes; 
set of int: SHAPES = 1..nShapes;

int: plateLength;
int: plateWidth;

set of int: LEN = 0..plateLength;
set of int: WID = 0..plateWidth;

int: k = 2;
set of int: DIM = 1..k;

array[SHAPES,DIM] of int: rect_size;
array[SHAPES,DIM] of 0..0: rect_offset;
array[PARTS] of set of SHAPES: shape;

array[PARTS,DIM] of …

我正在努力理解 clp(Z) 和MiniKanren 中使用的另一个关系算术系统之间的功能差异。

特别是，clp(Z) 显然适用于有界域，而 Kiselyov等人。被描述为适用于无界字段。

我尝试使用与无穷大和不确定性相关的各种边缘情况，但除了 Kiselyov等人之外，我无法找到明显的差异。显然不支持区间和负数。

Kiselyov 系统的要点/优点是什么？主要是实现更简单，还是还有更多？

我有一个问题，我有一组具有给定生产能力的仓库，它们以给定的成本将一些产品发送给客户列表。我试图将发送产品的总成本降至最低，以便满足每个客户的需求。那部分是排序的。

现在我需要添加一个新的目标（或约束），我尝试以最低的成本满足所有客户的需求，同时尽可能使用最少的仓库数量。假设从 5 个仓库开始，如果问题是不可能的，则尝试 6、7、8 等，直到找到解决方案，如果我使用尽可能少的仓库数量来满足所有需求。

我如何使用 or-tool 约束编程模块来解决这个问题？甚至有可能吗？我仔细查看了文档，但找不到任何似乎符合这个想法的约束或函数。

我正在 Minizinc 上对巨大的数据集执行聚类，但我的计算时间很长，我正在尝试减少它。为此，我想指定为变量尝试可能值的顺序。

例如，一个变量v作为一个域1..5，但我知道4比3更有可能，3比2更有可能，等等。在这种情况下，有没有办法让我说我想先尝试 4，然后是 3，然后是 2，等等？

我有一组U用户和一组S服务器。我想最大化分配给服务器的用户数量，同时最小化使用的服务器数量（这意味着我有两个目标函数）。

每个用户都有一些需求w ，每个服务器的总容量为C。

求解器变量如下：

# x[i,j] = True if user u[j] is allocated to server s[i]
# x[i,j] = False otherwise

# y[i] = True if server s[i] is used to serve users
# y[i] = False otherwise

如前所述，我想最大化x[i,j]，同时最小化y[i]

限制如下：

• 容量约束：由于每台服务器i都有一定的容量，因此分配的j个用户不得超过该容量
• 邻近约束：只有位于服务器范围内的用户才能分配给它。一个用户可以位于多个服务器的重叠范围内
• 约束系列：确保每个用户最多分配到一台服务器。

使用这个库

from ortools.sat.python import cp_model

到目前为止我已经做了：

• 创建求解器变量（它们是布尔值）
• 创建约束
• 最大化 x[i,j] 变量
• 获取目标函数

例如，如果我有 10 个用户和 4 台服务器，则所有 10 个用户都分配到 4 台服务器中

我需要但未能完成的事情：

• 最大化x[i,j] …

我想最大化两个变量之间的差异:

:- use_module(library(clpfd)).
maximize(X) :- 
    X = [A,B],
    X ins 1..5,
    % I want to write a constraint to have maximum difference between A and B.

Minisat是一个约束编程/满意度工具,有一个版本的Minisat可以在浏览器中运行http://www.msoos.org/2013/09/minisat-in-your-browser/

如何用Minisat表达调度问题？是否有更高级别的语言编译成Minisat,这会让我表达它？

我的意思是解决像考试时间表这样的问题.http://docs.jboss.org/drools/release/6.1.0.Final/optaplanner-docs/html_single/#examination

我想对特定的数组元素执行简单的递增操作:

最小的不工作示例:

array[1..2] of var 0..1: a = [0, 0];

constraint forall (i in 1..2) (
    a[i] = a[i] + 1
);

output ["\(a)"];

solve satisfy;

这会产生minizinc输出

  WARNING: model inconsistency detected
  stack.mzn:3:
  in call 'forall'
  in array comprehension expression
    with i = 1
  stack.mzn:4:
  in binary '=' operator expression
=====UNSATISFIABLE=====
% stack.fzn:1: warning: model inconsistency detected before search.

为什么这是模型中的不一致 - 为什么我不能引用当前数组元素的旧值？还有其他方法可以将当前数组元素增加1吗？

我是限制性解决的新手,所以我希望这不是一个非常愚蠢的问题.

It is known that exact mathematical strategies such MILP are not efficient for large instances of the flexible job shop problem.

It is common to see in the literature MILP formulations for the FJS problem. I read that it is interesting to use the MILP model for experiments involving non-exact methods as metaheuristics (GA, FA, TS, etc) since it provides lower and upper bounds.

我还读到，当找到可行的解决方案比最优解决方案更重要时，应该选择CP。这是真实的说法吗？