Максимальное количество последовательных значений (Minizinc)

Question

Я пытаюсь моделировать следующее ограничение в Minizinc:

Пусть S представляет собой массив переменных решения размера п. Я хочу, чтобы переменные решения принимали значение между 1-k, но существует максимальное значение «Cons_Max» для количества используемых последовательных значений.

Например, Cons_Max = 2, n = 8 и k = 15, то последовательность [1,2,4,5,7,8,10,11] является допустимой последовательностью, в то время как, например, [1,2,3,5,6,8,9,11] не является допустимой последовательностью, так как максимальное количество последовательных значений здесь равно 3 (1,2,3). Важно отметить, что последовательность [1,3,5,7,9,10,12,14] также действительна, так как значения не обязательно должны быть последовательными, но максимальное количество значений consectuive фиксируется на «Cons_Max» ».

Любые рекомендации по моделированию этого в Minizinc?

Answer 1

Вот модель с подходом, который, кажется, работает. Я также добавил два ограничения all_different и увеличился, поскольку они, вероятно, предполагаются в задаче.

include "globals.mzn"; 
int: n = 8; 
int: k = 15; 
int: Cons_Max = 2; 
% decision variables 
array[1..n] of var 1..k: x; 

constraint 
    forall(i in 1..n-Cons_Max) (
     x[i+Cons_Max]-x[i] > Cons_Max 
    ) 
; 

constraint 
    increasing(x) /\ 
    all_different(x) 
; 

%% test cases 
% constraint 
% % x = [1,2,4,5,7,8,10,11] % valid solution 
% % x = [1,3,5,7,9,10,12,14] % valid valid solution 

% % x = [1,2,3,5,6,8,9,11] % -> not valid solution (-> UNSAT) 
% ; 


solve satisfy; 
output ["x: \(x)\n" ]; 

Answer 2

Предположим, вы используете массив x для представления своей переменной принятия решения.

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

то вы можете моделировать ограничение, подобное этому.

constraint not exists (i in 1..n-1)(
         forall(j in i+1..min(n, i+Cons_Max)) 
          (x[j]=x[i]+1) 
        );