제약조건 최적화

제약 조건 최적화 또는 제약 조건 프로그래밍(CP)은 임의의 제약 조건 측면에서 문제를 모델링할 수 있는 매우 많은 후보 세트 중에서 실행 가능한 솔루션을 식별하기 위해 지정된 이름입니다. CP 문제는 많은 과학 및 공학 분야에서 발생합니다. ('프로그래밍'이라는 단어는 약간 잘못된 명칭으로, '컴퓨터'가 한때 '컴퓨팅하는 사람'을 의미했던 것과 비슷합니다. 여기에서 '프로그래밍'은 컴퓨터 언어로 프로그래밍하지 않고 계획을 정리하는 것을 의미합니다.)

CP는 최적화 (최적 솔루션 찾기)가 아닌 실행 가능성 (실행 가능한 솔루션 찾기)을 기반으로 하며 목적 함수보다는 제약 조건과 변수에 중점을 둡니다. 실제로 CP 문제에는 목적 함수조차 없을 수도 있습니다. 문제에 제약 조건을 추가하여 가능한 솔루션의 매우 큰 집합을 더 관리하기 쉬운 하위 집합으로 좁히는 것이 목표일 수 있습니다.

CP에 적합한 문제의 예로는 직원 일정이 있습니다. 공장과 같이 지속적으로 운영되는 회사는 직원을 위해 주간 일정을 만들어야 하는 경우 문제가 발생합니다. 아주 간단한 예는 다음과 같습니다. 회사에서 하루에 3개의 8시간 교대를 운영하고 4명의 직원 중 3명을 매일 서로 다른 교대 근무에 할당하는 동시에 4일은 쉬게 합니다. 이처럼 작은 경우라도 가능한 일정의 수는 엄청납니다. 매일 4! = 4 * 3 * 2 * 1 = 24건의 가능한 직원 할당이 가능하므로 가능한 주간 일정의 수는 24^{70억 회, 45억 회 이상입니다.} 일반적으로 실행 가능한 솔루션 수를 줄이는 다른 제약조건이 있습니다. 예를 들어 각 직원이 주당 최소 일수 이상 일해야 합니다. CP 메서드는 새 제약 조건을 추가할 때 실행 가능한 상태로 유지되는 솔루션을 추적하므로 대규모 실제 스케줄링 문제를 해결하는 강력한 도구가 됩니다.

CP는 전 세계적으로 광범위하고 매우 활발한 커뮤니티를 보유하고 있으며 전담 과학 저널, 콘퍼런스, 다양한 해결 방법을 갖추고 있습니다. CP는 계획, 예약 및 이기종 제약조건이 있는 기타 수많은 도메인에 성공적으로 적용되었습니다.

도구

Google에서는 CP 문제를 해결하는 몇 가지 방법을 제공합니다.

• CP-SAT 솔버: SAT (만족도) 방법을 사용하는 제약 조건 프로그래밍 솔버입니다.
• 원본 CP 솔버: 라우팅 라이브러리에서 사용되는 제약 조건 프로그래밍 솔버입니다.

선형 목표와 선형 제약조건으로 문제를 모델링할 수 있으면 선형 프로그래밍 문제가 있는 것이므로 MPSolver를 고려해야 합니다. 그러나 라우팅 문제는 선형 모델로 표현할 수 있더라도 일반적으로 차량 라우팅 라이브러리를 사용하여 가장 잘 해결됩니다.

예

다음 섹션에서는 제약 조건 프로그래밍의 기본 OR-도구 솔버인 CP-SAT 솔버를 설명합니다. (SAT는 만족도를 의미하며, 문제 해결사는 CP 방법과 함께 SAT 문제를 해결하는 기술을 사용합니다.)

다음은 CP-SAT 솔버에 적합한 스케줄링 문제의 예입니다.

• 직원 일정 예약
• 취업정보 가게 문제

두 가지 기본적인 CP 문제는 N-퀸 문제와 암호화 퍼즐입니다.