본 논문은 제약 프로그래밍에서 하드 및 소프트 제약 조건을 갖는 이산 최소화 문제를 해결하는 세 가지 접근 방식, 즉 (i) 소프트 글로벌 제약 조건, (ii) 선형 프로그램으로의 재구성, (iii) 로컬 비용 함수로의 재구성을 비교 분석합니다. (i)는 광범위한 제약 조건 목록의 이점을 제공하지만 약한 하한을 생성합니다. (ii)는 강력한 경계를 제공하지만 재구성의 크기가 문제가 될 수 있습니다. 본 논문은 (iii)에 중점을 두고, 중간 품질의 경계를 생성하는 소프트 아크 일관성(SAC) 알고리즘을 개선합니다. 특히, 선형 제약 조건을 로컬 비용 함수로 도입하여 모델링 표현력을 높이고, 기존 SAC 알고리즘을 선형 제약 조건을 처리하도록 적용합니다. 실험 결과, 여러 벤치마크에서 기존 알고리즘에 비해 하한을 크게 개선하고 일부 경우 해결 시간을 단축함을 보여줍니다.
