[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는 이 조건을 충족하지 않았다. 이 문제를 해결하기 위해 모든 계수들을 정수로 바꿀 수 있을 정도로 충분히 큰 정수값을 곱함으로써 첫번째 constraint를 변환시켜야한다. 

이건 아래 Constraints부분에서 다룬다. 

 

from ortools.sat.python import cp_model

model = cp_model.CpModel()

var_upper_bound = max(50, 45, 37)
x = model.NewIntVar(0, var_upper_bound, 'x')
y = model.NewIntVar(0, var_upper_bound, 'y')
z = model.NewIntVar(0, var_upper_bound, 'z')

# Define the constraints
# 계수가 정수가 아니므로 2를 곱해줌
model.Add(2*x + 7*y + 3*z <= 50)
model.Add(3*x -5*y +7*z <= 45)
model.Add(5*x + 2*y - 6*z <= 37)

model.Maximize(2*x + 2*y + 3*z)

# Call the solver
solver = cp_model.CpSolver()
status = solver.Solve(model)

# Display the solution
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    print(f'Maximum of objective function: {solver.ObjectiveValue()}\n')
    print(f'x = {solver.Value(x)}')
    print(f'y = {solver.Value(y)}')
    print(f'z = {solver.Value(z)}')
else:
    print('No solution found.')

Reference :

https://developers.google.com/optimization/cp/cp_example

CP 문제 해결  |  OR-Tools  |  Google Developers