본 논문은 계산적으로 어려운 조합 최적화 문제를 해결하기 위한 일반적인 프레임워크인 암묵적 히팅 집합(IHS) 접근 방식을 소개합니다. IHS는 비일관성의 원천을 추출하는 결정 오라클과 누적된 비일관성 원천에 대한 히팅 집합(HS)을 계산하는 최적화 도구 사이에서 반복합니다. 결정 오라클은 언어별로 다르지만, 최적화 도구는 일반적으로 정수 프로그래밍을 통해 구현됩니다. 본 논문에서는 의사 부울(PB) 추론 및 확률적 지역 탐색을 활용한 히팅 집합 최적화를 위한 대체 알고리즘 기법을 탐구합니다. 특히, IHS의 가장 최근 구현 중 하나인 의사 부울(0-1 IP) 최적화의 맥락에서 이러한 대체 기법들의 실용적 타당성을 광범위하게 평가합니다. 효율성과 신뢰성 사이의 상충 관계를 강조하면서, 상업용 IP 솔버가 HS 계산을 구현하는 가장 효과적인 방법으로 남아있지만, 수치적 불안정성으로 인해 정확성 문제가 발생할 수 있음을 보여줍니다. PB 추론을 통한 정확한 HS 계산이 수치적으로 정확한 IP 솔버와 경쟁할 수 있음을 입증하며, PB 추론을 HS 계산의 기반으로 사용하면 IHS 계산의 정확성에 대한 인증서를 얻을 수 있습니다. 이는 사용된 선언적 언어의 추론이 PB 기반 증명 형식으로 캡처될 수 있는 모든 IHS 구현에 일반적으로 적용될 수 있습니다.
