[OR-Tools 스터디] Constraint Optimization

Constraint optimization(or constraint programming(CP))은 문제가 임의의 constraint 관점에서 모델링 될 수 있다는 매우 큰 후보 집합 중에서 알맞은 해결책을 구분하고자 주어진 이름이다. 

CP문제는 많은 과학적, 공학적인 규율 속에서 일어났다. ("programming"이라는 단어는 약간 그릇된 명칭이며 이는 어떻게 "computer"가 "a person who computes"를 의미하는가와 유사한 흐름이다. 여기서 "Programming"은 컴퓨터 언어의 프로그래밍보다는 계획의 정렬을 의미한다. )

CP는 optimization(최적의 솔루션을 찾는 것)보다는 feasibility(가능한 솔루션을 찾는 것)에 기반을 두며 objective function보다는 constraint와 변수에 초점을 맞춘다.

사실 CP문제에 objective function이 없을 수도 있다. 목표는 단순히 문제에 constraint들을 추가함으로써 가능한 솔루션들의 매우 큰 집합들로부터 관리하기 쉬운 하위 집합으로 솔루션 집합을 좁히는 것일 수 있다

 

문제의 예시로 CP에 가장 적합한 것이 Employee Scheduling이다. 이 문제는 공장과 같은 연속적으로 계산하는 회사들이 그들의 직원들에 대해 매주 스케줄을 생셩해야할 때 발생한다. 이는 매우 단순한 예시이다 : 회사는 매일 3교대로 8시간씩 돌아가며 각 날마다 4명의 직원 중 3명은 다른 교대교에 배정하고 4번째 직원은 휴무이다. 이러한 작은 문제에도 가능한 스케줄의 수가 엄청나다. 각 날마다 가능한 직원 배정의 경우의 수는 4! = 4 * 3* 2* 1 = 24이며, 매주 가능한 스케줄의 수는 24^7이다. (이건 4.5 bilions...)

일반적으로 가능한 솔루션의 수를 줄이는 다른 constraint들도 있을 것이다. 예로 각 직원들은 최소 주당 일 수 이상을 근무한다. 이 CP method는 새 constraint를 추가할 때 실행 가능한 솔루션을 추적하기 때문에 실제 대규모 스케줄링 문제를 풀기 위한 강력한 툴이 된다.

 

CP는 널리 퍼져있고 매우 활동적인 커뮤니티를 가지고 있으며 전문적인 과학 학술지, 컨퍼런스, 그리고 다양한 해결 기술을 보유하고 있다.  CP는 planning, scheduling, 그리고 이질적인 constraint들과 함께 수많은 서로 다른 영역에서도 성공적으로 적용되고 있다.

 

Tools

google은 CP문제를 풀기 위해 몇 가지 방법을 제시한다.

• CP-SAT solver : SAT(satisfiability) method를 사용한 constraint programming solver
• Original CP solver : constraint programming solver

만약 문제가 lienar objective와 linear constraint로 모델될 수 있다면 linear probramming 문제를 가진 것으로 MPSolver를 고려해야 한다. (그러나, routing problem의 경우 선형 모델로 나타낼 수 있음에도 불구하고 전형적으로 vehicle routing library로 가장 잘 해결될 수 있다. )

 

Examples

다음 섹션에서는 CP-SAT solver를 묘사하고 있는데 이는 constraint programming에 대한 기본적인 OR-Tools solver이다.

(SAT는 satisfiability를 의미한다. solver는 CP method와 함께 SAT 문제를 푸는 기술을 사용한다. )

CP-SAT solver에 아주 적합한 스케줄링 문제의 예시들이다 :

• Employee Scheduling
• The Jop shop problem

고전적인 두 CP problem은 N-queens problem과 cryptarithmetic puzzles이다.

 

 

Reference :

https://developers.google.com/optimization/cp

제약조건 최적화  |  OR-Tools  |  Google Developers