• 최적화(Optimization) 관점에서 본 Knapsack 문제를 정리한 글입니다
  • Cousera Discrete Optimization 2주차 강의 내용입니다

---

Greedy Algorithms

• 가장 귀중한 아이템을 먼저 가져가고 다음 배낭에 들어갈 수 있는 다음 것을 가져가는 방식
• Idea : Take the most valuable items first
• 다른 Greedy 알고리즘과 비교
  • 디자인하는 방식에 따라 매우 복잡할 수 있고, 품질이 달라질 수 있음
• 실현 가능한(feasible) 솔루션을 쉽게 구축할 수 있다고 가정
• 한번에 하나의 항목을 선택
• 여기서 Greedy의 의미를 다르게 할 수 있음
  • 1) 무게에 기반해, 작은 물건부터 가져감
  • 2) 가치가 있는 것부터 가져감
  • 3) 가치의 밀도를 측정. dollars per kilogram
• 하나의 문제에 다양한 greedy 알고리즘이 존재할 수 있음
  • 어떤 것이 다른 것보다 나을 수 있음
  • input에 의존적
• 장점
  • 빠르게 구현 가능
  • 매우 빠를 수 있음
• 단점
  • 보통 퀄리티를 보장할 수 없음
  • 퀄리티가 input에 따라 크게 다를 수 있음
  • 문제의 feasibility는 쉬워야 함
• 항상 greedy로 시작할 수 있음
• 그 후
  • Constraint Programming
  • Local Search
  • mixed Integer Programming
• 방법
  • feasible solution을 확실하게 찾기
  • high quality 솔루션을 확실하게 만들기
    • 다른 input에 로버스트한(이상치에 영향을 덜 받는) 솔루션
  • 이상적으로 해당 솔루션이 최고임을 입증

---

Knapsack Modeling

• Knapsack 문제를 수학적 모델로 공식화하는 방법
• item 조합 I이 있을 때
  • weight \(w_{i}\)
  • value \(v_{i}\)
  • capacity K for a Knapsack
• 다음 조건을 만족하는 부분 집합 찾기
  • maximum value를 갖는
  • 그러나 Knapsack의 capacity를 초과하지 않아야 함
• 모델링하는 방법
  • Decision Variable(결정 변수) 선택
    • 의사 결정의 대상
    • 목적함수 식이나 제약조건 식에서 미지수로 나타나는 변수
  • 이 변수들의 constraint(제약 조건)을 표현
    • 문제에 구체적으로 정의되어 있음
  • Objective function(목적 함수)을 표현
    • 각 해답의 퀄리티가 결정됨
• Optimization model의 결과
  • declarative formulation
    • how가 아니라 what을 명시
  • 최적화엔 많은 모델링 방법이 가능함(오픈 마인드!)
• Decision Variables
  • \[x_{i}\]
    • item i가 선택되었는지 아닌지(1이 선택, 0은 미선택)
• Problem constraint
  • 선택된 item은 knapsack의 capacity를 초과할 수 없음
  • \[\sum_{i\in I}w_{i}x_{i} \le K\]
• Objective function
  • 선택된 것들의 total value 추적
  • \[\sum_{i\in I}v_{i}x_{i}\]
• 
• Exponential Growth
  • 가능한 솔루션이 얼마나 있는지?
  • Search space(Solution space)
  • 모든 것이 feasible하진 않음(실현가능하진 않음)
    • Knapsack의 capacity를 초과할 수 없음
  • How many are they? 2^∣I∣
  • 탐색하는데 드는 시간은?
    • ∣I∣=50일 때 1,285,273,866 centuries
    • 너무 오래걸림

Dynamic Programming

• 어떻게 최고의 Knapsack 솔루션을 찾을 수 있을까
  • 다이나믹 프로그래밍을 이용해서!
• 최적화 테크닉으로 많이 사용됨
  • 다양한 종류의 문제에서 잘 작동하며 특히 생물학에 계산에서 잘 작동
• 기본 원칙
  • 분할하고 정복한다
  • bottom부터 계산한다
• Convetions and notations
  • I = {1,2,…n}
  • O(k,j)는 capacity k and items [1..j]의 optimal solution을 뜻함
  • 
• Recurrence Relations (Bellman 방정식)
  • 우리가 해결하는 방법을 안다고 가정
  • O(k,j)를 풀고 싶음
  • 만약 \(w_{j} \le k\)일 때, 2가지 케이스가 있음
    • j를 선택하지 않으면 O(k, j-1)가 best solution
    • j를 선택하면 best solution은 v_{j} + O(k-w_{j}, j-1)
  • summary
    • O(k,j) = max(O(k, j-1), v_{j} + O(k-w_{j}, j-1)) if w_{j} <= k
    • O(k,j) = O(k,j-1) otherwise
  • 당연히 O(k,0) = O for all k
