각 변수가 취할 수있는 모든 값을 확인하십시오.

Question

변수와 변수 사이에 선형 제약 조건 목록이 있습니다. 각 변수에 대해 유효한 값의 시작 목록이 포함 된 집합이 있습니다. Minizinc를 사용하여 어떻게 시작 값의 집합을 제약 조건을 만족시킬 수있는 값으로 줄일 수 있습니까? 내가 xy에 대한 모든 솔루션 solve satisfy 항목 및 인쇄 이것을 실행하면 (수평 라인이 제거 포함)

array[1..2] of var int: xy; 
array[1..2] of set of int: xyvalid = [ {1, 5, 7}, 0..9 ]; 

constraint forall(i in 1..2)(xy[i] in xyvalid[i]); 
constraint xy[1] + xy[2] = 7; 

, 내가 얻을 :

간단한 예를 들어 내가 달성하기 위해 노력하고있어 설명하기

내가을 원하는 무엇

[1, 6] 
[5, 2] 
[4, 3] 
[3, 4] 

어떻게 든이 경우 [ {1, 3, 4, 5}, {2, 3, 4, 6} ] 동일 것이라고 xypossible를 호출, VAR 세트의 배열을 얻을 수 있습니다. xypossible[1]의 가능한 모든 값에 대해 유효한 솔루션을 생성하는 xypossible[2]에 값이 있음을 확인하고 그 반대의 경우를 확인한 다음 모든 세트의 전체 카디널리티를 최대화하도록 해결하는 일련의 제약 조건을 정의 할 수 있습니다. xypossible하지만 내 실제 데이터는 수십 개의 선형 제약이있는 수백 개의 변수로 잠재적으로 코드를 작성할 때 추악하고 실행하기가 어려울 때 유용합니다.

모델로 할 수있는 방법이 없다면 솔버가 자체 작업을 수행하는 과정에서 유효한 값을 식별 한 결과로 정보를 캡처 할 수있는 방법이 있습니까?

Answer 1

xy [1]의 가능한 값은 {1,5,7}이라고 명시되어 있기 때문에 결과가 [{1,5,7}, {0,2,6}이어야 함을 의미한다고 가정합니다 "xyvalid"배열에; 0, 2 및 6은 1,5에 추가 할 때 7을 산출하는 유일한 값이며, 그렇지 않은 경우, 뭔가를 놓쳤을 것입니다. ...

다음은 원하는 방식으로 작동하는 모델입니다. 최상의 솔루션을 골라 내려면 최대한의 목표가 필요합니다.

z = array1d(1..2 ,[{1,5,7}, {0,2,6}]); 
    ---------- 
    z = array1d(1..2 ,[{1,7}, {0,6}]); 
    ---------- 
    z = array1d(1..2 ,[{5,7}, {0,2}]); 
    ---------- 
    z = array1d(1..2 ,[7..7, 0..0]); 
    ---------- 
    z = array1d(1..2 ,[{1,5}, {2,6}]); 
    ---------- 
    z = array1d(1..2 ,[1..1, 6..6]); 
    ---------- 
    z = array1d(1..2 ,[5..5, 2..2]); 
    ---------- 
    z = array1d(1..2 ,[{}, {}]); 
    ---------- 
    ========== 

(이들 중 일부는 몇 가지 추가적인 제약 조건에 의해 제거 될 수 있었다)

:

% the domains of the two variables 
array[1..2] of set of int: xyvalid = [ {1, 5, 7}, 0..9 ]; 

% the result sets 
array[1..2] of var set of 0..9: z; 

% ensure that the largest solution is picked 
solve maximize card(z[1]) + card(z[2]); 

constraint 
    % get the domains of each variable set 
    forall(i in 1..2)(z[i] subset xyvalid[i]) /\ 
    % ensure that for all valid values in z[1] are in z[2] given 
    % that j + k = 7 
    forall(j in z[1]) (
     exists(k in z[2]) (j + k = 7) 
    ) 
    /\ 
    % and ensure that all valid values in z[2] are in z[1] 
    forall(k in z[2]) (
     exists(j in z[1]) (j + k = 7) 
    ) 
    ; 

결과는 최대화 목적없이 다음

z = array1d(1..2 ,[{1,5,7}, {0,2,6}]); 

이며, 8 해결책이있을 것

내 개인적인 접근 방식은 아마도 귀하의 변종을 사용하여 possi를 수집했을 것입니다 일부 외부 프로그램을 통해 값을 구할 수 있습니다.

참고 : 일부 CP 시스템에서는 레이블링 전에 올바른 변수 값을 찾기 위해 의사 결정 변수의 도메인을 인쇄 할 수 있습니다. 그러나 MiniZinc에는이 기능이 없습니다. 그리고 나는 그것을 놓친다.

참고 2 : 결정 변수의 도메인을 제공하는 dom() 함수를 테스트했지만 제대로 작동하지 못했습니다.