k 연속 정수 제약

Question

제약 프로그래밍에서 다음 제약 조건을 어떻게 나타낼 수 있습니까? (Gurobi 또는 Comet에서 선호).

S는 크기 n의 정수 배열입니다. 배열을 채우는 데 사용할 수있는 정수 집합은 1-k 범위에 있습니다. 사용할 수있는 각각의 정수에는 ci의 제약 조건이 있습니다. ci은 연속적인 정수의 최소 수인 i을 나타냅니다.

예를 들어 c1 = 3, c2 = 2 인 경우 1112211122111은 유효한 시퀀스 인 반면 2 개의 연속적인 2가 있어야하므로 1112211112111은 유효한 시퀀스가 ​​아닙니다.

Answer 1

아마도 가장 일반적인 방법은 정규 구속 조건 (Comet의 자동 연산)을 사용하는 것입니다.

그러나 여기에는 많은 정량법을 사용하는 MiniZinc의 간단한 해결책이 있습니다. 최소한 Comet에게 번역 할 수 있어야합니다 (저는 Gurobi를지지한다고 생각하지 않습니다).

결정 변수 (시퀀스)는 배열 "x"에 있습니다. 또한 각 시퀀스의 시작 위치를 포함하는 도우미 배열 ("starts")을 사용합니다. 이렇게하면 "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];