LG AI Research 156

LG AI연구원의 Data Intelligence Lab은 현실의 난제를 해결하기 위해 조합 최적화(Combinatorial Optimization) 연구에 집중하고 있다. 조합 최적화는 외판원 문제, 최소 신장 트리, 배낭 문제 등으로 대표되며, 실행 가능한 해의 영역이 이산적(Discrete)이라는 특징을 가진다.

특히 **배낭 문제(Knapsack Problem)**는 제한된 무게 내에서 가치를 최대화하는 문제로, 물건의 개수가 늘어날수록 가능한 조합이 기하급수적으로 증가한다. 이러한 특성 때문에 많은 조합 최적화 문제는 NP-Complete에 속하는 어려운 문제로 분류된다.

이러한 문제는 수학적으로 **정수 계획법(Integer Programming)**으로 표현할 수 있다. 변수가 실수가 아닌 정수 집합에 속하기 때문에, 기존의 선형 계획법(Linear Programming)과 달리 효율적인 최적해를 찾는 것이 매우 까다롭다.

현재 산업계에서는 이러한 문제를 해결하기 위해 다음과 같은 소프트웨어 패키지를 활용한다.

• CPLEX: 선형 및 정수 계획법을 지원하는 대표적 도구
• GUROBI: 유료로 제공되는 고성능 최적화 도구
• SCIP: 무료로 사용 가능한 최적화 도구
• OR-Tools: 구글에서 제공하는 최적화 솔루션