OGC 2026 Autonomous Research System

블록은 베이 격자 위에 층으로 쌓이고, 크레인은 수직으로만 움직입니다. 블록을 층 k에 내리면 풋프린트가 겹치는 기존 블록의 j ≥ k 높이 영역을 그대로 통과합니다. 그래서 풋프린트가 겹치는 두 블록은 같은 시간에 작업할 수 없고, 겹치지 않는 블록만 병렬로 진행됩니다.

목적함수는 세 항의 가중합입니다. 총 납기 지연 Z1, 베이 간 작업량 불균형 Z2, 베이 선호도 페널티 Z3을 `min w1·Z1 + w2·Z2 + w3·Z3`으로 묶습니다. w1이 약 26667로 지배적이라 납기 지연이 사실상 주 지표입니다. 채점은 인스턴스마다 별도 서브프로세스에서 CPU 4개, RAM 16GB, 인터넷 연결 없이 실행됩니다.

알고리즘을 한 번 실행하는 일은 자동화할 수 있었지만, 다음 가설을 만들고 후보 코드를 평가해 더 나은 결과만 남기려면 계속 사람의 판단이 필요했습니다. 실패한 후보가 계산 자원을 낭비하거나 기존 결과를 훼손하지 않도록, 실험 전체의 제어 경계를 먼저 세웠습니다.

가설 생성, 후보 구현, sandbox 실행, 공식 채점기 평가, holdout·stress 검증과 승격을 한 흐름으로 연결했습니다. 후보는 기존 결과와 분리해 실행하고, 검증 게이트를 통과해 실제로 개선된 경우에만 다음 기준으로 승격하도록 구성했습니다.

루프는 방향을 바꾸는 판단도 남깁니다. 2026-05-29에는 ALNS와 restricted-MIP 조합을 폐기하고 CP-SAT 포트폴리오로 전향했습니다.

제출 엔트리포인트는 6개 솔버 암을 각각 독립 서브프로세스로 동시에 실행한 뒤, 공식 목적함수 기준 최솟값을 고릅니다. 암은 `cpsat`, `v8r`, `greedy`, `alns`, `cpinterval`, `serial`이고, `serial`은 언제나 실행 가능한 해를 보장하는 기준선입니다. 빈 해나 무효 해가 제출되지 않도록 구조 자체를 feasible-by-construction으로 두었습니다.

다수 베이·대규모 인스턴스에서는 `cpinterval`이 이겼습니다. MDD 기준으로 베이를 나누고, 베이마다 `[entry, exit)` interval 변수로 CP-SAT 모델을 세우고, 크레인 j ≥ k 풋프린트 중복 제약을 시공간 비연접으로 인코딩합니다. 회전과 (x, y) 위치를 결정변수로 두어, 중복을 피하면서 동시 작업 여지를 남겼습니다.

여기에 재조정 두 단계를 직렬로 붙였습니다. `fold`는 블록 250개 이상이면서 베이가 정확히 4개인 인스턴스에서 발동해, 블록-베이 할당을 국소 탐색으로 바꾸고 영향받은 베이만 다시 풉니다. `offload`는 지연이 한 베이에 몰린 인스턴스에서 지연 기여도 상위 블록을 다른 베이로 옮깁니다. 둘 다 공식 목적함수가 나아진 경우에만 채택합니다.

파이프라인은 안전 휴리스틱, 최선 ALNS, MIP 보수 세 해 가운데 실행 가능성 게이트를 통과한 해의 목적함수 최솟값만 반환합니다. 어떤 단계가 오작동해도 안전 휴리스틱보다 나쁜 해가 나갈 수 없는 구조입니다. 94케이스 전체 평가에서 오류 0건, 파국적 출력 0건, 회귀 유출 0건을 기록했고, 변형 반복까지 누적하면 기록된 250회 이상의 인스턴스 실행에서 회귀 유출이 없었습니다. 최종 목표는 알고리즘 개선 실험을 24시간 사람 개입 없이 반복할 수 있는 연구 시스템이었습니다.

`prob_1`, `prob_2`, `prob_8`은 gap 0으로 최적해임을 확인했습니다. 경합 없는 납기 지연 하한(LB=0)과 Z2·Z3에 대한 할당 전용 CP-SAT 완화 하한을 합한 값이 현재 해와 일치했고, 세 모델을 교차로 대조했습니다. `fold`는 `prob_13`, `prob_15`, `prob_16`, `prob_17`, `prob_18`, `prob_19`에서, `offload`는 `prob_9`, `prob_10`, `prob_12`, `prob_13`, `prob_15`, `prob_19`에서 개선을 만들었습니다. 특정 4-베이 인스턴스에서는 연산 시간을 5배 준 단일 탐색보다 `fold` 쪽이 나은 목적함수를 냈습니다.

여기 적힌 수치는 주최 측이 공개한 학습용 인스턴스 20개 기준입니다. 실제 채점은 비공개 테스트셋으로 이뤄지므로 이 값들이 순위를 뜻하지 않으며, 대회는 참가로 마쳤습니다.