기술 요약: 누적 제약 조건의 추론에 관하여

문제 정의

누적 제약 조건(Cumulative constraints)은 스케줄링에서 제한된 재생 가능 자원을 모델링하기 위한 제약 프로그래밍(CP)의 핵심 요소입니다. 그러나 표준 전파(propagation) 기법은 일반적으로 각 자원 제약 조건을 독립적으로 다룹니다. 이러한 "단일 자원 관점"은 여러 자원 간의 상호작용을 포착하지 못하며, 이로 인해 특정 벤치마크(예: "3n 문제" 구조)에서 심각한 성능 저하를 초래합니다.

Sidorov 등[2025a]의 "Unite and Lead"(UNL) 접근 방식과 같은 이전의 시도들은 숨겨진 이산 구조(disjunctive structures, 병렬로 실행될 수 없는 작업 집합)를 성공적으로 식별해 냈습니다. 하지만 UNL은 두 가지 결정적인 한계를 가집니다:

1. 일반성 부족: 이산적 추론에 국한되어 있어 더 일반적인 다중 자원 상호작용을 도출할 수 없습니다.
2. 탐색 오버헤드: 탐색 과정에서 이산 클리크(disjunctive cliques)를 찾기 위해 명시적인 프로빙(probing)이 필요하며, 이는 해당 구조가 없는 인스턴스의 경우 솔버의 속도를 10배 가까이 늦추는 상당한 오버헤드를 발생시킵니다.

본 논문이 다루는 핵심 문제는 동적인 클리크 탐지에 따른 탐색 시간 페널티를 지불하지 않으면서, 어떻게 유효한 다중 자원 상호작용을 추론하고 모델을 강화할 것인가 하는 점입니다.

방법론

제안된 접근 방식은 누적 제약 조건을 **점유 벡터(occupancy vectors)**에 대한 선형 부등식으로 재정의하고, 폴리헤드럴 기하학(polyhedral geometry) 및 혼합 정수 프로그래밍(MIP) 기술을 적용하여 루트 노드(전처리 단계)에서 새로운 제약 조건을 추론합니다.

1. 이론적 기초

이 방법은 작업 시작 시간 $s_i$와 지속 시간 $d_i$를 점유 벡터 $\langle s_i | d_i \rangle$로 표현하는 것에 기반합니다. 여기서 벡터는 구간 $[s_i, s_i + d_i)$ 동안 1이고 그 외에는 0입니다. 누적 제약 조건 $\sum r_i \langle s_i | d_i \rangle \le C$는 이처럼 하나의 선형 부등식으로 간주됩니다.

• Lemma 7은 점유 벡터에 의해 정의된 폴리헤드론에 대한 모든 유효한 부등식이 원래의 스케줄링 문제에 대한 유효한 누적 제약 조건에 대응함을 입증합니다.
• 이를 통해 제약 조건 추론 문제를 유효한 절단면(cutting planes)을 생성하는 문제로 취급할 수 있습니다.

2. 리프팅 기반 워크플로우(Lifting-Based Workflow)

이 알고리즘은 동적으로 이산 클리크를 찾는 대신, 세 단계로 구성된 정적 전처리 단계를 수행합니다.

1. 커버 발견(Cover Discovery): 알고리즘은 "커버"(자원 요구량의 합이 용량을 초과하는 작업 집합 $C$, 즉 $\sum_{i \in C} r_i > C$)를 열거합니다. "짧은" 커버(카디널리티 2 및 3)와 "긴" 커버(자원 소비 값에 따라 그룹화됨)를 생성하며, 작업들이 차지하는 최소 메이크스팬(makespan)을 추정하는 용량 경계(capacity bound) 지표($L$)를 기준으로 가장 유망한 후보를 선택합니다.
2. 리프팅(Lifting): 발견된 각 커버에 대해, 알고리즘은 리프팅 절차(Padberg, 1975)를 적용합니다. 이는 기본 커버 부등식($\sum_{i \in C} x_i \le |C| - 1$)을 강화하는 과정으로, 원래 커버에 포함되지 않은 변수들에 대해 부등식 $\sum_{i \in C} x_i + \beta x_j \le |C| - 1$이 여전히 유효하게 유지되는 최대 계수 $\beta$를 결정합니다. 이는 특정 제약 조건 하에서 현재 부등식의 좌변을 최대화하는 보조 하위 문제를 해결함으로써 달성됩니다.
3. 제약 조건 주입(Constraint Injection): 결과로 도출된 리프팅된 부등식들은 다시 새로운 누적 제약 조건으로 변환되어, CP 솔버가 탐색을 시작하기 전에 문제 인스턴스에 주입됩니다.

