Mathematical Programming (MP)과 Constraint Programming (CP)은 복잡한 플래닝 및 스케줄링 문제를 푸는데 중요한 두 가지 기술입니다. ILOG는 가장 어려운 옵티마이제이션 문제를 해결하는데 있어 이 두 가지 기술이 중요하다는 것을 발견하였습니다. 각 기술의 가능성을 모두 활용하기 위하여, 두 기술의 유사성과 차이점을 이해하는 것은 중요합니다.

일반적인 모델 스트럭쳐

CP (constraint programming) 최적화 모델은 의사결정 변수, 최대화 또는 최대화 목적함수, 제약 세트 측면에서 MP (Mathematical Programming) 과 같은 구조를 가지고 있습니다.

모델링 차이점

• CP 모델은 곱셈, 나눗셈, 최대값, 최소값, 의사결정 변수로 가치배열에 색인을 다는 표현 등의 비선형 수리적 표현과 논리적 제약을 지원합니다.
• CP 모델은 자주 사용되는 패턴을 신속하게 검색할 수 있는 “all-different” 제약과 같은 특정 제약을 사용합니다.
• CP 모델은 의사결정 변수를 정하는 수리 제약에 대한 제한이 없습니다. 반면, MP 엔진은 특정 수리적 성질을 만족하는 문제 클래스에 적합합니다. ILOG CPLEX list 를 참조하여 주십시오.
• CP 모델은 정수형(Boolean형 포함) 의사결정 변수를 가지고 있습니다. 반면 MP 모델은 정수형과 실수형 의사결정 변수 모두를 지원합니다.

최적화 엔진 차이점

• CP 엔진은 변수 및 값에 대한 의사결정을 내립니다. 하나의 변수에 대한 의사결정 후, 나머지 변수의 도메인에 대한 가능한 옵션을 줄이기 위한 논리적 추론을 수행합니다. 반면, MP 엔진은 개별 최적화 맥락에서 제약 완화(cutting-planes에 의해 강화된)와 “branch and bound” 컴비네이션을 사용합니다.
• CP 엔진은 현재 솔루션보다 더 나은 솔루션이 없다는 것을 보여줌으로써 최적성을 입증합니다. 반면, MP 엔진은 컷과 선형 제약완화를 통해 제시된 lower bound proof를 사용합니다.
• CP 엔진은 솔루션 스페이스 (볼록성, 선형성 등)의 수리적 속성에 대한 가정을 하지 않습니다. 반면, MP 엔진은 정밀하게 정의된 수리 카테고리 내에 모델을 두어야 합니다. (예: MIQP (Mixed Integer Quadratic Programming)

MP/CP 비교표

MP CP Relaxation   Lower bound and optimality gap measure   Optimality proof Modeler support (With ILOG CP Optimizer) Model-and-run (With ILOG CP Optimizer) Modeling limitations Restricted to linear and quadratic problems Restricted to discrete problems Specialized constraints   Logical constraints Theoretical basis Algebra Logical inferences