Aria-Opt
최적화 모델을 Aria로 한 번 작성하면 하나의 인터페이스 뒤에서 MILP, QUBO, 배낭 문제 솔버로 보냅니다. HiGHS, CBC, SCIP, GLPK, CP-SAT, 자체 시뮬레이티드 바이퍼케이션 머신, 그리고 Pisinger의 정확한 배낭 알고리즘.
오픈소스 MILP와 QUBO 솔버 전반에 걸쳐 하나의 모델 텍스트를 쓰고 싶은 운영 연구 및 퀀트 팀을 위해.
현재 상태 동작하고 테스트된 것: 모델 IR, 설정, 라우터, QUBO 및 배낭 문제 변환, LP / MPS / QUBO 내보내기, 완전 탐색 오라클. 명세만 있고 아직 구현되지 않은 것: 솔버 어댑터, 시뮬레이티드 바이퍼케이션 적분기, DSL 파서.
배낭 문제, 처음부터 끝까지.
정수 파라미터와 데이터 파일이 모델을 인스턴스화합니다. 라우터가 배낭 문제의 형태를 인식해 정확한 Pisinger 솔버로 보냅니다. 표시된 출력은 그 솔버가 완성됐을 때의 목표 출력입니다.
-- aria: opt
maximize sum i from 0 to n - 1 { p[i] * x[i] }
subject to capacity: sum i from 0 to n - 1 { w[i] * x[i] } <= C
$ aria-opt solve knapsack.aria --model Knapsack --int n=8 \
--data knapsack_8.json
status OPTIMAL obj 1458 bound 1458 gap 0.000% [knapsack]상용 솔버를 써 보셨다면 익숙하게 느껴질 겁니다.
하나의 인터페이스
모든 솔버가 같은 Solver 트레이트를 구현합니다. 호출하는 쪽은 백엔드별 타입을 볼 일이 없습니다.
이미 알고 있는 파라미터 이름
time_limit, mip_gap, threads, seed 등. 다른 흔한 표기도 별칭으로 받습니다. 지원하지 않는 파라미터는 경고를 내며, 조용히 의미가 바뀌는 일은 없습니다.
솔버가 보는 것을 그대로 볼 수 있음
코어에서 정수는 비트로, 제약은 페널티로 바뀌며 그 과정의 보고서를 확인할 수 있습니다. 그래서 QUBO 솔버와 MILP 솔버가 같은 모델을 풉니다.
모든 예제에 정답지
제공되는 모든 예제에 오라클이 붙어 있습니다: 완전 탐색, 동적 계획법, 또는 솔버 간 일치. aria-opt verify가 수락 게이트입니다.
연결 중인 솔버들.
- MILP / CPHiGHS, COIN-OR CBC, SCIP, GLPK, OR-Tools CP-SAT.
- 시뮬레이티드 바이퍼케이션변환 후 QUBO를 위한 단열(aSB), 탄도(bSB), 이산(dSB) SB. GPU 가속은 이후에.
- 배낭 문제0-1 및 유계 배낭 문제를 위한 Pisinger의 expknap과 minknap.
- QUBO 휴리스틱시뮬레이티드 어닐링과 타부 탐색, 그리고 참조 오라클로서의 완전 탐색(현재 동작).