Ortools 사용법 및 최적화 이론(Linear Programming)

in Data on Optimization


  • 최적화 소프트웨어인 Ortools의 사용법과 최적화 이론(Optimization)에 대해 작성한 글입니다
    • 키워드 : Ortools 사용법, Ortools Python, Ortools Install, Optimization, 최적화 이론, Linear Programming

최적화란?

최적화 소개, Operation Research의 문제

  • 최적화(Optimization)는 여러 분야에서 다양하게 사용되는 개념
    • 최적화의 정의 : 주어진 제약 조건에서 목표를 가장 잘 가장 좋은(최적의) 해답을 찾는 과정
    • 데이터, AI 분야 : 머신러닝 모델의 파라미터를 찾는 과정에서 사용(Gradient Descent, 비선형 최적화)
    • Operation Research 분야 : 비즈니스 의사 결정 문제를 해결하는 과정에서 사용(Linear Programming, Integer Programming)
    • 이 글에선 Operation Research 분야의 최적화를 주로 설명할 예정
  • Operation Research란?
    • OR은 운용 과학(또는 운영 과학, 경영 과학)이라고 번역이 되는데, 수학적인 방법을 사용해 복잡한 의사결정 문제를 해결하는 학문 분야
    • 군사 작전에서 의사 결정을 최적화하기 위해 시작했고, 여러 산업의 문제 해결에도 사용됨
  • 저는 회사에서 최적화 관련 프로젝트를 진행하면서 익혔고, 팀원분과 아래 프로젝트를 진행하면서 이해도가 높아졌어요



최적화로 풀 수 있는 여러 문제들

  • 여러가지 문제들
    • 공장의 생산 계획 최적화
    • 물류 센터의 배송 경로 최적화
    • 그 외에도 재고 최적화, 가격 최적화 등에도 적용될 수 있음
    • 통신사에서 기지국, 중계기의 최적 위치 선정하기
    • 대역폭 할당 : 트래픽에 따른 최적 자원 분배
    • 시간표 작성 : 교사, 강의실 배정 최적화, 학생 배정
    • 버스 노선 : 버스 경로 최적화
    • 항공편 스케쥴링, 승무원 스케쥴링 근무 최적화
    • 광고 플랫폼에서 광고 예산 할당, 여러 채널의 예산 최적 분배 / 입찰가 최적화, 타겟팅 최적화
    • 모빌리티, 물류, 광고 도메인에서 많이 활용됨
  • 위 내용들을 Operation Research 책, 강의에선 다음과 같이 정의함
    • 수송 문제(Transportation Problem)
      • 여러 공급지에서 여러 수요지로 물건을 운송할 때 최소 비용을 찾는 문제
      • 예 : 세 개의 창고에서 다섯 개의 매장으로 상품을 배송할 때 운송 비용을 최소화하는 방법을 찾는 것
    • 할당 문제(Assignment Problem)
      • m명의 작업자를 n개의 작업에 배정하는 문제. 각 작업자마다 각 작업에 대한 능력치가 다를 때, 전체 효율을 최대화하는 배정 방법을 찾음
      • 예 : 6명의 직원을 5개의 프로젝트에 가장 효율적으로 배정하는 문제
    • 네트워크 최적화(Network Optimization)
      • 최단 경로 찾기, 최소 신장 트리 구하기 등의 문제
      • 예 : 여러 도시를 연결하는 도로 네트워크에서 최소 비용으로 모든 도시를 연결하는 방법을 찾는 것
    • 배낭 문제(Knapsack Problem)
      • 제한된 용량 안에서 가장 가치 있는 물건들의 조합을 찾는 문제
      • 예 : 무게 제한이 있는 등산 가방에 어떤 물건들을 넣을지 결정하는 것
    • 스케줄링 계획(Scheduling Problem)
      • 작업들의 순서와 시작 시간을 정하는 문제
      • 예 : 공장에서 여러 제품을 생산할 때 기계 사용 순서를 최적화하는 것
  • 이 글에선 최적화를 배울 때 초반에 배우는 Linear Programming(LP)에 대해서 다룸
    • Linear Programming : 선형 제약 조건 하에서 선형 목적함수를 최적화하는 방법



