복잡한 최적화 문제 해결에 필수적인 혼합 정수 선형 계획법(MILP) 모델은 그동안 수많은 연구 논문에 파편화되어 있어 실제 적용과 재현에 어려움이 있었습니다. 특히 철도 재조정(railway rescheduling)과 같은 분야에서는 방대한 모델링 지식이 비호환적인 표기법으로 흩어져 있어, 연구자들이 기존 모델을 이해하고 활용하는 데 많은 시간과 노력이 소요되었습니다. 이러한 문제를 해결하기 위해, 새로운 연구 'LP Mining with LP2Graph'는 LP2Graph라는 방법을 통해 출판된 LP 및 MILP 모델의 구조를 자동으로 추출하고 표준화하여 재현 가능한 데이터셋과 분류 체계(taxonomy)를 구축하는 혁신적인 접근 방식을 제시합니다.
LP2Graph의 핵심은 각 모델을 '변수-방정식 그래프(variable-equation graph)' 형태로 표현하는 것입니다. 이 방법은 각 모델을 정규 문법(canonical grammar)에 따라 단일 정규 모델(canonical model)로 변환한 후, 변수, 제약 조건, 목적 함수, 그리고 전체 모델 구조에 따라 하향식(bottom-up)으로 클러스터링합니다. 또한, 응용 분야 및 해결 접근 방식에 따라서도 별도로 분류합니다. 이렇게 생성된 그룹에는 규칙 기반의 자체 업데이트 분류기(rule-seeded, self-updating classifier)를 통해 레이블이 부여됩니다. 연구팀은 이 표현 방식의 유효성을 검증하기 위해 각 클러스터의 대표 모델을 독립적인 LaTeX 코드로 재생성하고, CBC, HiGHS, Gurobi와 같은 상용 솔버를 사용하여 원본 논문에서 보고된 최적값과 비교하여 정확성을 확인했습니다.
이러한 LP2Graph는 변수, 제약 조건, 모델 유형에 대한 객관적이고 반복 가능한 분류 체계를 제공함으로써, 최적화 모델 개발의 자동화를 위한 중요한 기반을 마련합니다. 특히 철도 재조정 모델 개발을 자동화하는 'raiLPminer'와 같은 시스템에 원칙적인 토대를 제공할 수 있습니다. 이는 단순히 모델을 분류하는 것을 넘어, 기존에 파편화되어 있던 지식을 체계화하고 새로운 모델을 더 효율적으로 개발할 수 있도록 돕는다는 점에서 큰 의미를 가집니다. 궁극적으로 다양한 산업 분야에서 최적화 문제 해결의 효율성을 높이고, 새로운 솔루션 개발을 가속화하는 데 기여할 것으로 기대됩니다.