代码之家 › 专栏 › 技术社区 › Max Power

为什么这两行的变化打破了这个迷你锌套封面计划?

set-cover operations-research minizinc constraint-programming

0

Max Power · 技术社区 · 5 年前

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
   )
;

output
[
  "x: " ++ show(x) ++ "\n" ++ 
  "a: " ++ show(a) ++ "\n"
];

a 上述定义:

array[ALTERNATIVES] of var set of 1..num_objects: a;

这两条线在我看来是等价的:

var set of int: OBJECTS = 1..num_objects;  
array[ALTERNATIVES] of OBJECTS: a;

这让我很困惑。我改变了什么?在每种情况下 一 是整数集的数组。类型实例是 var set of int 在每种情况下,但是第二个抛出一个错误,而第一个由于某种原因没有?

下面是一些可以放在.mzn代码文件底部的数据,以生成一个自包含、可运行的示例:

% data
num_alternatives =  10;
costs = [ 19, 16, 18, 13, 15, 19, 15, 17, 16, 15];
num_objects = 8;

% the alternatives and the objects they contain
a = [
  {1,6},
  {2,6,8},
  {1,4,7},
  {2,3,5},
  {2,5},
  {2,3},
  {2,3,4},
  {4,5,8},
  {3,6,8},
  {1,6,7}
];

0 回复 | 直到 5 年前

1

5

Axel Kemper 5 年前

你可以这样写:

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

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

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

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

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

constraint
   forall(j in OBJECTS) (
     sum(i in ALTERNATIVES) (x[i] * (j in a[i])) >= 1
   )
;

output
[
  "x: " ++ show(x) ++ "\n" ++ 
  "a: " ++ show(a) ++ "\n"
];

在你的实验中

var set of int: OBJECTS = 1..num_objects;  
array[ALTERNATIVES] of OBJECTS: a;

a array 范围内的整数 1..num_objects 但你打算 数组 在这个范围内的整数集合。