제약 조건

3. 강제 제약 조건과 유연 제약 조건

문제에서 제약 조건을 반드시 충족해야 한다면, 그러한 제약 조건을 '''강제 제약 조건'''이라고 부른다. 그러나 유연한 제약 만족 문제처럼 특정 제약 조건을 충족하는 것이 권장되지만 필수는 아닌 경우도 있다. 이러한 비필수 제약 조건은 '''약한 제약 조건'''이라고 한다.

3. 1. 강제 제약 조건 (Hard Constraints)

3. 2. 유연 제약 조건 (Soft Constraints)

4. 전역 제약 조건 (Global Constraints)

전역 제약 조건^[2]은 여러 변수 간의 특정 관계를 전체적으로 나타내는 제약 조건이다. 어떤 전역 제약 조건은 더 간단한 언어의 원자 제약 조건의 결합으로 다시 쓸 수 있지만, 다른 전역 제약 조건은 제약 조건 프레임워크의 표현력을 확장한다. 이러한 경우, 전역 제약 조건은 일반적으로 조합 문제의 전형적인 구조를 포착한다.

전역 제약 조건은 제약 만족 문제의 모델링을 단순화하고, 제약 조건 언어의 표현력을 확장하며, 제약 해결을 개선하는 데 사용된다.^[3] 변수를 전체적으로 고려함으로써 해결 과정에서 실행 불가능한 상황을 더 빨리 확인할 수 있기 때문이다. 많은 전역 제약 조건이 [https://sofdem.github.io/gccat/ 온라인 카탈로그]에 참조되어 있다.

4. 1. Alldifferent 제약 조건

4. 2. 정규 제약 조건 (Regular Constraint)

5. 예시

다음은 간단한 최적화 문제이다.

:$\backslash min\; f(\backslash mathbf\; x)\; =\; x\_1^2+x\_2^4$

제약 조건:

:$x\_1\; \backslash ge\; 1$

그리고

:$x\_2\; =\; 1,$

여기서 $\backslash mathbf\; x$는 벡터 (''x''₁, ''x''₂)를 나타낸다.

이 예에서 첫 번째 줄은 최소화할 함수(목적 함수, 손실 함수 또는 비용 함수라고도 함)를 정의한다. 두 번째 및 세 번째 줄은 두 가지 제약 조건을 정의하며, 그 중 첫 번째는 부등식 제약 조건이고 두 번째는 등식 제약 조건이다. 이 두 제약 조건은 하드 제약 조건으로, 반드시 충족되어야 함을 의미하며, 이는 후보 해의 실행 가능 집합을 정의한다.

제약 조건이 없으면 해는 (0, 0)이 되며, 여기서 $f(\backslash mathbf\; x)$는 가장 낮은 값을 갖는다. 그러나 이 해는 제약 조건을 충족하지 않는다. 위에 제시된 제약 최적화 문제의 해는 $\backslash mathbf\; x\; =\; (1,1)$이며, 두 제약 조건을 모두 충족하는 $f(\backslash mathbf\; x)$의 가장 작은 값을 갖는 점이다.

참조

_[1] 서적 Mathematical Economics https://archive.org/[...] Cambridge University Press
_[2] 서적 Handbook of constraint programming Elsevier 2006
_[3] 서적 Principles and Practice of Constraint Programming CP 2003 00 : 9th International Conference, CP 2003, Kinsale, Ireland, September 29 October 3, 2003. Proceedings Springer-Verlag Berlin Heidelberg 2003