#0 OrTools란 무엇인가?

Google Optimization Tools로 구글에서 만들어 무료(open-source)로 배포하고 있는 최적화 도구입니다. 최적화 도구란 여러가지 선택 가능한 문제를 수학적 모델로 정의하고 가장 나은 선택을 제시해 주는 프로그램이라고 할 수 있다. 예를 자주 드는 N-Queen 문제가 있다. 

크기가 N x N 인 체스판 위에 퀸 N 개가 서로를 공격 할 수 없게 놓는 경우의 수를 구하는 문제

체스에서 퀸은 대각선과 가로, 세로로 공격할 수 있다. 그러면 N x N 크기의 체스판에서 공격할 수 없게 놓을 수 있는 퀸 배치 경우의 수는 몇개인가? 

8x8 N-Queens 문제(출처:https://mathworld.wolfram.com/QueensProblem.html)

N-Queens 문제는 최적화라기보다 가능한 모든 경우의 수를 구하는 문제이지만, 최대값, 최소값을 구하는 문제도 Or-Tools를 통해 구할 수 있다.

OrTools는 C++로 Core가 작성되어 있고 C#, Python, Java 등 다양한 언어로 사용할 수 있게 배포하고 있다. 무료이지만 때로는 상용 솔루션과 비슷한 성능을 보여준다. 위키피디아에 따르면 OR-Tools와 함께 제공되는 CP-SAT 솔버는 국제 제약 조건 프로그래밍 대회인 MiniZinc Challenge에서 2018년과 2020년 사이에 총 11개의 금메달을 획득했다.

다음에는 python으로 n-queens 문제를 해결하는 방법을 소개하겠다.