▲

지난 50년간의 정수 선형 프로그래밍: 최근 실용적 진보

 (inria.hal.science)
1P by GN⁺ 2일전 | ★ favorite | 댓글 1개
  • 정수 선형 프로그래밍(MILP) 은 여러 산업 분야에서 핵심 도구로 자리잡음
  • 최신 솔버의 계산 효율성 향상 덕분에 과거에는 풀기 어려웠던 문제도 빠르게 최적해를 찾을 수 있음
  • 이 기사에서는 MILP 해법의 최근 실용적 발전과 컴퓨팅 성능 개선에 초점을 맞춰 설명함
  • 주요 방법론으로 branch-and-cut, Dantzig-Wolfe 분해, Benders 분해가 소개됨
  • MILP 분야의 지속적 도전과 미래 연구의 기회가 요약되어 있음

서론

  • 혼합 정수 선형 프로그래밍(MILP) 은 오퍼레이션 리서치에서 필수적인 도구로, 다양한 산업 영역에서 성공적으로 활용되고 있음
  • 최신 MILP 솔버는 이제 예전에는 불가능했던 대규모 문제도 몇 초 만에 최적해 탐색 가능함
  • 이로 인해 운송, 공급망, 수익 관리, 금융, 통신, 제조업 등 다양한 분야에서 MILP의 적용이 확대되었음
  • 하지만 여전히 해결되지 않은 문제와 새로운 과제들이 남아있어, MILP 연구는 꾸준히 활발하게 진행 중임

주요 내용 개요

  • 본 논문은 MILP 해법의 최근 발전상과 실용적 성능 개선을 중심으로, 각 기술이 실제로 어떤 컴퓨팅 퍼포먼스 향상에 기여했는지 분석함
  • 방대한 문헌 중에서도 실제 컴퓨팅 실험에 근거한 연구들을 우선적으로 다룸
  • MILP 해법의 세 가지 핵심 분야로 논의를 구성함
    • Branch-and-Cut 방법: 노드 분할 기법과 컷팅 플레인 기법을 결합한 대표적 MILP 해결 방식임
    • Dantzig-Wolfe 분해: 대규모 문제를 더 작은 부분 문제로 나눠 효율적으로 처리하는 분해 접근 방식임
    • Benders 분해: 변수와 제약을 분리하여 반복적으로 해결함으로써 복잡한 구조에서 계산 부담을 낮추는 방법임

마무리: 도전 과제와 미래 전망

  • 논문 마지막 부분에서는 여전히 남아있는 MILP의 도전과제와 미래 연구기회를 조망함
  • 더 복잡해지는 실제 산업 문제들, 데이터의 확장, 솔버 성능 한계 등이 앞으로의 주요 연구 주제임
  • 앞으로 MILP 분야는 알고리듬의 진보, 하드웨어의 발전, 새로운 응용 도메인의 확대와 함께 계속 성장할 전망임
