This paper compares and analyzes three approaches to solving discrete minimization problems with hard and soft constraints in constraint programming: (i) soft global constraints, (ii) reformulation into linear programs, and (iii) reformulation into local cost functions. (i) offers the advantage of a large constraint list but produces weak lower bounds. (ii) provides strong bounds but the size of the reformulation can be problematic. This paper focuses on (iii) and improves the Soft Arc Consistency (SAC) algorithm, which produces moderate-quality bounds. Specifically, we introduce linear constraints as local cost functions to enhance modeling expressiveness and adapt the existing SAC algorithm to handle linear constraints. Experimental results demonstrate that our approach significantly improves lower bounds and, in some cases, reduces solution times compared to existing algorithms on several benchmarks.