최적화 진행 프로세스

  • (1) 문제 정의 및 수학적 모델링
  • (2) 알고리즘 결정
  • 각각의 과정은 유기적으로 진행함(수학적 모델링을 하면서 알고리즘을 결정하기도 함)



1) 문제 정의 및 수학적 모델링

문제 정의

  • 주어진 문제 상황을 보고, 다음 요소를 생각함
  • 실제 현실의 문제를 수학적 모델로 변환하는 단계
  • 최적화 문제의 구조
    • 의사 결정 변수
    • 목적 함수
    • 제약 조건
  • 의사 결정 변수(Decision Variables)
    • 우리가 실제로 찾고자 하는 값
    • 예 : X, Y
  • 목적 함수(Objective Function)
    • 최대화, 최소화하는 대상
    • 예 : 이익 최대화, 비용 최소화
  • 제약 조건(Constraint)
    • 의사 결정 변수들이 만족해야 하는 조건
    • 예 : 예산 제한, 생산 용량 제한, 한사람이 연속으로 스케줄을 진행할 수 없음
  • 참고로 목적 함수가 없다면, 최적화 문제가 아닌 실행 가능성 문제(Feasibility Problem), 제약 만족 문제(Constraint Satisfaction Problem, CSP)라고 할 수 있음
    • 이 케이스는 조건을 만족하는 해가 존재하는가? 조건에 만족하는 해를 찾음
    • 최적화 문제는 조건을 만족하는 해 중 가장 좋은 해는?
    • 때론 최적(Optimal)이 아니여도 조건에 해당되는 값만 찾아도 괜찮은 경우가 있음


문제 상황 파악

  • 우리가 통제할 수 있는 것(의사 결정 변수)과 통제할 수 없는 것(파라미터)를 구분함
    • 생산 계획(어떤 제품을 만드는 계획)에서 통제 가능한 것과 통제 불가능한 것을 나누면
    • 통제 가능: 제품의 생산량
    • 통제 불가능 : 시장 수요, 원자재 가격
  • 목표 설정
    • 달성하고자 하는 것
    • 보통 이익 최대화, 비용 최소화, 생산 시간 최소화가 많이 사용됨
  • 제약의 여러 종류
    • 물리적 제약 : 저장 공간, 생산 능력
    • 논리적 제약 : 선행 관계, 상호 배타성
    • 정책적 제약 : 최소 주문량, 예산 제한


최적화 문제 예시

  • 과자 공장에서 과자 A와 B를 생산 A는 개당 100원의 이익, B는 개당 150원의 이익이 발생
  • 하루 최대 생산량은 총 200개
  • A는 최소 50개 이상 생산해야 함
  • 위 문제를 정의하면
    • 의사 결정 변수 : A의 생산량, B의 생산량
    • 목적 함수 : 이익 최대화
    • 제약 조건
      • 총 생산량 제한(두 요소의 생산량을 합치면 200보다 낮아야 함)
      • x 생산량 제한(최소 50개 이상)
      • x, y는 모두 0 이상(음수 생산 불가능)


최적화 문제 예시 2

  • 커피숍에서 바리스타 근무 시간표를 짜야 함
  • 가게는 매일 9시부터 22시까지 운영
  • 시간당 최소 2명의 바리스타가 필요
  • 각 바리스타는 하루 8시간 근무
  • 인건비를 최소화하고 싶음
  • 위 문제를 요소에 맞게 정의하면
    • 의사결정 변수: 각 바리스타의 시작 근무 시간
    • 목적함수: 총 인건비 최소화
    • 제약조건
      • 매 시간 최소 인원 충족(최소 2명)
      • 근무 시간 제한(하루 8시간)
      • 운영 시간 준수(9시 ~ 22시)



