경영과학 - Google OR-tools

일반적으로 경영과학이라고 하는 분야는 계량적 접근법 활용하여 의사결정을 하는 방법론을 총칭하는 것입니다. 애매한 정의와 같이 경영과학이란 분야는 광범위한 주제들을 포함하고 있습니다. 실제로 Management Science, Operations Research 서적을 보면 Linear Programming 부터 Integer Programmin, Dynamic Programming, Stochastinc Process, Simulation 등 다양한 내용을 다루고 있습니다.

이렇게 다양한 방법론 중 하나를 선택하여 깊게 들어가는 것도 어렵지만 중요한 일임에는 틀림이 없지만 "경영과학"이라는 용어에서 느낄 수 있듯이 경영과학에서 말하는 방법론들을 실제 의사결정에 활용하는 것이 더 의미가 있다고 생각합니다. 따라서 경영과학 주제로 이어지는 포스팅에서는 다양한 의사결정 방법론 중에서 가장 활발히 적용되는 Linear/Integer Programming 과 주요한 몇가지 방법론을 실제로 구현해보는 것에 대해서 정리해보도록 하겠습니다.

현재 Linear/Integer Programming을 수행하기 위해서 많은 Tool들이 있습니다. 가장 대표적으로는 CPLEX, Gurobi와 같은 상용 소프트웨어가 있습니다. 최적화 분야에서 Standard라고 불리긴하지만 유료이기 때문에 학교나 회사에서 지원해주지 않은 사람들이 쓰기에는 제약이 있습니다. Excel Solver와 같은 SpreadSheet기반의 최적화 Tool도 있지만  변수가 많은 경우 다루기에 무리가 있고 자유도가 조금 떨어진다고 생각됩니다.

따라서 여기서는 Python 기반에 Google OR-tools를 활용하여 Linear/Integer Programming을 해결하고자 합니다. Cvxpy, Pulp와 같은 Python 기반에  최적화 Tool도 몇가지 더 있지만 Google OR-tools은 Flow/Routing Problem과 같은 문제를 해결할 수 있는 method를 제공하기 때문에 좀 더 범용적이라 판단하였습니다. (활용하는 tool은 정말 무엇이 더 좋다기 보다는 자신의 상황/목적에 맞는걸 선택하는 것이 중요한 것 같습니다.)

Google OR-tools는 아래 주소에서 설치 할 수 있습니다. (Install OR-Tools > OR-Tools for Python > Install from Binary)

https://developers.google.com/optimization

OR-Tools  |  Google Developers

 

본격적으로 내용을 들어가기전에  간단한 Linear Programming을 Google OR-Tools를 활용하여 풀어보겠습니다. 상당히 직관적으로 문제를 정의할 수 있기 때문에 실무/과제에서도 충분히 Google OR-Tools를 활용할 수 있을 것이라고 생각됩니다.

''' 
-- 해결해야하는 문제 --

MINIMIZE 1000p1+1500p2+1000r1+1500r2

subject to
    p1+p2 >= 125,000
    r1+r2 >= 175,000
    2p1-3p2 >= 0
    p1-4p2 <= 0
    r1-2r2 <= 0
    p1,p2,r1,r1 >=0
'''

## define solver
solver_1 = pywraplp.Solver.CreateSolver('GLOP')

## define decision variable
p_1 = solver_1.NumVar(0, solver_1.infinity(), 'p_1')
p_2 = solver_1.NumVar(0, solver_1.infinity(), 'p_2')
r_1 = solver_1.NumVar(0, solver_1.infinity(), 'r_1')
r_2 = solver_1.NumVar(0, solver_1.infinity(), 'r_2')

## define constraints
solver_1.Add(p_1+p_2 >= 125000.0)
solver_1.Add(r_1+r_2 >= 175000.0)
solver_1.Add(2*p_1 - 3*p_2 >= 0.0)
solver_1.Add(p_1 - 4*p_2 <= 0.0)
solver_1.Add(r_1 - 2*r_2 <= 0.0)
print('Number of constraints =', solver_1.NumConstraints())

## defince objective function
solver_1.Minimize(1000*p_1 + 1500*p_2 + 1000*r_1 + 1500*r_2)

## invoke the solver
status = solver_1.Solve()

if status == pywraplp.Solver.OPTIMAL:
    print('Objective value =', solver_1.Objective().Value()) # Objective value = 341666666.67
    print('p_1 =', p_1.solution_value()) # p_1 = 100000.0
    print('p_2 =', p_2.solution_value()) # p_2 = 25000.0
    print('r_1 =', r_1.solution_value()) # r_1 = 116666.67
    print('r_2 =', r_2.solution_value()) # r_2 = 58333.33
else:
    print('The problem does not have an optimal solution.')