1 조합최적화 문제란?

• 이산적인 탐색공간에서 최적의 조합을 찾는 문제
• 대표적으로 TSP, 차량 배차 문제, 스케쥴링 (간호사 업무 배정, SCM, 스포츠 경기 일정 수립 등)이 있습니다.
• 2023 프로야구 일정 톺아보기
  https://absorbed-in-optimization.tistory.com/15
• AI 오픈소스로 2023 프로야구 일정 수립하기
  https://absorbed-in-optimization.tistory.com/17
• 모든 경우의 수를 다 시도해봐야 가장 좋은 해를 알 수 있고, 누군가 자신 있게 이 조합이 좋은 해라고 말해도 좋은 해인지 알 수 없습니다. (어딘가 더 좋은 해가 숨어 있을지 모릅니다.)

2 기존 풀이 방법

2.1 Heuristics

• 수 초 내에 룰을 기반으로 문제를 풀어본다.
• 예를 들어 차량 배차 문제의 경우, 어떤 순서대로 주문을 배정하는가(요청 일자가 빠른 순서대로, 차량 출발지 기준으로 시계 방향으로 등), 어떤 순서대로 차량을 배정하는가 (직영 차량 우선, Capa가 큰 차량 우선) 등의 Rule을 만들어 수 초 내로 초기 해를 산출합니다.
  https://velog.io/@drimdrim2002/Heuristics-%EC%A0%95%EB%A6%AC

2.2 Improvement

• 초기 해를 기준으로 랜덤성을 기반으로 새로운 해를 찾아봅니다. (메타휴리스틱)
• 유전자 알고리즘 (Genetic Altorithm), Tabu Search, Simulated Annealing 등

2.3 Optaplanner

• Heuristics + Meta Heuristics 을 통합한 AI 오픈소스 Solver
  https://www.optaplanner.org/

3 람다 병렬 처리를 생각한 이유

3.1 병렬 작업 필요한 이유

• Heuristics의 경우에도 보통 여러 가지 Rule 을 동시에 적용한 후 가장 좋은 해 하나를 선택하는 기능 필요
• Meta Heuristics의 경우, 기존에는 각 쓰레드마다 Random Seed를 다르게 설정하여, 각 쓰레드에서 동시에 해를 산출하고 가장 좋은 해 하나를 선택하도록 되어 있음
• 이 작업을 순차적으로 진행하게 되면 많은 시간이 걸리기 때문에, 기존 On Premise 환경에서는 Multi Thread로 병렬 작업 수행

Pseudo Code

ExecuteService threadPool = Executors.newFixedThreadPool(threadSize);
List<Solution> solutions = deepCloningSolutions(solution, threadSize);
List<Callable<MetaAlgorithm>> callables = new ArrayList<Callable<MetaAlgorithm>>();
Future<Solution> futures = threadPool.invokeAll(callables);

3.2 고사양 EC2가 필요하나 비용 문제

• 최적화 문제는 반복적인 많은 연산이 필요하여 고사양이 필요
  https://aws.amazon.com/ko/events/summits/seoul/agenda/
• 차량 배차 작업이나 업무 배정 작업은 보통 하루에 3,4번 수행
  • 하루 몇 번 수행되는 작업 때문에 고사양 EC2 서버를 24시간 가동하는것이 비효율적

3.3 람다 병렬 처리를 통해 멀티프로세스를 대신할 수 있는지?

• 그러나 Lambda는 쓰레드 사용이 제한적임 --> 경험적으로 하나의 Lambda에 안정적으로 확보할 수 있는 thread 수는 4개 정도 추정

람다를 통한 병렬 처리 안

기대 효과와 우려 (생각나는대로 정리)

1. 기존 멀티쓰레드 방식보다 안전하게 개발 진행

• 쓰레드 간 간섭이 없어지고, 디버깅도 편리해짐

2. Solver 람다 결과를 어떻게 효율적으로 취합할 것인가?
3. Solver 람다를 얼마나 주기적으로 실행할 것인가?

• Solver 람다 실행 Step을 너무 짧게 설정하면 취합시 발생하는 오버헤드가 클 수 있음
• Solver 람다 실행 Step을 너무 길게 설정하면 알고리즘에 따라 특정 Solver 람다의 실행 시간이 길어져 비효율적이 될 수 있음