수학적 모델링

  • 위에 정의한 내용을 수식으로 변환하는 과정. 외국어 번역과 유사함
  • 최적화 문제 예시 1의 과자 공장 생산량 결정 문제
    • 의사 결정 변수 : A의 생산량, B의 생산량
    • 목적 함수 : 100x + 150y = 이익
    • 제약 조건
      • x + y <= 200(총 생산량 제한)
      • x >= 50(A 최소 생산량)
      • x, y >= 0(음수 생산 불가능)
  • 최적화 문제 예시 2의 커피숍 바리스타 스케줄링 문제
    • 의사결정 변수 : 이것이 답이 되는가?
      • 각 시간대별로 일하는 바리스타의 수”가 답이 될 수 있을까
      • 수식으로는: x₁ = 9시 바리스타 수, x₂ = 10시 바리스타 수, …
    • 목적함수는 “우리가 최적화하고 싶은 것”을 수식으로 표현
      • “인건비 최소화”가 목표
      • 시급이 10,000원이라면 MIN(SUM(10000(x₁ + x₂ + … + x₁₃)))
    • 제약조건은 ~해야한다를 찾아서 부등식이나 등식으로 바꿈
      • “매 시간 최소 2명이 있어야 한다”
        • x₁ ≥ 2, x₂ ≥ 2, … (각 시간별로)
      • “한 사람은 8시간까지만 일할 수 있다”
        • 이 조건은 조금 더 복잡하지만, 결국 “연속된 8개의 x의 합”이 관련됩니다
  • “최소 ~명이 필요하다” → x ≥ (숫자)
  • “최대 ~개까지 가능하다” → x ≤ (숫자)
  • “A와 B를 합해서 ~이하” → x + y ≤ (숫자)
  • “A는 B의 두 배 이상” → x ≥ 2y

만약 수학적 모델링 과정이 어렵다면

  • 최종 Output 먼저 생각하기
    • 이 문제를 풀면 뭘 알고 싶은가? : 이 질문은 회사에서 커뮤니케이션을 할 때도 도움이 된다. 회의할 때 자주 활용함
    • 물류 창고의 위치를 찾고 싶은 경우
      • 어느 위치가 가장 좋을지를 알고 싶어요
      • 그러면 의사결정 변수는 x 좌표, y 좌표
  • 극단적인 케이스 생각하기
    • 제약조건을 찾을 때 활용
    • 창고가 서울에 있어도 되나요?
      • 아뇨. 너무 땅 값이 비싸요 → 그럼 땅 값을 제약 조건으로 사용
  • 처음엔 단순하게 접근하고 점진적으로 요소 추가하기
    • 처음에 모든 현실적 제약을 고려하려고 하면 어려움
    • 단순한 버전으로 한번 만들고, 거기서 제약을 추가하는 방식으로 문제 정의하는 것을 추천



2) 알고리즘 결정

  • 최적화를 진행할 때 선택할 수 있는 알고리즘은 다양함

  • 이미지 출처 : neos-guide
  • 최적화 문제를 정의하고, 여러 기준을 토대로 알고리즘을 결정함
    • 변수가 연속적(Continuous)인가? 이산값(Discrete)인가?
      • 변수가 실수 값을 가질 수 있는 경우 : Continuous -> LP 고려
      • 변수가 정수나 2진(Binary)값을 가지는 경우 : Discrete -> Integer Programming(IP), Binay Integer Programming(BIP) 고려
      • 변수가 실수, 정수 모두 다 사용해야 한다 -> Mixed Integer Programming(MIP)
    • 제약 조건과 목적 함수가 선형적인가?
      • 선형적이다 : 변수가 1차식으로만 표현, 변수끼리 곱하지 않음
      • 제약 조건과 목적 함수가 선형이면 LP/IP/MIP
      • 비선형이 존재하면 비선형 최적화
    • 논리적 제약이 많은가?
      • 복잡한 논리적 제약이 있으면 Constraint Programming(CP)
      • 제약 조건이 없는 경우엔 Unconstrained Optimization
    • 불확실성 여부에 따라서 다름
      • 불확실함이 없는 경우 : 모든 데이터를 정확히 아는 경우 => LP, IP
      • 불확실함이 있는 경우 : Stochastic Optimization, Robust Optimization
  • 또한 해 관점에서
    • 최적해가 반드시 필요한가?
    • Feasible한 값도 괜찮은가?(Feasible : 제약 조건을 만족하는 해. 최적은 아니지만 조건을 충족한 값을 의미)



