고객지원
기술문의
iLOG Solve에서 Domain Reduction Propagation에 대해서
- Hyun Jung Lee
- 2004.04.13
- 조회수 1,533
안녕하세요? KAIST에 박사과정학생 이현정입니다.
다름이 아니라, ILOG Solver에서 Domain Reduction Propagation을 이용해서 PRunning을 한다고 되어 있는데, 그렇다면 일부 노드에 대해서만 PRopagation을 한다는 의미인지, 아니면 Domain Reduciton후 Domain들간의 우선순위를 주어서 그 순서대로 Propagation해서 결국 전 노드에 대해서 Propagation을 하는 것인지 궁금해서 메일드립니다.
만약 구해진 해가 여러가지일 경우 어떤 해를 선택하개 되는지, 다시 말해 랜덤하게 선택하는지, 아니면 옵티멈을 찾는지, 찾는 다면 어떻게 찾는지 궁금합니다. 꼭 좀 회신 주시면 감사하겠습니다.
안녕히계세요.
이현정 드림
다름이 아니라, ILOG Solver에서 Domain Reduction Propagation을 이용해서 PRunning을 한다고 되어 있는데, 그렇다면 일부 노드에 대해서만 PRopagation을 한다는 의미인지, 아니면 Domain Reduciton후 Domain들간의 우선순위를 주어서 그 순서대로 Propagation해서 결국 전 노드에 대해서 Propagation을 하는 것인지 궁금해서 메일드립니다.
만약 구해진 해가 여러가지일 경우 어떤 해를 선택하개 되는지, 다시 말해 랜덤하게 선택하는지, 아니면 옵티멈을 찾는지, 찾는 다면 어떻게 찾는지 궁금합니다. 꼭 좀 회신 주시면 감사하겠습니다.
안녕히계세요.
이현정 드림
댓글 1
-
- 김태현2004-04-13
- 안녕하세요..
1번 질문에 대한 답변입니다.
우선, Domain Reduction과 Propagation에 대한 설명을 먼저 간단히 드리겠습니다.
Domain Reduction 이라는 것은 어떤제약이나, 다른 변수의 Domain이 변경될 경우, 해당 변수의 불필요한 Domain을 제거 하는 일련의 방법을 말합니다.
이렇게 Domain의 변경이 이루어 지면, 그 변수와 연관된 또 다른 변수들도 마찬가지로 Domain Reduction이 일어나게 되어있습니다.
이런 도미노 현상을 Propagation 이라고 합니다.
간단히 예를 들면,
X = [5..20], Y = [0..10] Z = [0..20]; 이런 integer 변수가 있다고,
제약1: X < Y,
제약2: X + Z = 10;이 있다면
X의 domain은 제약 1에 의해 [5..9]까지만 남게 되고, X 변수가 포함된 제약2에 영향의 미쳐, Z의 domain도 줄어드는 현상이 벌어집니다.
어떤제약을 먼저들어가든지 간에 Domain Reduction과 Propagation이 일어난 후의 결과는 같습니다.
즉, 우선 순위는 존재하지 않습니다.
물론 Solver 내부 적으로 Domain Reduction과 Propagation의 Level을 조절할수 있는 기능이 있습니다..
즉, 문제의 난이도가 어려운 경우는 Propagation을 많이 하면 도움이 되겠지만, 문제의 난이도가 쉬운경우는 굳이 Propagation Level을 높게 하지 않아도 되겠죠..
2번 질문에 대한 답변입니다.
초기해를 찾는지, 최적해를 찾는지의 여부에 따라 원하는 답을 얻을수 있습니다.
초기해를 찾는 경우, 랜덤하게 선택되는게 아니고, 아시다시피 DFS, DDS, LDS등의 여러 search 방법에 의해 초기해를 찾을수 있습니다.
물론, Solver 내에서 핸들링이 가능합니다.
최적해를 찾는 경우는 먼저 초기해를 찾고, 초기해가 Low Bound가 되어 초기해를 갱신하면서 최적해를 찾습니다. 이과정에서 불필요한 node는 Propagation의 의해 저절로 탐색을 하지 않습니다.
도움이 되었는지 모르겠네요..
목록
확인