어쩐지 오늘은

최적화 소프트웨어인 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에서 예시 코드를 보는 것도 추천
그러나 함수들만 보는 것은 어려움. 문서가 불친절
    
Python Doc
설치
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로 해결하는 과정에 대해 작성할 예정
레퍼런스 및 추천 자료
ORTools 학습 Resource
회사 사례
    
쏘카 예약 테트리스
컬리
        
컬리 물류 최적화 1
컬리 물류 최적화 2
도어대시
        
Next-Generation Optimization for Dasher Dispatch at DoorDash
Using ML and Optimization to Solve DoorDash’s Dispatch Problem
파이썬으로 구현하는 최적화 알고리즘 - 파이콘 2019 : 다양한 솔버들을 사용한 후기가 있고, Ortools, PuLP에 대해 소개함
Convex Optimization
    
이 분야는 스탠포드의 보이드 교수님 강의가 제일 기본
유튜브 영상 : Convex Optimization 1
        
이 영상은 2023년 강의로 최신 강의. Convex Optimization 2는 아직 올라오진 않음
2008년에 올라온 영상도 있음. 유튜브
Convex Optimization 책
  
글 작성하는데 걸린 시간 : 2시간 15분
    
하고자 하는 이야기, 개요 정리 : 13분
초안 글 작성 : 46분
클로드와 셀프 글 피드백 : 안함
2차 글 작성 : 1시간 16분

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

댓글