제약 조건 합성 그래프

Constraint composite graph

제약 조건 복합 그래프는 가중 제약 조건 만족도 문제로 제기되는 주어진 조합 최적화 문제와 연관된 노드 가중치 비방향 그래프다.사티쉬 쿠마르 티타마라할리(T. K. Satish Kumarhalli, T. K. Satish Kumar)가 개발하고 소개한 제약 복합 그래프의 아이디어는 가중 제약 만족도 문제에서 "구조"를 이용하기 위한 다양한 접근법을 통일하기 위한 큰 진전이다.[1][2]

가중 구속조건 만족도 문제(WCSP)는 제약조건 만족도 문제의 일반화로서, 제약조건이 더 이상 "강성"이 아니라 튜플과 관련된 비-부정 비용을 명시하기 위해 확장된다.그런 다음, 총 비용이 최소화되도록 각 도메인에서 모든 변수에 대한 값 할당을 찾는 것이 목표다.가중 제약 만족도 문제는 인공지능과 컴퓨터 과학에서 무수한 응용 분야를 찾아낸다.그것들은 마르코프 무작위 필드(통계 및 신호 처리)와 에너지 최소화 문제(물리학)라고도 다양하게 언급된다.

가중 구속조건 만족도 문제는 일반적으로 해결하기 어려운 NP이지만, 가중 구속조건이 특정한 종류의 숫자 구조를 나타내는 다항식 시간에 여러 하위 분류들을 해결할 수 있다.또한 변수 위에 제약 조건이 배치되는 방법을 분석하여 추적 가능한 하위 분류도 식별할 수 있다.특히 가중 제약조건 만족 문제는 시간 지수적으로만 변수 상호작용 그래프(기형 네트워크)의 트리 너비에서만 해결할 수 있다.그러나 제약 네트워크의 주요 단점은 가중 제약조건의 수치 구조를 활용하기 위한 계산적 프레임워크를 제공하지 않는다는 것이다.

제약 조건 네트워크와 달리 제약 조건 복합 그래프는 가중 제약 조건의 수치 구조뿐만 아니라 변수 상호작용의 그래픽 구조 모두를 나타내기 위한 통일된 프레임워크를 제공한다.간단한 다항식 시간 절차를 사용하여 구성할 수 있으며, 주어진 가중 구속조건 만족도 문제는 관련된 구속조건 복합 그래프에 대한 최소 가중 정점 표지의 계산 문제로 축소할 수 있다.제약 조건 복합 그래프의 "하이브리드" 계산 속성은 다음의 두 가지 중요한 결과에 반영된다.

(결과 1) 주어진 가중 제약조건 만족도 문제에 대한 제약조건 복합 그래프는 연관된 제약조건 네트워크와 트리 너비가 동일하다.

(결과 2) 가중 구속조건의 수치 구조로 인해 추적 가능한 가중 구속조건 만족도 문제의 하위 분류에는 본질적으로 양분적인 제약조건 복합 그래프가 있다.

결과 1은 제약 조건 복합 그래프를 사용하여 변수 상호작용의 그래픽 구조를 캡처할 수 있음을 보여준다(어떤 그래프에 대한 최소 가중 정점 커버는 해당 그래프의 트리 너비에서만 시간 지수적으로 계산될 수 있기 때문이다).결과 2는 제약 조건 복합 그래프를 사용하여 가중 제약 조건의 수치 구조를 포착할 수도 있음을 보여준다(최소 가중 정점 커버는 초당적 그래프의 다항 시간에서 계산할 수 있기 때문이다).

경험적으로 WCSP를 풀 때는 WCSP의 제약조건 복합 그래프에 직접 적용하는 것보다 메시지 전달 알고리즘과 정수 선형 프로그래밍을 적용하는 것이 더 유리하다는 것이 밝혀졌다.[3][4]

참조

  1. ^ Kumar, T.K.S. (2008). "A Framework for Hybrid Tractability Results in Boolean Weighted Constraint Satisfaction Problems". Proceedings of the Fourteenth International Conference on Principles and Practice of Constraint Programming (CP). Lecture Notes in Computer Science book series. Vol. 5202. pp. 282–297. doi:10.1007/978-3-540-85958-1_19. ISBN 978-3-540-85958-1.
  2. ^ Kumar, T.K.S. (2008). "Lifting Techniques for Weighted Constraint Satisfaction Problems" (PDF). Proceedings of the Tenth International Symposium on Artificial Intelligence and Mathematics (ISAIM'2008).
  3. ^ Xu, Hong; Kumar, T. K. Satish; Koenig, Sven (2017). "The Nemhauser-Trotter reduction and lifted message passing for the weighted CSP". Proceedings of the 14th International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming (CPAIOR). Lecture Notes in Computer Science book series. Vol. 10335. Springer. pp. 387–402. doi:10.1007/978-3-319-59776-8_31. ISBN 978-3-319-59776-8.
  4. ^ Xu, Hong; Koenig, Sven; Kumar, T. K. Satish (2017). "A constraint composite graph-based ILP encoding of the Boolean weighted CSP". Proceedings of the 23rd International Conference on Principles and Practice of Constraint Programming (CP). Lecture Notes in Computer Science book series. Vol. 10416. Springer. pp. 630–8. doi:10.1007/978-3-319-66158-2_40. ISBN 978-3-319-66158-2.