# CP-SAT와 Python을 활용한 제약 프로그래밍 실용 입문

> Clean Markdown view of GeekNews topic #15689. Use the original source for factual precision when an external source URL is present.

## Metadata

- GeekNews HTML: [https://news.hada.io/topic?id=15689](https://news.hada.io/topic?id=15689)
- GeekNews Markdown: [https://news.hada.io/topic/15689.md](https://news.hada.io/topic/15689.md)
- Type: GN+
- Author: [neo](https://news.hada.io/@neo)
- Published: 2024-07-05T09:54:04+09:00
- Updated: 2024-07-05T09:54:04+09:00
- Original source: [pganalyze.com](https://pganalyze.com/blog/a-practical-introduction-to-constraint-programming-using-cp-sat)
- Points: 1
- Comments: 1

## Topic Body

##### 제약 프로그래밍을 이용한 실용적인 소개: CP-SAT와 Python

###### 선언적 패러다임
- **제약 프로그래밍(CP)**은 이산 최적화 문제를 해결하기 위한 선언적 패러다임임
- **명령형 프로그래밍**과 달리, 원하는 결과를 기술하고 프로그램이 스스로 결과를 도출함
- 예를 들어, 성인 명단을 추출하는 경우 명령형 접근법과 선언적 접근법의 차이를 설명함

###### 제약 프로그래밍(CP)의 기본
- **모델**: 문제의 원하는 결과를 기술하는 것
- **변수**: 찾고자 하는 값, 각 변수는 도메인(허용되는 값의 집합)을 가짐
- **제약 조건**: 변수 간의 관계를 기술함
- **해결책**: 변수에 값을 할당하여 제약 조건을 만족시키는 것

###### Python과 CP-SAT를 이용한 실용적인 예제
- **문제**: 직원의 주간 근무 일정을 생성하는 것
- **모델 생성**: CP-SAT를 사용하여 빈 모델을 생성함
- **데이터**: 직원 목록과 역할, 근무일, 근무 교대 시간 정의
- **변수 정의**: 각 직원의 근무 여부를 나타내는 불리언 변수 생성
- **제약 조건 추가**: 문제 설명에 따라 변수에 제약 조건을 추가함

###### 모델 해결
- **해결**: 모델을 해결하고 결과를 도출함
- **추가 제약 조건**: 초과 근무 방지, 특정 직원의 근무 시간 제한, 특정 직원 간의 근무 시간 겹침 방지 등 추가 제약 조건을 추가함

###### 중간: 해결 상태
- **해결 상태**: 최적, 실행 가능, 실행 불가능, 알 수 없음 등의 상태를 반환함
- **예시**: 간단한 예제를 통해 각 상태를 설명함

###### "미안해, Emma"
- **실행 불가능 상태**: Emma가 주중 5일을 쉬는 것은 불가능함
- **대안 제안**: Emma가 주중 3일만 쉬도록 제안함

###### 목표: 근무 시간의 균등 분배
- **목표 추가**: 근무 시간을 균등하게 분배하기 위해 목표를 추가함
- **결과**: 각 직원의 근무 시간이 균등하게 분배됨

###### 결론
- **기본 개념 소개**: 제약 프로그래밍의 기본 개념을 소개하고 실용적인 예제를 통해 설명함
- **다음 기사 예고**: 다음 기사에서는 Postgres의 인덱스 선택에 제약 프로그래밍을 사용하는 방법을 다룰 예정임

##### GN⁺의 의견
- **제약 프로그래밍의 유용성**: 복잡한 최적화 문제를 해결하는 데 매우 유용함
- **CP-SAT의 강점**: Google의 OR-Tools 프로젝트의 일환으로 개발된 CP-SAT는 강력한 성능을 자랑함
- **실제 적용 사례**: 직원 근무 일정 생성과 같은 실제 문제에 적용 가능함
- **기술 채택 고려 사항**: 새로운 기술을 채택할 때는 학습 곡선과 기존 시스템과의 통합 문제를 고려해야 함
- **유사 프로젝트 추천**: IBM의 CPLEX, Gurobi 등의 상용 솔버도 유사한 기능을 제공함

## Comments



### Comment 26974

- Author: neo
- Created: 2024-07-05T09:54:04+09:00
- Points: 1

###### [Hacker News 의견](https://news.ycombinator.com/item?id=40867746) 
- 과거에 제약 해결기를 사용한 경험이 있으며, 이 도구들이 매우 놀라운 성능을 발휘함
  - 문제는 초보자를 위한 자료가 거의 없다는 점임
  - 대부분의 자료는 스도쿠 해결 방법이나 고도로 기술적인 연구 자료임
  - 더 많은 문제를 해결할 수 있는 도구들이 더 접근 가능했으면 좋겠음
  - 접근 가능하다는 것은 여전히 프로그래머가 필요하다는 의미임

- MiniZinc와 Python을 사용하는 짧은 챕터를 내 오래된 책에서 재작성 중임
  - MiniZinc는 제약 프로그래밍 시스템임
  - Coursera에서 MiniZinc를 사용하는 좋은 강의가 있음

- 많은 프로그램들이 단일 데이터 표현을 가지려고 노력하는데, 이는 대부분의 경우 비합리적임
  - 새로운 표현으로 알고리즘을 작동시키기 위해 많은 왜곡이 필요함
  - 더 자주 표현을 변환하지 않는 것이 항상 아쉬움
  - 표현을 변환하면 매우 간결한 표현을 얻을 수 있으며, 이는 더 빠른 실행을 가능하게 함

- 스포츠 캠프를 운영하는 고객이 있음
  - 아이들이 원하는 스포츠와 친구를 요청할 수 있음
  - 이는 인간에게는 어려운 일정 문제를 만듦
  - OR-Tools 기반의 최적화 도구를 사용하여 간단한 시스템을 구축함
  - 이제 몇 번의 클릭으로 일정이 완료됨

- 2000년대 초반에 많은 해결기를 사용한 경험이 있음
  - 현재는 Python을 사용하는 소프트웨어(웹) 작업 중임
  - 이 주제에 대한 깊은 탐구를 보게 되어 기쁨
  - 제약을 모델로 변환하는 것이 작업의 90%이며 가장 어려운 부분임

- 주로 제약 해결기로 작동하는 파라메트릭 CAD가 있는지 궁금함
  - 초기에는 신경 쓰지 않는 매개변수 값을 추정해야 하는 것이 자주 불편함
  - 대신 관심 있는 매개변수를 제약하고 나머지를 최적화하고 싶음

- 혼합 정수 프로그래밍과 비교하면 어떨지 궁금함