Как распространить множество доменов int во время преобразования mzn2fzn?

У меня есть следующее MiniZinc Пример кода:

include "globals.mzn";

var int: i;
array[-3..3] of var set of 1..10: x;
var set of 1..100: y;

constraint element(i, x, y);

solve satisfy;

output [
    show(i), "\n",
    show(x), "\n",
    show(y), "\n",
];

mzn2fzn Команда, выполненная со стандартной библиотекой, выводит следующее FlatZinc код:

var set of 1..10: X_INTRODUCED_0_;
var set of 1..10: X_INTRODUCED_1_;
var set of 1..10: X_INTRODUCED_2_;
var set of 1..10: X_INTRODUCED_3_;
var set of 1..10: X_INTRODUCED_4_;
var set of 1..10: X_INTRODUCED_5_;
var set of 1..10: X_INTRODUCED_6_;
var -3..3: i:: output_var;
var set of 1..10: y:: output_var;
var 1..7: X_INTRODUCED_9_ ::var_is_introduced :: is_defined_var;
array [1..7] of var set of int: x:: output_array([-3..3]) = [X_INTRODUCED_0_,X_INTRODUCED_1_,X_INTRODUCED_2_,X_INTRODUCED_3_,X_INTRODUCED_4_,X_INTRODUCED_5_,X_INTRODUCED_6_];
constraint array_var_set_element(X_INTRODUCED_9_,[X_INTRODUCED_0_,X_INTRODUCED_1_,X_INTRODUCED_2_,X_INTRODUCED_3_,X_INTRODUCED_4_,X_INTRODUCED_5_,X_INTRODUCED_6_],y):: defines_var(y);
constraint int_lin_eq([1,-1],[i,X_INTRODUCED_9_],-4):: defines_var(X_INTRODUCED_9_):: domain;
solve  satisfy;

Здесь обратите внимание, что изначально y был объявлен set of 1..100 в MiniZinc модель, но mzn2fzn правильно распространяет границы на элементы массива x на y, таким образом FlatZinc модель заявляет y быть set of 1..10,

Теперь я хочу настроить содержание element_set.mzn так что мой собственный предикат называется, когда element_set используется, поэтому я изменил его следующим образом:

predicate element_set(var int: i, array[int] of var set of int: x,
        var set of int: y) =
    min(index_set(x)) <= i /\ i <= max(index_set(x)) /\
    optimathsat_element_set(i, x, y, index_set(x));

predicate optimathsat_element_set(var int: i,
                                  array[int] of var set of int: x,
                                  var set of int: y,
                                  set of int: xdom);

Однако этот код не будет распространять границы на элементы массива. x на yитак FlatZinc файл имеет y до сих пор объявлен set of 1..100:

predicate optimathsat_element_set(var int: i,array [int] of var set of int: x,var set of int: y,set of int: xdom);
var set of 1..10: X_INTRODUCED_0_;
var set of 1..10: X_INTRODUCED_1_;
var set of 1..10: X_INTRODUCED_2_;
var set of 1..10: X_INTRODUCED_3_;
var set of 1..10: X_INTRODUCED_4_;
var set of 1..10: X_INTRODUCED_5_;
var set of 1..10: X_INTRODUCED_6_;
var -3..3: i:: output_var;
var set of 1..100: y:: output_var; %%% OFFENSIVE LINE %%%
array [1..7] of var set of int: x:: output_array([-3..3]) = [X_INTRODUCED_0_,X_INTRODUCED_1_,X_INTRODUCED_2_,X_INTRODUCED_3_,X_INTRODUCED_4_,X_INTRODUCED_5_,X_INTRODUCED_6_];
constraint optimathsat_element_set(i,x,y,-3..3);
solve  satisfy;

Я хотел бы знать, если кто-нибудь знает, какова правильная кодировка для распространения домена x над y, Мне удалось сделать это для других element_T ограничения, но я не могу найти элегантное решение для element_setпотому что я не могу найти подходящих встроенных функций для этого.

Другими словами, я хотел бы получить

var set of 1..10: y:: output_var;

вместо

var set of 1..100: y:: output_var;

Как бы я это сделал?

Источник

2 ответа

Решение

Семья element/element_T предикаты внутренне отображаются на семью element/element_T функции.

В MiniZinc версия 2.0.2 и выше, эти функции отображаются на следующие предикаты:

% This file contains redefinitions of standard builtins for version 2.0.2
% that can be overridden by solvers.

...    

predicate array_var_bool_element_nonshifted(var int: idx, array[int] of var bool: x, var bool: c) =
  array_var_bool_element((idx-(min(index_set(x))-1))::domain,array1d(x),c);

predicate array_var_int_element_nonshifted(var int: idx, array[int] of var int: x, var int: c) =
  array_var_int_element((idx-(min(index_set(x))-1))::domain,array1d(x),c);

predicate array_var_float_element_nonshifted(var int: idx, array[int] of var float: x, var float: c) =
  array_var_float_element((idx-(min(index_set(x))-1))::domain,array1d(x),c);

predicate array_var_set_element_nonshifted(var int: idx, array[int] of var set of int: x, var set of int: c) =
  array_var_set_element((idx-(min(index_set(x))-1))::domain,array1d(x),c);

Лучшее решение - переопределить эти предикаты вместо того, чтобы возиться с element/element_T из них.

Источник

Хотя это немного сложно найти, домен индекса фактически распространяется в определении MiniZinc element функция. Определение находится в builtins.mzn, а именно так:

function var set of int: element(var int: idx, array[int] of var set of int: x) =
  if mzn_in_root_context(idx) then let {
    constraint idx in index_set(x)
  } in element_t(idx,x)
  elseif (has_bounds(idx) /\ lb(idx) >= min(index_set(x)) /\ ub(idx) <= max(index_set(x))) then
    element_t(idx,x)
  else let {
    constraint idx in index_set(x)
  } in element_mt(idx,x)
  endif;

Вы можете видеть, что ограничение вашего элемента оценивается как находящееся в первой ветви if-then. Более важный вопрос, почему ограничение элемента так сложно. Ответ в том, что это связано с неопределенностью.

Скажем, у нас есть array[1..3] of int: aтогда что a[4] оценить? Казалось бы, легко сделать такую ​​вещь незаконной, но как насчет выражения? a[i] > 5 \/ i > 10, Это может быть хорошо продуманная модель, которая должна быть удовлетворительной для i = 11, В MiniZinc эти недопустимые значения называются неопределенными и всплывают до ближайшего логического выражения, которое должно быть false,

Теперь, когда мы оглядываемся назад на ограничение элемента, мы можем понять, что в корневом контексте, как в вашем примере, мы можем просто применить домен и использовать "безопасное" ограничение элемента. Аналогично, если границы индекса меньше границ массива, мы можем использовать ограничение "safe" для элемента, но если границы больше, мы используем ограничение "unsafe" для элемента и убедитесь, что true возвращается только когда значение определено.

Я бы предложил вам использовать аналогичный подход или переопределить предикаты поздней стадии. (Можно переопределить array_var_set_element вместо)

Более подробную информацию о неопределенности в MiniZinc можно найти в следующей статье:

Фриш, AM & Stuckey, PJ (2009). Правильное обращение с неопределенностью в ограниченных языках. СР, 5732, 367-382.

MiniZinc использует реляционную семантику.

Источник
Другие вопросы по тегам