id: 05817462
dt: j
an: 05817462
au: Law, Yat Chiu; Lee, Jimmy H.M.; Woo, May H.C.
ti: Redundant modeling in permutation weighted constraint satisfaction
    problems.
so: Constraints 15, No. 3, 354-403 (2010).
py: 2010
pu: Springer, Norwell, MA
la: EN
cc: 
ut: weighted constraint satisfaction; WCSP; constraint optimization; model
    redundancy
ci: 
li: doi:10.1007/s10601-009-9075-2
ab: Summary: In classical constraint satisfaction, redundant modeling has been
    shown effective in increasing constraint propagation and reducing
    search space for many problem instances. In this paper, we investigate,
    for the first time, how to benefit the same from redundant modeling in
    weighted constraint satisfaction problems (WCSPs), a common soft
    constraint framework for modeling optimization and over-constrained
    problems. Our work focuses on a popular and special class of problems,
    namely, permutation problems. First, we show how to automatically
    generate a redundant permutation WCSP model from an existing
    permutation WCSP using generalized model induction. We then uncover why
    naively combining mutually redundant permutation WCSPs by posting
    channeling constraints as hard constraints and relying on the standard
    node consistency (NC$^*$) and arc consistency (AC$^*$) algorithms would
    miss pruning opportunities, which are available even in a single model.
    Based on these observations, we suggest two approaches to handle the
    combined WCSP models. In our first approach, we propose $m\text
    {-NC}_{\text c}^*$ and $m\text {-AC}_{\text c}^*$ and their associated
    algorithms for effectively enforcing node and arc consistencies in a
    combined model with $m$ sub-models. The two notions are strictly
    stronger than NC$^*$ and AC$^*$ respectively. While the first approach
    specifically refines NC$^*$ and AC$^*$ so as to apply to combined
    models, in our second approach, we propose a parameterized local
    consistency $\text{LB}(m,Φ)$. The consistency can be instantiated with
    $any$ local consistency $Φ$ for single models and applied to a
    combined model with $m$ sub-models. We also provide a simple algorithm
    to enforce $\text{LB}(m,Φ)$. With the two suggested approaches, we
    demonstrate their applicabilities on several permutation problems in
    the experiments. Prototype implementations of our proposed algorithms
    confirm that applying $2\text {-NC}_{\text c}^*$, $2\text {-AC}_{\text
    c}^*$, and $\text{LB}(2,Φ)$ on combined models allow far more
    constraint propagation than applying the state-of-the-art AC$^*$,
    FDAC$^*$, and EDAC$^*$ algorithms on single models of hard benchmark
    problems.
rv: