이항 구속조건
Binary constraint이항 제약조건은 수학적 최적화에서 정확히 두 변수를 포함하는 제약조건이다.
예를 들어, n-Queens 문제를 고려해 보십시오. 목표는 n-by-n 체스판 위에 체스 여왕을 배치하여 여왕이 서로 공격할 수 없도록 하는 것입니다(수평, 수직 또는 대각선).따라서 공식적인 제약조건 집합은 "퀸 1은 퀸 2를 공격할 수 없다", "퀸 1은 퀸 3을 공격할 수 없다" 등이다.이 문제의 각 제약조건은 두 개별 여왕의 배치만을 고려한다는 점에서 이항이다.[1]
모든 제약 조건이 이진인 선형 프로그램은 강력한 다항식 시간 내에 해결할 수 있으며, 그 결과 더 일반적인 선형 프로그램에 대해서는 사실이 아닌 것으로 알려져 있다.[2]
참조
- ^ Marriott, Kim; Stuckey, Peter J. (1998), Programming with Constraints: An Introduction, MIT Press, p. 282, ISBN 9780262133418.
- ^ Megiddo, Nimrod (1983), "Towards a genuinely polynomial algorithm for linear programming", SIAM Journal on Computing, 12 (2): 347–353, CiteSeerX 10.1.1.76.5, doi:10.1137/0212022, MR 0697165.
