# ④ RAG · Search · Structured Output · Optimization — 사례 적용 리포트

## 적용 사례와 범위

Google OR-Tools 공식 공개 knapsack 예제에 기존 네 도구를 연결했습니다. 50개 항목에서 단일 예산을 넘지 않으면서 가치 합계를 최대화합니다.

공개 예제 검증입니다. 실제 제조 현장 데이터, 외부 LLM 품질, 해커톤 규정 적합성을 검증한 결과로 표현하지 않습니다.

## 적용 설계

전체 흐름은 공식 근거 확보 → 검색 → citation 확인 → 구조 검증 → 제약 최적화 → 독립 비교입니다.

Generator는 deterministic literal extractor입니다. 다운로드한 Python 코드를 실행하지 않고 AST literal을 읽습니다. RAG status는 generated_unverified로 유지하며, citation membership만으로 의미적 정답을 보장하지 않습니다.

## 실행 과정

기록된 순서를 보여줍니다. 단계별 실행 시간은 측정하지 않았으므로 시간축 길이로 표현하지 않습니다. 보고서는 기록된 결과를 읽으며 solver나 테스트를 재실행하지 않습니다.

| 순서 | 작업 | 실행 근거 |
| --- | --- | --- |
| 1 | 기존 구현·테스트 확인 | main 기준 기존 56개 통과 |
| 2 | 실패 입력 재현 | 중복 JSON 키·NaN 통과 확인 |
| 3 | 공개 사례 연결 | 네 도구 연결·문서 순서 반전 결과 일치 |
| 4 | 보완·회귀 검증 | 추가 8개 포함 최종 64개 통과 |
| 5 | 독립 최적성 검증 | HiGHS status 0, gap 0; 목적값 일치 |
| 6 | 결과 동결·병합 | PR #5 병합; 원본 해시·로그·JSON 보존 |

## 실측 결과

동적계획법과 별도의 HiGHS MILP가 같은 최적 목적값을 얻었습니다. 동일한 항목 집합을 선택해야 한다는 조건은 두지 않았습니다.

Runner 시간은 Python 프로세스 시작 시간을 제외하고 SciPy import와 독립 검증을 포함합니다. 검색·LLM latency나 대규모 서비스 성능으로 해석하지 않습니다.

| 지표 | 측정값 |
| --- | --- |
| 항목 수 | 50 |
| 예산 한도 / 사용 | 850 / 850 |
| Kit 목적값 | 7,534 |
| 독립 HiGHS 목적값 | 7,534 |
| HiGHS status / gap | 0 / 0 |
| 기록된 runner 시간 | 0.386095초 |

## 검증과 개선

기존 56개 + 추가 8개 = 총 64개 테스트가 실제 통과했습니다. 100개의 seeded 소형 합성 문제는 완전탐색 oracle과 일치했습니다. 이 100개는 공개 사례와 별도 검증입니다.

최종 병합 때 GitHub CI check/status 실행 기록은 없었습니다. 로컬 suite 결과와 CI를 구분합니다. HTML 구조·다운로드·수치 일관성은 확인했으며 브라우저 픽셀 QA는 미완료입니다.

| 실패 경로 | 보완·검증된 동작 |
| --- | --- |
| 근거 없음 | generator 호출 없이 insufficient_evidence |
| 잘못된 citation | ValueError로 거부 |
| 구조 불일치 | schema에서 거부; solver 입력으로 사용하지 않음 |
| 중복 키·NaN·Infinity | 모호하거나 비유한 payload 거부 |
| 잘못된 limit·비용·중복 ID | 입력 검증 실패 |
| 목적값 overflow | 최적값으로 기록하지 않고 거부 |

## 항목별 결정

선택 집합의 비용과 가치 합계를 원본 literal에서 다시 계산해 기록값과 비교했습니다.

| ID | 비용 | 가치 | 결정 |
| --- | --- | --- | --- |
| 0 | 7 | 360 | 선택 |
| 1 | 0 | 83 | 선택 |
| 2 | 30 | 59 | 제외 |
| 3 | 22 | 130 | 선택 |
| 4 | 80 | 431 | 선택 |
| 5 | 94 | 67 | 제외 |
| 6 | 11 | 230 | 선택 |
| 7 | 81 | 52 | 제외 |
| 8 | 70 | 93 | 제외 |
| 9 | 64 | 125 | 제외 |
| 10 | 59 | 670 | 선택 |
| 11 | 18 | 892 | 선택 |
| 12 | 0 | 600 | 선택 |
| 13 | 36 | 38 | 제외 |
| 14 | 3 | 48 | 선택 |
| 15 | 8 | 147 | 선택 |
| 16 | 15 | 78 | 선택 |
| 17 | 42 | 256 | 선택 |
| 18 | 9 | 63 | 선택 |
| 19 | 0 | 17 | 선택 |
| 20 | 42 | 120 | 제외 |
| 21 | 47 | 164 | 선택 |
| 22 | 52 | 432 | 선택 |
| 23 | 32 | 35 | 제외 |
| 24 | 26 | 92 | 선택 |
| 25 | 48 | 110 | 제외 |
| 26 | 55 | 22 | 제외 |
| 27 | 6 | 42 | 선택 |
| 28 | 29 | 50 | 선택 |
| 29 | 84 | 323 | 선택 |
| 30 | 2 | 514 | 선택 |
| 31 | 4 | 28 | 선택 |
| 32 | 18 | 87 | 선택 |
| 33 | 56 | 73 | 제외 |
| 34 | 7 | 78 | 선택 |
| 35 | 29 | 15 | 제외 |
| 36 | 93 | 26 | 제외 |
| 37 | 44 | 78 | 제외 |
| 38 | 71 | 210 | 선택 |
| 39 | 3 | 36 | 선택 |
| 40 | 86 | 85 | 제외 |
| 41 | 66 | 189 | 선택 |
| 42 | 31 | 274 | 선택 |
| 43 | 65 | 43 | 제외 |
| 44 | 0 | 33 | 선택 |
| 45 | 79 | 10 | 제외 |
| 46 | 20 | 19 | 제외 |
| 47 | 65 | 389 | 선택 |
| 48 | 52 | 276 | 선택 |
| 49 | 13 | 312 | 선택 |

## 해석과 남은 검증

검증 완료: lexical Search, 근거/citation contract, strict top-level payload, 단일 정수 예산 solver, 독립 최적값 비교.

미검증: 외부 LLM 답변 품질, semantic retrieval, 한국어 검색 품질, prompt injection 내성, 실제 생산 데이터, 대규모 runtime·memory.

재사용률은 측정하지 않았으며 70% 달성을 주장하지 않습니다. 단일 예산 solver를 일반 MILP나 routing solver로 표현하지 않습니다. CHO-FAM 정규 학습 일정은 변경하지 않습니다.

## 근거와 다운로드

공식 source SHA-256: 8c51a495028e63eb423964092fa12118db019c0f4ff045e1598cf32ba1dfba09

공식 source commit: 100f66e6242ab8bf8d32feb8f3bf086db66ae2b5

Python 3.12.14 · SciPy 1.17.0 · 독립 엔진: SciPy/HiGHS

HTML과 Markdown은 같은 기록된 JSON과 테스트 로그를 사용합니다. 실행 중 원본을 바꾸거나 신규 성능을 생성하지 않습니다.


공식 source: https://github.com/google/or-tools/blob/100f66e6242ab8bf8d32feb8f3bf086db66ae2b5/ortools/algorithms/samples/knapsack.py