구현에는 리프팅 하위 문제를 해결하기 위해 Gurobi 12가 사용되었으며, 전처리 시간을 제어하기 위해 생성되는 제약 조건의 수($N_{out}$)와 초기 커버의 수($N_{cover}$)를 제한하였습니다.

주요 기여

• 알고리즘 프레임워크: 유효한 부등식을 통해 다중 자원 상호작용을 포착함으로써, 이산적 추론을 넘어 일반화된 누적 제약 조건 추론을 위한 새로운 방법을 제시합니다.
• 전처리 전략: 동적인 클리크 탐지로 인한 탐색 시간 오버헤드를 피하기 위해 루트 노드 접근 방식을 채택하여, 기존 UNL 방식에서 관찰된 불안정성을 제거했습니다.
• MIP 기술의 통합: 정수 프로그래밍의 리프팅 및 커버 부등식을 스케줄링 도메인에 적용했습니다.
• 품질 지표: 어떤 커버를 리프팅하고 어떤 추론된 제약 조건을 유지할지 선택하기 위한 휴리스틱으로 용량 경계 비율(capacity bound ratio)을 도입했습니다.

실험 결과

본 방법은 최신 솔버(Pumpkin 및 CP-SAT)를 사용하여 표준 RCPSP(736개 인스턴스) 및 RCPSP/max(349개 인스턴스) 벤치마크에서 평가되었습니다.

• 성능 향상:
  • 최적성(Optimality): 최적해까지 도출된 인스턴스의 경우, 리프팅은 해결 시간을 수십 분에서 수 초 미만으로 크게 단축시켰습니다.
  • 탐색 진행(Search Progress): 최적해에 도달하지 못한 인스턴스의 경우, 이 접근 방식은 듀얼 인테그럴(dual integral)(하한값 개선율)을 실질적으로 개선하여 하한값이 더 빠르게 조여짐을 보여주었습니다.
  • 안정성: UNL과 달리 성능 저하(해결 시간 증가)는 드물게 나타났습니다. 단 19쌍의 실행에서만 유의미한 속도 저하가 나타났으며, "2배 저하" 이벤트조차 상위 95백분위수에서만 발생했습니다.
• 새로운 경계값:
  • 이 접근 방식은 **25개의 새로운 하한값(lower bounds)**과 **5개의 새로운 최적해(upper bounds)**를 발견했습니다.
  • 8개의 새로운 하한값은 별도의 탐색 없이 추론된 제약 조건에 의해 직접 검증되었습니다.
• 전처리 오버헤드: 전처리 단계(커버 생성 및 리프팅)는 통상 몇 초밖에 걸리지 않았습니다. 전처리가 1분 이상 소요된 경우는 모두 500개 이상의 작업을 가진 대규모 인스턴스(UBO500/UBO1000)였습니다.
• 제약 유형: 가장 큰 성능 향상은 최적의 추론된 제약 조건이 이산적(단위 용량)인 경우에 관찰되었으나, 일반적인 누적 제약 조건 또한 완만한 개선을 제공했습니다.

의의 및 주장

본 논문은 이 접근 방식이 (숨겨진 구조가 있는 인스턴스에서 상당한 이득을 주는) UNL 방식의 긍정적인 특성을 유지하면서도, (구조가 없는 인스턴스에서의 불안정성과 심각한 속도 저하라는) 주요 약점을 피하는 데 성공했다고 주장합니다.

누적 제약 조건을 폴리헤드럴 기하학의 관점에서 해석함으로써, 이 방법은 유효한 부등식을 통해 모델을 강화하는 체계적인 방법을 제공합니다. 저자들은 이것이 전처리 기술임을 강조합니다. 즉, 솔버를 대체하는 것이 아니라 입력 인스턴스를 강화하는 것입니다. 실험 결과는 리프팅을 통한 제약 조건 추론이, 이전의 동적 프로빙 기술과 관련된 "차수의 격차(order of magnitude)" 수준의 속도 저하 위험 없이, 특히 하한값을 조이고 탐색 노력을 줄이는 데 있어 최신 기술을 발전시키는 견고한 전략임을 시사합니다.