k ограничение последовательных целых чисел

Question

Как я могу сформулировать следующее ограничение в Программе ограничения? (Предпочтительно в гуроби или кометах).

S - массив целых чисел размера n. Набор целых чисел, который я могу использовать для заполнения массива, находится в диапазоне 1-k. Существует ограничение ci для каждого из целых чисел, которые могут быть использованы. ci обозначает минимальное количество последовательных целых чисел i.

Например, если c1 = 3, c2 = 2, то 1112211112111 не является допустимой последовательностью, так как должно быть два последовательных 2, тогда как 1112211122111 является допустимой последовательностью.

Answer 1

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

Однако, это прямое решение в MiniZinc, которое использует много овеществлений. Должно быть возможно перевести его на комету по крайней мере (я не думаю, что Гуроби поддерживает призывы).

Переменные решения (последовательности) находятся в массиве «x». Он также использует вспомогательный массив («начинается»), который содержит начальные позиции каждой последовательности; это облегчает рассуждение о последовательностях в «x». Количество последовательностей находится в «z» (например, для задач оптимизации).

В зависимости от размера x и других ограничений можно, вероятно, добавить больше (избыточных) ограничений на количество последовательностей, которые могут быть и т. Д. Однако это не делается.

Вот модель: http://www.hakank.org/minizinc/k_consecutive_integers.mzn

Это также показано ниже.

int: n; 
int: k; 

% number of consecutive integers for each integer 1..k 
array[1..k] of int: c; 

% decision variables 
array[1..n] of var 1..k: x; 

% starts[i] = 1 -> x[i] starts a new sequence 
% starts[i] = 0 -> x[i] is in a sequence 
array[1..n] of var 0..k: starts; 
% sum of sequences 
var 1..n: z = sum([bool2int(starts[i] > 0) | i in 1..n]); 

solve :: int_search(x, first_fail, indomain_min, complete) satisfy; 

constraint 
    forall(a in 1..n, b in 1..k) (
     (starts[a] = b) -> 
     (
      forall(d in 0..c[b]-1) (x[a+d] = b) 
      /\ 
      forall(d in 1..c[b]-1) (starts[a+d] = 0) 
      /\ 
      (if a > 1 then x[a-1] != b else true endif) % before 
      /\ 
      (if a <= n-c[b] then x[a+c[b]] != b else true endif) % after 
     ) 
) 
    /\ 
    % more on starts 
    starts[1] > 0 /\ 
    forall(i in 2..n) (
    starts[i] > 0 <-> (x[i]!=x[i-1]) 
) 
    /\ 
    forall(i in 1..n) (
    starts[i] > 0 -> x[i] = starts[i] 
) 
; 

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


% 
% data 
% 

%% From the question above: 
%% It's a unique solution. 
n = 13; 
k = 2; 
c = [3,2];