标签: constraint-programming

我需要解决工作影响问题,我想找到优选的有效算法来解决这个问题.

假设有些工人可以做几种任务.我们还有一个必须每周完成的任务池.每项任务都需要一些时间.每项任务都必须由某人完成.每个工人必须每周工作N小时.

问题的第一部分似乎是约束编程算法的良好候选者.

但这里有复杂性:因为工人可以做不同的任务,他们也可能有偏好(或愿望).如果一个人想要满足每个人的所有愿望,那么问题就没有解决方案(限制太多).

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

算法必须公平(如果可以定义这个词),例如我应该能够添加一个约束,例如"试着满足每个人至少一个愿望".我不确定这个问题可以通过这里描述的Constraint Hierarchies方法解决:Constraint Herarchies.事实上,我不确定"公平"和愿望可以通过这类算法的有效约束来表达.

是否有约束编程专家给我一些建议？我是否需要使用一些启发式方法开发新的轮子而不是使用有效的CP算法？

谢谢 !

请你帮助优化这个工作的 MiniZinc 代码：

任务：有一个有 6 个时隙的会议。有 3 位演讲者参加了会议，每个人都可以在特定的时段使用。每个扬声器将出现预定数量的插槽。

目标：生成发言者最早完成的时间表。

示例：演讲者 A、B 和 C。演讲时长 = [1, 2, 1]

扬声器可用性：

+---+------+------+------+
|   | Sp.A | Sp.B | Sp.C |
+---+------+------+------+
| 1 |      | Busy |      |
| 2 | Busy | Busy | Busy |
| 3 | Busy | Busy |      |
| 4 |      |      |      |
| 5 |      |      | Busy |
| 6 | Busy | Busy |      |
+---+------+------+------+

链接到工作 …

我需要创建一个谓词:

applyConstraints(L)

这对L中的变量应用约束,使得L中没有两个连续元素都是奇数,甚至我怎么能这样做？固定尺寸L很简单,但可变尺寸L呢？我需要使用sicstus-prolog clpfd库来完成.

我是Prolog的新手,所以请保持温柔.

这是我的规则:

solve(X) :- A = B, A is (7 * (X - 2)), B is (3 * (X + 4)).

显然,这里的正确答案是6.5.如果我把它交给Prolog,它确认:

| ?- solve(6.5).

yes

但是,如果我让Prolog做脏工作,它会抛出一个错误:

| ?- solve(X).
uncaught exception: error(instantiation_error,(is)/2)

我完全承认,这里发生的一切都是由于我对Prolog的误解.有人可以向我解释我是如何让这个工作或为什么它不起作用？

我有一个矩形放置问题。我想要的是将大小为 x x y 的矩形放入另一个矩形而不重叠。我最终想要的是每个矩形的起点。

我为它制作了这部分代码，逻辑是它会沿着函数的高度和宽度累积检查 x 和 y 轴。但是，当我运行它时，它适用于一些实例，但不适用于其他实例。因此，我发布了一个特定实例，它在这里给出了重复点，以询问问题是什么以及可以进行哪些更改。

谢谢

constraint cumulative(start, x, y, height);
constraint cumulative(starty, y, x, width);

我是 CP 的新手，但我想解决我在大学遇到的问题。

我有一个 Minizinc 模型，它最大限度地减少了执行某些任务的已使用机器的数量。机器有一些资源，任务有资源需求。除了最小化这个数字，我试图最小化将任务分配给机器的成本（我有一个带有成本的数组）。有没有机会先最小化这个数字，然后在 Minizinc 中优化成本？

例如，我有 3 个任务和 2 台机器。每台机器都有足够的资源来分配 3 个任务，但我想分配成本较低的任务。

对不起我的英语，感谢您的帮助。如果有这样的需要，我会粘贴我的代码。

设置

我使用 google OR 工具作为约束编程求解器：

from ortools.sat.python import cp_model

我定义了以下 BoolVars

model = cp_model.CpModel()
a = model.NewBoolVar("a")
b = model.NewBoolVar("b")
c = model.NewBoolVar("c")
d = model.NewBoolVar("d")
e = model.NewBoolVar("e")
f = model.NewBoolVar("f")
g = model.NewBoolVar("g")

问题

我需要向模型添加复杂的布尔约束。就像是

(a || b) && (d || e) == g

如何将这样的复杂布尔约束添加到模型中？

PS：我无法立即在网上找到此信息，但根据我在此处的相关问题和此处另一个人的另一个相关问题上得到的答案找到了解决方案。我以问答的形式总结了我的发现，希望它们对某人有用。

我是数据挖掘领域的博士候选人，我必须使用 ORtools 创建一个全局约束以用于数据挖掘目的。

问题是互联网上缺乏关于使用 CP-Sat 创建自己的全局约束的文档，我不知道如何开始。

我在ECLiPSe下遇到了我的CSP问题.我想在我的密码中添加一个约束,要求TWO表示的数字可以被2整除.

[eclipse 11]: test(Xs).
instantiation fault in (_268{[1..4]}*100 + _200{[0..9]}*10 + _302{[0..9]}*1) mod 2#=0
Abort

谢谢你的帮助.

我的代码:

/*
          T W O                                           
   +  T H R E E      
   +  T H R E E                                       
      ---------                                      
      E I G H T                                     
*/

:- lib(fd).

myCsp(Xs):-
    Xs=[W,I,G,H,T,R,O,E],
    Xs::0..9,
    [C1,C2,C3,C4]::0..2,
    T #> 0,E #> 0,
    O + E + E #= C1*10 + T,
    W + E + E + C1 #= C2*10 + H,
    T + R + R + C2 #= C3*10 …

下面的程序（改编自http://www.hakank.org/minizinc/set_covering4b.mzn）是解决机密问题的方法（问题末尾提供了示例数据）。这可以正常运行。

int: num_alternatives;
int: num_objects;
par set of int: ALTERNATIVES = 1..num_alternatives;

% costs for the alternatives
array[ALTERNATIVES] of int: costs; 

% objects covered by the alternatives
array[ALTERNATIVES] of var set of 1..num_objects: a;

% decision variable: which alternative to choose
array[ALTERNATIVES] of var bool: x; 

% the objective to minimize
var int: z = sum(i in 1..num_alternatives) (x[i]*costs[i]); 
solve minimize z;

constraint
   forall(j in 1..num_objects) (
     sum(i in 1..num_alternatives) (x[i] * bool2int(j in a[i])) >= 1
   ) …