▲
GN⁺ 2일전  [-]
Hacker News 의견

  • 누군가 Gurobi 같은 상업용 ILP 솔버가 무료/오픈소스 솔버보다 훨씬 뛰어난 이유를 한 번 설명해줄 수 있는지 궁금증 표현, ILP 본질적 난이도로 인한 것인지, 아니면 최고의 솔버란 특정한 서브문제들을 위한 방대한 휴리스틱들 집합이기 때문인지, 그래서 일반적으로 "좋은" 전략이 아직 공개 도메인에 없었는지 질문

    • 상업용 솔버는 대부분 고객과 긴밀하게 협력해 문제 특화 가속화 기법 구현, 10~20년 동안 쌓인 노하우 보유 언급, MILP 분야에서 좋은 휴리스틱(브랜치&바운드 시작점 선정, 효과적 트리 가지치기)과 커스텀 컷(부분해를 효율적으로 배제) 활용 강조, 또한 OR 분야 연구자들이 문제를 직접 골라 커스텀 커트와 휴리스틱을 작성하면 종종 상업용 솔버보다 더 나은 결과 얻을 수 있음, 그러나 솔버 회사는 이를 일관적으로 구현하기 위해 박사급 연구팀을 채용하고 수많은 고객 실제 문제 데이터로 개선 추적

    • 상업용 솔버는 실제 고객이 관심을 갖고 도와주기 때문에 문제 해결 성능 조정에 막대한 시간과 자원 투자 가능, 휴리스틱 외에도 간단한 서브문제나 근사 문제 인식 후 이를 전체 문제로 피드백하는 과정도 포함됨, 오픈소스 솔버는(1) 최신 옵티마이저 개발 진입장벽이 매우 높고(수학과 코딩 모두 숙련자가 적음), (2) 만약 그 정도 실력이 있다면 보통 돈 많이 버는 커리어로 빠짐, (3) 오픈소스 구조상 고객이 개선을 위한 케이스, 성능 데이터, 프로파일링 등을 거의 제공하지 않아 한계 노출<br> 예외로는 SNOPT처럼 상업 목적이지만 비전통적 상업 개발인 경우가 있으며, 학계 솔버는 특정 응용 분야에 집중되어 범용성이 낮음, 타 분야에서는 구글 등 큰 회사가 인수 또는 지원을 해 생태계 키우기도 하지만, 솔버 분야는 처음부터 전 범위 스택을 구축하기엔 투자 부담이 너무 큼

    • 상업용 솔버는 정말 다양한 트릭과 패턴 탐지 메커니즘을 통해 문제에 따라 어떤 트릭이 효과적일지 파악 가능, 문제 구조를 잘 알면 상업용 솔버보다도 빠르게 만들 수 있지만 랜덤한 문제라면 승산이 거의 없음

    • "솔버=특화된 서브문제에 대한 다양한 휴리스틱 집합"이라는 주장이 있는데, NP-Hard 문제에는 거의 모든 게 그런 구조라는 지적, ILP는 SAT와 동등하므로 동일하게 적용 가능

    • 상업적 규모와 속도 문제, 대부분의 퀀트 트레이딩 회사들은 매우 큰 최적화 문제를 가능한 자주 돌리는데, 오픈소스 솔버는 종종 아예 문제를 풀지 못하거나 메모리 부족 문제가 발생할 정도, 그만큼 격차 존재

  • IBM의 ILOG MILP 라이브러리로 자원 할당 툴 만들 때 경험 회상, 20년 전에 비슷한 문제를 풀었다면 지금 5분 만에 해결하는 데 그때는 아직 풀고 있을 것임, 컴퓨터 성능은 천 배 올랐고 알고리즘도 천 배 좋아져서 전체적으로 백만 배 향상, 미래 예측 때 한번쯤 곱씹을 만한 이야기, 참고로 여기서의 "자원"은 다이아몬드였음

  • 실제로 어떻게 활용되는지 궁금증, 수치 최적화는 데이터 기반의 일반적인 한계(신뢰, 데이터 문제 등)로 인해 결국 중요한 사람이 '감'으로 의사결정 하는 경우가 많지 않냐는 질문

    • 회사에서 스택 전체에 걸쳐 솔버 사용, 가정용 배터리 및 EV 스케줄링 최적화, 수십만 가정 포트폴리오 최적 스케줄링, 그 포트폴리오 거래까지 솔버로 수행, EU 전기 스팟 가격도 Euphemia라는 단일 거대 솔버 실행으로 결정, 실질적으로 돈과 연결된 명확한 최적화 목표가 있는 분야라면 어디든 솔버가 널리 쓰임 언급

    • FMCG 회사에서 실제 활용 예시, (1) 영업사원 및 배송 경로 계획, (2) 생산을 위한 기계, 인력, 자재 스케줄링, (3) 창고 분포센터 적정 재고 수준 결정 등, 수요 예측의 어려움 때문에 완전 자동화되진 않음

    • 참고할 만한 사례 연구 링크 공유: Gurobi 사례 연구, CPLEX 사례 연구, Hexaly(옛 LocalSolver) 사례 연구

  • Gurobi는 꽤 비싸다는 이야기 들었는데 실제 가격 정보 공유 가능 여부 질문

    • 구체적인 가격은 비공개지만, MIP 실습 목적이면 XPRESS/Gurobi/CPLEX 등 상업 솔버를 구입할 필요 없이 학생용 무료 라이선스나 비상업적 무료 오픈소스 MIP 솔버 사용 추천, 예: HiGHS, SCIP

    • 들은 바로는 가격 책정이 "전화해서 협상" 수준이고, 실제로 고객이 얼마나 돈을 버는지 보고 그에 맞춰 금액 책정하는 방식이라고 전해짐

    • 느린 하위 최적(서브옵티멀) 의사결정보다 훨씬 싸다는 점 강조, 작은 문제는 무료 솔버(GLPK 등)로 충분하지만 비즈니스 현장 대형 문제는 제시간에 해답을 얻는 게 거의 불가능, 그래서 프리미엄 솔버는 값어치 충분

    • 10년 전쯤, 서버 여러 명 라이선스 기준으로 약 10만 달러 정도 기억, 정확한 사용자 수나 서버 수 제한은 기억나지 않음, 업계에선 그 정도 가치 충분히 인정된다는 점도 언급

    • Gurobi는 시간 단위로 과금하는 클라우드 서비스도 제공하며, 비학술 라이선스는 매우 비쌈

  • 1990년대 Gomory 컷팅 하이퍼플레인 직접 구현해 봤던 경험, 그동안 분야가 얼마나 발전했는지 놀람, 예전엔 LP 문제 푸는 데 두 달 걸렸다가 이제 1초면 충분, Bixby의 연구서 1990년-2020년 사이 CPLEX와 Gurobi가 기계 성능 독립적으로 거의 400만 배 빨라졌다고 보고됨

  • 1988~2004년 사이 하드웨어는 1600배, LP 솔버는 3300배 빨라짐, 그때만 해도 누적 속도 향상 500만 배 이상, 2001~2020년 상업용 MILP 솔버도 1000배 이상 빨라짐(알고리즘이 50, 컴퓨터가 20), 이런 각 분야별 속도 향상 데이터를 알고리즘 및 컴퓨터 기여도로 분해해서 모아보면 어떨지 호기심, 컴파일러 분야에는 "Proebsting의 법칙"처럼 18년마다 컴파일러 발전이 컴퓨팅 파워 2배 증가 효과를 낸다는 결과도 있음

  • ML/AI 기반 접근이 이런 문제에는 의외로 많이 안 쓰인 것 같다는 느낌, RL/GNN 활용 사례가 소규모 문제에 시도되는 논문은 있으나 결국 Gurobi 라이선스 구매가 최선 같음, 최근 스케줄링 최적화 하면서 RL 사례도 봤지만 실제 성능은 미흡, 큰 문제에는 진화 알고리즘 최적, 결국 문제 공식을 잘 세울 수 있다면 OR 기반 접근이 가장 효율적인 듯

    • 문제 종류에 따라 다름, 예를 들어 발전소 ON/OFF 결정(유닛 커밋먼트)는 극도로 복잡하지만 MILP 솔버라면 글로벌 최적 해를 신속히 탐색 가능, 유전 알고리즘은 로컬 미니마에서 벗어날 보장도 없고, 실행 속도도 느릴 수 있음, 뉴럴 네트워크도 항상 서브옵티멀

    • SAT는 전통적 GOFAI 문제이고, ML 패밀리 모든 언어로도 SAT 솔버 작성 가능, 오히려 "ML/AI" 접근은 충분히 적용 가능

  • pdf 표기를 제목에 추가하면 좋겠다는 코멘트

  • Integer linear programming이 복잡해 보이지 않는다는 의견

    • 그래프 정점 3-컬러링(G3C)는 NP이자 NP-Hard이므로 NPC, 일반 ILP 풀면 G3C도 풀 수 있다는 결과 있음, 또 SAT도 NP-Complete, SAT 풀면 G3C 풀 수 있으므로 G3C 풀 수 있으면 정수 인수분해(FAC)도 가능, FAC는 NPC는 아니지만 현재 컴퓨팅 환경에서 엄청 중요, 즉 임의 ILP 풀면 주요 암호 알고리즘 파괴 가능, ILP가 매우 까다로운 문제임을 유추, 많은 사람들이 헷갈리는 부분은 NPC 문제는 랜덤 인스턴스가 대체로 쉽게 풀리는 점, 난이도 있는 인스턴스 비율은 문제 크기 커질수록 오히려 작아짐

    • 외판원 문제(Travelling Salesperson Problem, TSP)도 ILP로 인코딩 가능, 상당한 난이도 시사

    • 조건을 가장 잘 만족하는 정수를 찾아야 하는데, 실수처럼 보이지만 근본적으로 완전히 다름, 범용 해법은 없고, 특수 케이스에 대한(아주 좋은) 휴리스틱만 존재

    • 선형계획보다는 더 까다로운 문제임

    • 혹은 아주 현실적인 문제로 볼 수 있음

답변달기