M.S.28 [OR-Tools] Cryptarithmetic Puzzles cryptarithmetic puzzle은 수학적인 exercise으로 여기서는 몇자리 숫자들이 글자 혹은 기호에 의해 표현된다. 목표는 주어진 수학적 방정식을 검증할 수 있는 숫자를 찾는 것이다 : CP + IS + FUN -------- = TRUE 문자를 숫자에 한 번 할당하면 다음과 같은 방정식이 생성된다. 23 + 74 + 968 -------- = 1065 이는 이 문제에 대한 또다른 정답이다. 모든 솔루션을 어떻게 찾는지를 다루어보자. Modeling the problem 어떠한 최적화문제이건, 변수와 constraint들을 정의함으로써 시작된다. 변수는 문자들이며 이들은 어떠한 단일 숫자값을 가질 수 있다. CP + IS + FUN = TRUE에 대해 constraint들은 다음과 같다 :.. 2023. 2. 21. [OR-Tools] Solving a CP Problem 이전 섹션에서는 CP 문제에 대한 모든 정답을 어떻게 찾아내는가를 다루었다. 다음으로 우리는 어떻게 최적의 솔루션을 찾는지를 다룰 것이다. Maximize 2x + 2y + 3z subject to the following constraints: x + 7⁄2 y + 3⁄2 z ≤ 25 3x - 5y + 7z ≤ 45 5x + 2y - 6z ≤ 37 x, y, z ≥ 0 x, y, z integers 계산 속도를 높히기 위해 CP-SAT solver는 정수에 한해서 수행할 것이다. 이것은 모든 constraint들과 objective는 반드시 정수 계수를 가져야 한다는 것을 의미한다. 위의 예제에서 첫번째 constraint는 이 조건을 충족하지 않았다. 이 문제를 해결하기 위해 모든 계수들을 정수로 바.. 2023. 2. 15. [OR-Tools 스터디] CP-SAT Solver OR-Tools는 정수 프로그래밍 문제를 해결하기 위한 두가지 메인 툴을 제공한다. MPSolver (이전 섹션에서 기술된 것) CP-SAT solver(다음에서 기술할 것) CP-SAT solver와 MPSolver wrapper를 둘다 사용한 정수 프로그래밍 문제를 푸는 예제는 추후 Solving an Assignment Problem 섹션에서 확인 가능하다. 여기서는 CP-SAT solver를 어떻게 사용하는지에 대해 다룬다. Example: finding a feasible solution 간단한 예제 문제이다 : Three variables, x, y, and z, each of which can take on the values: 0, 1, or 2. one constraint: x != y .. 2023. 2. 15. [OR-Tools 스터디] Constraint Optimization Constraint optimization(or constraint programming(CP))은 문제가 임의의 constraint 관점에서 모델링 될 수 있다는 매우 큰 후보 집합 중에서 알맞은 해결책을 구분하고자 주어진 이름이다. CP문제는 많은 과학적, 공학적인 규율 속에서 일어났다. ("programming"이라는 단어는 약간 그릇된 명칭이며 이는 어떻게 "computer"가 "a person who computes"를 의미하는가와 유사한 흐름이다. 여기서 "Programming"은 컴퓨터 언어의 프로그래밍보다는 계획의 정렬을 의미한다. ) CP는 optimization(최적의 솔루션을 찾는 것)보다는 feasibility(가능한 솔루션을 찾는 것)에 기반을 두며 objective functio.. 2023. 2. 15. 이전 1 2 3 4 5 6 7 다음