Linear Programming

  • 선형 계획법
    • 많은 현실 문제를 선형으로 근사할 수 있음
    • 복잡한 최적화 문제를 해결할 때 선형 계획법이 기초가 되는 경우가 있음
    • 위 최적화 문제 예시 둘 다 LP 문제
  • LP에서 주목할 점
    • 모든 식이 일차식(xy 같은 이차항이 없음)
      • 선형 계획법의 기본 요구사항은 모든 식이 일차식이어야 함
      • 수학적인 선형은 변수들이 곱해지거나 제곱되지 않고, 단순히 더해지기만 하는 것을 의미미함
      • 선형인 식 : 3x + 2y
      • 비선형 : xy(변수가 곱해짐) 또는 x^2(변수가 제곱)
      • 선형성이 보장되어야 global optimum을 찾을 수 있음. 비선형이 되면 문제가 훨씬 복잡해짐
    • 부등호 사용
      • 현실의 제약을 표현할 때 중요함
      • 제약 조건을 잘 보는 것이 중요한데, 재료를 정확히 M을 사용한다보단 M 이하로 사용한다가 현실적인 옵션(재료는 남아도 되므로)
    • 음수 제약이 명시적으로 포함
      • 음수 제약이 없으면, 수학적으로 -10개 생산이 가능함. 그러나 현실에선 음수 생산은 불가능



최적화 솔루션

  • 최적화 솔루션은 모델링 툴과 솔버로 나뉨
  • 모델링 툴 : 다양한 솔버를 선택할 수 있음. 최적화 문제를 해결하는 인터페이스라고 보면 됨
  • 솔버 : 자동차의 엔진처럼 핵심 알고리즘이 구현됨
    • 실제 최적화 문제를 푸는 것은 솔버
    • Gurobi, Cplex 등이 대표적인 상용 솔버
    • Ortools에서 사용할 수 있는 솔버
      • 단순한 선형 문제 : GLOP
      • 정수 제약이 있는 경우 : SCIP
      • 복잡한 논리 제약이 있는 경우 : CP-SAT 솔버
  • 아래 글에선 구글이 만든 Ortools에 대해 설명할 예정
  • 그 외 최적화솔루션, 솔버에 대해선 Optimization Software에 잘 나와있음



Ortools 사용하기

  • Ortools는 구글에서 만든 최적화를 위한 오픈소스 제품
  • 차량 라우팅 문제, LP, CP 등의 문제를 처리하는데 최적화 됨
  • Ortools 문서 : 이 페이지에서 다양한 알고리즘의 설명과 코드 예시를 볼 수 있음
    • GitHub에서 예시 코드를 보는 것도 추천
  • 그러나 함수들만 보는 것은 어려움. 문서가 불친절


설치

pip3 install ortools



Ortools Python 코드 설명

  • Solver 인스턴스 생성 : 어떤 솔버를 사용할지 명시

      solver = pywraplp.Solver.CreateSolver('GLOP')

  • 의사 결정 변수 정의

      # 변수 x는 0 이상의 실수값을 가질 수 있음
  # CreateNumVar의 인자는 (최소값, 최대값, 변수 이름)
  x = solver.NumVar(0, solver.infinity(), 'x')
  y = solver.NumVar(0, solver.infinity(), 'y')

  • 제약 조건 설정 : solver.Add로 제약 조건 추가

      # x + 2y ≤ 10 형태의 제약 조건 추가
  solver.Add(x + 2 * y <= 10)
  solver.Add(x + y <= 6)

  • 목적 함수 설정 : solver.Maximize, solver.Minimize 사용

      # 최대화: 2x + 3y
  solver.Maximize(2 * x + 3 * y)

    • 또는 다음과 같이 구성할 수 있음

        objective = solver.Objective()
  objective.SetCoefficient(x, 2)  
  objective.SetCoefficient(y, 3) 
  objective.SetMaximization()
  • 최적화 시작 : solver.Solve()를 실행하면 최적화가 시작
    • x.solution_value()을 사용하면 값을 확인할 수 있음
      status = solver.Solve()
    
  # 결과 출력
  if status == pywraplp.Solver.OPTIMAL:
      print('해를 찾았습니다!')
      print('x =', round(x.solution_value(), 2))
      print('y =', round(y.solution_value(), 2))
      print('최적값 =', round(solver.Objective().Value(), 2))
  else:
      print('해를 찾지 못했습니다')
  • 정리
    • Solver 생성: 문제 유형에 맞는 솔버를 선택. 여기서는 선형 계획법을 위한 ‘GLOP’을 사용
    • 변수 정의: solver.NumVar()를 사용해 변수를 생성. 각 변수의 범위를 지정할 수 있음
    • 제약조건 추가: solver.Add()를 사용해 제약조건을 추가
    • 목적함수 설정: solver.Maximize() 또는 solver.Minimize()로 목적 함수를 설정
    • 문제 해결: solver.Solve()로 해를 구함


