带有可选变量的搜索策略

Question

我正在 Minizinc 中实现一个简单的模型，以在一系列时隙中安排具有不同优先级和持续时间的任务，但并非所有任务都可以安排，所以有些任务会被排除在外，我正在尝试最大化计划任务的优先级总和。

我有一个工作版本，其中任务在变量数组中定义，非计划任务的时间为 0。约束有几个 where 子句仅考虑计划任务 (when[i]> 0).默认搜索策略非常慢，所以我将其更改为另一种效果更好的策略，使用 Gecode 作为求解器。

现在我正在使用可选变量实现一个不同的版本，以摆脱 where 子句，以检查是否有任何改进。但是，在使用 opt var.

时，我似乎无法定义搜索策略 int_search()

有什么办法吗？

工作模型如下（我想尝试的搜索策略的solve子句被注释掉了）：

int: numtasks=100;
int: numslots=100;

set of int: TASK=1..numtasks;
set of int: SLOT=1..numslots;
array[TASK] of var opt 1..numslots: when;
array[TASK] of int: duration = [(i mod 3)+1 | i in TASK];
array[TASK] of int: prio = [(i mod 10)+1 | i in TASK]; 

include "globals.mzn";
constraint disjunctive(when, duration);

var int: obj = sum(i in TASK where not absent(when[i]))(prio[i]);
%solve ::int_search(when, input_order, indomain_random, complete) maximize obj;
solve maximize obj;

output [show(obj)," ",show(when)];

Answer 1

我不确定这是否是最好的方法，但可以在 "int_search" 中使用 "occurs()" 进行测试，即

 solve ::int_search([occurs(when[t]) | t in TASK], input_order, indomain_random, complete) maximize obj;

此外，我建议您使用 input_order/indomain_random 以外的一些其他标签进行测试，例如first_fail/indomain_split等

/哈坎

带有可选变量的搜索策略

Search strategy with optional variables

constraint-programming

minizinc

gecode