[OR-Tools 스터디] About OR-Tools

OR-Tools는 가능한 모든 해결책 중 가장 최적의 해결책 하나만을 찾아주는 combinational optimization을 위한 오픈소스소프트웨어이다. 

OR-Tools로 풀 수 있는 예제들은 vehical routing, schedulinng, bin packing 등이 있다. 

이러한 예제들과 같은 문제들은 정답을 너무 많이 가지고 있기때문에 최적의 해결책을 찾기 위해 state-of-the-art알고리즘을 사용하는 OR툴을 활용해야한다. 

 

OR-Tool은 Constraint Programming, Linear and Mixed-Integer Programming, Vehicle Routing, Graph Algorithms에 대한 해결책을 가지고 있다.

 

OR-Tools는 C++로 쓰여졌지만 python, java 혹은 .NET으로도 사용가능하다. 

(나는 python으로 학습해볼 예정이다)

 

What is an optimization Problem?

앞서 말해왔듯, 엄청난 양의 정답들 중 가장 best solution을 찾아내는 목적을 가진 것이다. 

 

모든 optimization problems는 아래의 요소들을 항상 포함한다. :

• objective : optimize하고자하는 것이 무엇인지.. ex) to minimize cost
  • optimization problem을 셋업하기 위해서는 어떠한 solution이건 objective의 값을 계산할 수 있는 function을 정의해야한다. => 이것이 objective function
  • optimal solution은 objective function의 값이 가장 최적인 것
• constraints
  • feasible solution은 반드시 최적인 경우가 아닌 문제에서 주어진 모든 constraints들을 만족하는 것 (이해못함)

solving an optimization problem in python

<A linear optimization example>

maximize 3x+y subject to the following constraints  :

1. 0 ≤ x ≤ 1

2. 0 ≤ y ≤ 2

3. x+y ≤ 2

=> 즉, 이 문제에서의 objective function은 3x+y이다. 

 

<Main steps in solving the problem>

다른 언어들에서도 아래의 셋업과정과 문제풀이 과정은 동일하다

1. 필요한 라이브러리들 import

2. solver 선언

3. 변수 생성

4. constraint 정의

5. objective function 정의

6. invoke the solver

7. 결과 display. 

 

# This is a sample Python script.

# Press ⌃R to execute it or replace it with your code.
# Press Double ⇧ to search everywhere for classes, files, tool windows, actions, and settings.

# import the required libraries.
from ortools.linear_solver import pywraplp
from ortools.init import pywrapinit

def main():
    # declare the solver
     # Create the linear solver with the GLOP backend.
    solver = pywraplp.Solver.CreateSolver('GLOP')
    if not solver:
        return


    # create the variables.
     # create the variables x and y.
    x = solver.NumVar(0,1,'x')
    y = solver.NumVar(0,2,'y')

    print('Number of variables = ', solver.NumVariables())

    # define constraints.
     # create a linear constraints
    ct = solver.Constraint(0, 2, 'ct') # 0 <= x + y <= 2
    ct.SetCoefficient(x, 1) # 0 <= x <= 1
    ct.SetCoefficient(y, 1) # 0 <= y <= 2
    print('Number of constraints =', solver.NumConstraints()) # NumConstraints sets the coefficients of x and y in expression for constraint.

    # define the objective function
     # create the objective function, 3 * x + y
    objective = solver.Objective()
    objective.SetCoefficient(x, 3)
    objective.SetCoefficient(y, 1)
    objective.SetMaximization() # SetMaximization declares this to be a maximization problem.

    # invoke the solver and display the results.
    solver.Solve()
    print('Solution:')
    print('Objective value = ', objective.Value())
    print('x = ', x.solution_value())
    print('y = ', y.solution_value())



if __name__ == '__main__':
    pywrapinit.CppBridge.InitLogging('basic_example.py')
    cpp_flags = pywrapinit.CppFlags()
    cpp_flags.logtostderr = True
    cpp_flags.log_prefix = False
    pywrapinit.CppBridge.SetFlags(cpp_flags)

    main()

나는 pycharm에서 실행시켰으며 결과는 아래와 같다. 

 

Identifying the type of problem you wish to solve

optimization 문제를 풀기 위해 프로그램을 작성하기 전, 우리가 푸는 문제가 어떠한 type인지 확인한 후 적합한 solver를 선택해야한다. 

(여기서 solver란 optimal solution을 찾기 위한 알고리즘을 말함)

아래는 solver 종류들이다. (앞으로 하나씩 배울 예정)

• linear optimization
• connstraint optimization
• mixed-integer optimization
• assignment
• schedulinng
• packing
• routing
• network flows

 

reference : 

https://developers.google.com/optimization/introduction

OR 도구 정보  |  OR-Tools  |  Google Developers

https://developers.google.com/optimization/introduction/python

Python용 OR 도구 시작하기  |  OR-Tools  |  Google Developers