Ortools의 Solver

  • GLOP: Google의 자체 선형 계획법 솔버입니다. 순수한 선형 계획법 문제(즉, 모든 변수가 실수이고 제약조건과 목적함수가 선형인 경우)에 사용. 가장 기본적이고 간단한 문제에 적합함
  • SCIP: 혼합 정수 계획법(MIP) 문제를 풀 수 있는 솔버. 변수 중 일부가 정수여야 하는 경우에 사용함
  • CP-SAT: 제약 프로그래밍(Constraint Programming) 문제를 위한 솔버. 복잡한 논리적 제약 조건이 있는 문제에 적합함



연습 문제

  • 연습 문제는 직접 풀어보는 것을 추천해요!



연습 문제 1번

  • 작은 가구 공장에서 책상과 의자를 만듭니다.
    • 책상: 이익 200달러, 제작 시간 4시간, 목재 30단위 필요
    • 의자: 이익 100달러, 제작 시간 2시간, 목재 10단위 필요
    • 가용 자원: 하루 작업시간 32시간, 목재 200단위
  • 목표: 하루 최대 이익을 계산하기





연습 문제 2번

  • 작은 학교의 시간표를 작성해야 합니다.
    • 3명의 선생님(국어, 수학, 영어)
    • 2개 학급
    • 하루 4교시
    • 각 선생님은 각 학급에 하루 1회 이상 수업
    • 한 선생님이 같은 시간에 두 학급에서 수업할 수 없음
    • 같은 과목은 하루에 2교시 이상 연속으로 배치할 수 없음
  • 목표는 미정. 실행 가능한 Feasible한 값 출력하기
  • SCIP 솔버를 사용해서 풀고, 나중에 Constraint Programming을 학습하면 CP로 풀어보는 것을 추천



정리

  • 최적화의 정의와 어떤 흐름으로 문제를 푸는지, 수학적 모델링을 하는 과정에 대해 작성함
    • 머신러닝, AI 분야가 아니지만 회사에선 이런 문제를 푸는 경우도 있음
  • 다음 글에선 IP, MIP, CP를 Ortools로 해결하는 과정에 대해 작성할 예정



레퍼런스 및 추천 자료



  • 글 작성하는데 걸린 시간 : 2시간 15분
    • 하고자 하는 이야기, 개요 정리 : 13분
    • 초안 글 작성 : 46분
    • 클로드와 셀프 글 피드백 : 안함
    • 2차 글 작성 : 1시간 16분

카일스쿨 유튜브 채널을 만들었습니다. 데이터 사이언스, 성장, 리더십, BigQuery 등을 이야기할 예정이니, 관심 있으시면 구독 부탁드립니다 :)

PM을 위한 데이터 리터러시 강의를 만들었습니다. 문제 정의, 지표, 실험 설계, 문화 만들기, 로그 설계, 회고 등을 담은 강의입니다

이 글이 도움이 되셨거나 다양한 의견이 있다면 댓글 부탁드립니다 :)

Buy me a coffeeBuy me a coffee



© 2017. by Seongyun Byeon

Powered by zzsza