● 벤치마크
OR-Tools와 직접 비교했습니다.
같은 문제와 같은 시간 예산을 주고, 모든 해는 문제의 규칙에 따라 다시 채점했습니다. 다른 솔버가 이기거나 비긴 결과도 빼지 않고 실었습니다.
27 / 32
최고 또는 동점
직접 비교한 인스턴스 기준
2
솔버
optimaru, Google OR-Tools
30 s
실행 1회당
모든 솔버에 같은 시간 예산
- optimaru
- OR-Tools
차량 경로 — CVRPLIB Set X
지금까지 알려진 최적해와의 차이입니다. 고객 수 구간(100–1000명)마다 중간 크기 인스턴스를 하나씩 골랐습니다. OR-Tools는 Routing solver에 guided local search를 썼습니다. · 낮을수록 좋음
X-n153-k22
X-n289-k60
X-n491-k59
X-n701-k44
X-n895-k37
계획 문제 — OR-Tools CP-SAT와 비교
스케줄링·배정 문제 12종, 인스턴스 24개입니다. 두 솔버가 같은 모델을 풀었고, 모든 해는 문제의 규칙에 따라 다시 채점했습니다. 표의 값은 승부가 갈린 점수 단계의 벌점입니다. · 낮을수록 좋음
| 문제 | 인스턴스 | optimaru | OR-Tools CP-SAT |
|---|---|---|---|
| 병상 배정 soft | demo 77 stays / 13 beds / 10 rooms | 6,954 | 6,640 최고 |
| 병상 배정 soft | medium 183 stays / 30 beds / 24 rooms | 13,686 최고 | 21,696 |
| 병상 배정 soft | large 551 stays / 61 beds / 48 rooms | 34,556 최고 | 해 없음 |
| 학회 일정 soft | demo demo conference | 54,420 동점 | 54,420 동점 |
| 시설 입지 선정 soft | demo 60 cons / 30 fac | 1,343,284 동점 | 1,343,284 동점 |
| 시설 입지 선정 soft | medium 200 cons / 50 fac | 3,144,802 | 3,099,950 최고 |
| 시설 입지 선정 soft | large 600 cons / 80 fac | 6,498,876 | 6,381,914 최고 |
| 항공 승무원 배정 soft | demo 62 seats / 50 crew / 14 flights | 23,000 동점 | 23,000 동점 |
| 항공 승무원 배정 hard | medium 120 seats / 50 crew / 28 flights | 2 최고 | 11 |
| 항공 승무원 배정 hard | large 236 seats / 50 crew / 56 flights | 21 최고 | 41,471 |
| 생산 라인 순서 계획 soft | demo demo plant | 95,221,284 최고 | 해 없음 |
| 정비 일정 soft | small 14 jobs / 3 crews / 40 dates | 71 | 61 최고 |
| 정비 일정 soft | large 48 jobs / 5 crews / 80 dates | 3,472 최고 | 해 없음 |
| 회의 일정 soft | demo demo (24 meetings) | 3,040 최고 | 해 없음 |
| 오더 피킹 soft | small 22 picks / 2 trolleys | 8,244 동점 | 8,244 동점 |
| 오더 피킹 soft | medium 56 picks / 4 trolleys | 20,478 최고 | 20,488 |
| 프로젝트 일정 soft | demo 24 jobs / 2 projects / 7 res | 7 동점 | 7 동점 |
| 프로젝트 일정 soft | medium 72 jobs / 4 projects / 13 res | 20 동점 | 20 동점 |
| 프로젝트 일정 soft | large 156 jobs / 6 projects / 19 res | 35 | 18 최고 |
| 스포츠 리그 일정 hard | demo demo league | 0 최고 | 13 |
| 업무 배정 soft | demo demo | 10,179,610,011,485 동점 | 10,179,610,011,485 동점 |
| 대회 일정 soft | demo 72 slots / 7 teams / 18 days | 1.55 동점 | 1.55 동점 |
| 대회 일정 soft | large 180 slots / 10 teams / 36 days | 0 최고 | 2 |
| 대회 일정 hard | xlarge 800 slots / 20 teams / 100 days | 0 최고 | 956 |
학교 시간표
모든 제약을 넣은 시간표 모델입니다. 값은 필수 규칙을 모두 지킨 상태에서의 가중 벌점 합계입니다. · 낮을수록 좋음
S · 6학급
M · 12학급
L · 24학급
공개 데이터셋
논문에서 널리 쓰는 표준 인스턴스로 OR-Tools CP-SAT와 비교했습니다.
| 문제 | 지표 | optimaru | OR-Tools CP-SAT |
|---|---|---|---|
| 픽업 · 배송 (Li & Lim 방식 합성 데이터, 요청 200건) | 차량 · 주행 거리 | 43 · 11,300 | no solution |
| 픽업 · 배송 (Li & Lim lc101, 요청 10건) | 주행 거리 | 156.0 동점 | 156.0 |
| 프로젝트 일정 (Patterson Pat1) | 총 소요 기간 | 65 | 62 |
| 빈 패킹 (상자 채우기, t60_00 · u120_04) | 사용한 상자 수 | 21 · 50 동점 | 21 · 50 |
| 조립 라인 밸런싱 (작업 100개 × 3) | 공정 수 | 24 · 22 · 26 | 23 · 22 · 25 |
측정 방법
- 모든 솔버에 같은 인스턴스와 같은 실제 시간 예산을 줍니다. optimaru는 스레드 1개, OR-Tools CP-SAT는 워커 8개를 쓰며, CP-SAT의 시간에는 모델 구성 시간도 포함됩니다.
- 솔버가 보고한 점수를 그대로 믿지 않습니다. 모든 해를 별도의 평가기로 다시 채점해, 모든 솔버를 같은 목적함수로 평가합니다.
- OR-Tools 버전은 9.15입니다.
- 인스턴스와 시드마다 한 번씩, 컴퓨터 한 대에서 잰 결과입니다. 통계적인 연구가 아니라 한 시점의 측정값입니다. 벤치마크 코드는 공개되어 있으니 직접 다시 돌려 보실 수 있습니다.
2026-11-04, Apple M4 Max Mac 한 대(16코어)에서 솔버·인스턴스마다 30초씩 측정했습니다. GitHub의 벤치마크 코드 →