• Simple program
  • 
  • recursive
• 피보나치 수를 찾기 위해 간단한 프로그램을 짤 수 있음
  • fib(n-1)은 fib(n-2)가 이미 풀려있어야 함
• Dynamic Programming
  • recursive 식으로 bottom up으로 연산함
    • start with zero items
    • continue with one item
    • then two tiems
    • then all items
  • 
• 이 알고리즈의 복잡도
  • 테이블을 모두 채워야 함 O(K n)
• polynomial?
  • how many bits does K need to be represented on a computer?

---

Relaxation, branch and bound

• Introduce branch and bound
• The value of relaxation
• Exhausitive Search(완전 탐색)
  • 가능한 방법을 전부 만들어보는 알고리즘
  • Brute Force Search라고도 함
  • 총 몇가지 나오는지 파악 => 너무 많으면 탐색 시간이 부족
  • 경우의 세를 세어보고 완전 탐색해야 함
• Branch and Bound(분기 한정법)
  • 참고 자료
  • Iterative two steps
    • branching
      • 문제를 여러 하위 문제로 쪼갬
      • 여러개의 작은 feasible subregion로 구성하고 그 과정이 subregion 각각에 대해 재귀 반복을 거쳐 tree 구조를 형성
    • bounding
      • 하위 문제의 best solution을 찾고 optimistic estimate함
      • feasible subregion 내에서 최적해를 찾기 위해 upper and low bound를 빠르게 찾는 방법
      • maximization : upper bound
      • minimization : lower bound
  • Relaxation
    • optimistic estimate를 찾는 방법
    • Optimization is the art of relaxation
    • capacity constraint를 relax할 수 있음
    • 어려운 문제를 해결하기 쉬운 문제로 근사한 것
    • Wikipedia : Linear programming relaxation
• Depth-First branch and Bound
  • 
  • 왼쪽 테이블에서 하나씩 선택하고 안하고를 분기해서 답을 찾아감
• A Knapsack Model
  • 초콜렛을 조각낼 수 있음
  • 특정 결정 변수의 fractional value를 취할 수 있음
  • Linear relaxation
    • 나중 수업에서 배울 예정
    • Integrality 요구 조건을 완화함
    • 모든 value를 정수(integer number)로 바꾸고 그것들의 분수로 이완
  • 푸는 방법
    • 용량이 소진되지 않은 상태에서 아이템 선택
    • 마지막 아이템의 분수 선택
    • 
    • 
    • linear relaxation이 문제의 해답은 아님
• 
  • relaxation으로 9 / 6 / 11.7

---

Search Strategies

• Branch and bound를 위한 탐색 전략
• Search Strategies
  • 트리를 탐색하기 위한 다양한 전략
  • Depth-first, best-first, least-discrepancy
  • many others
• Depth-first
  • 노드 추정이 best found solution보다 나쁠때 처리
  • Go deep
  • when does is prune?
    • 여태 찾은 best solution보다 나쁠 경우
  • is it memory efficient?
    • exaggerate(과장됨)
• Best-First
  • best 추정일 때 node를 선택
  • 
  • go for the best
  • when does is prune?
    • 여태 찾은 solution보다 모든 노드들이 나쁠 경우
  • is it memory efficient?
    • exaggerate(과장됨)
    • 모든 Tree를 탐색 => eponential time, space
    • worst 사례
• Least-Discrepancy
  • Greedy heuristic을 신뢰
  • Good heuristic을 추정하면
    • 실수가 적은
    • search tree가 binary
    • 휴리스틱할 경우 branching이 왼쪽으로 분기
    • 휴리스틱이 잘못되면 branching이 오른쪽으로 분기
  • Limited Discrepancy Search(LDS)
    • 실수를 줄인다
    • 실수로 증가하는 search space 탐색
    • 휴리스틱을 더 신뢰
  • Explores the search space in waves
    • no mistake
    • one mistake
    • two mistakes..
    • 이럴 때마다 search space가 줄어듬
  • 
  • 
  • trust the greedy heuristics
  • when does it prune?
    • best-first와 동일
  • is it memory efficient?
    • depth-first와 best-first 대비
• Relaxation and Search
  • Discrete optimization heaven이 만든 match
  • relaxation을 어떻게 하냐에 따라 속도가 개선될지 결정

Assignments Getting started

• 최적화에 silver bullet은 없음
  • 다양하게 접근
  • High quality : 10*4+3*2=46
  • Scalable, lower quality solution 7*6=42

---

Reference

• Coursera Discrete Optimization

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

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

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