Миницинк "не может определить нижнюю границу" для float

Question

У меня есть модель Minizinc, где у меня есть матрица расстояний:

array[1..n, 1..n] of var float: dist;

Который выведет ошибку Error: Gecode: Float::linear: Number out of limits, Если я попытаюсь свести к минимуму матрицу, например, с solve minimize sum(i,j in 1..n)(dist[i,j]); (на самом деле код более сложный). Нижняя граница мне понятна. Никакое значение в матрице расстояний не может быть ниже нуля. Формулировка ограничения с нижней границей, однако, не будет работать:

constraint forall(i,j in 1..n)(dist[i,j] >= 0.0);

Уменьшение домена будет работать. Но я не могу заранее сказать, какой будет верхняя граница домена (для приведенного ниже кода я взял очень большое число, которое в некоторых случаях может быть слишком маленьким):

array[1..n, 1..n] of var 0.0..1000000.0: dist;

Есть ли возможность определить только нижнюю границу?

Я использую Minizinc 2.2.1 с геокодом 6.0.1.

Answer 1

Вы получаете Error: Gecode: Float::linear: Number out of limits потому что для Gecode (и любого другого решателя CP) потребуется верхняя и нижняя граница для каждой переменной. В вашей цели вы суммируете переменные, каждая из которых варьируется от 0.0..1000000.0, Внутри MiniZinc создает переменную для этого выражения суммы, и домен этой переменной превышает внутренние границы Gecode.

Итак, я вижу два решения для решения этой проблемы:

1) Создайте целевую переменную самостоятельно и установите для нее верхнюю границу. Следующая модель работает для меня на MiniZinc 2.2.1 и Gecode 6.0.1:

int: n = 3;
array[1..n, 1..n] of var 0.0..100000.0: dist; 
% a new variable for the objective term with a lower and upper bound
var 0.0..1000000.0: total_distance;  

constraint forall(i,j in 1..n)(dist[i,j] >= 0.0);

constraint    % set the objective term
   total_distance = sum(i,j in 1..n)(dist[i,j]);

solve minimize total_distance;

2) Не используйте решатель CP, но используйте решатель MIP (Mixed Integer Programming). Они могут иметь дело с переменными, которые имеют бесконечные границы. MiniZinc поставляется с MIP-решателем CBC и без проблем решает следующую модель MiniZinc:

int: n = 3;
array[1..n, 1..n] of var float: dist;

constraint forall(i,j in 1..n)(dist[i,j] >= 0.0);

solve minimize sum(i,j in 1..n)(dist[i,j]);