Mv
M.J.C. van Leest
info
Please Note
<p>This page displays the records of the person named above and is not linked to a unique person identifier. This record may need to be merged to a profile.</p>
1 records found
1
Strong Bridges for the Circuit Constraint
Implementing and Evaluating Strong Bridge Detection in a Lazy Clause Generation Solver
Constraint Programming with Lazy Clause Generation (LCG) relies on effective propagation to reduce the search space. We study the integration of strong bridge detection into a circuit propagator, where strong bridges identify edges that must be present to maintain strong connectivity in the graph induced by current domains. Compared to a baseline that only prevents subcycles, this approach substantially reduces search effort, with reductions of up to three orders of magnitude in the satisfaction setting and one order of magnitude in the optimization setting. These gains often translate into runtime improvements, particularly for satisfaction. The extension also produces shorter nogoods, while its effect on LBD is mixed, reflecting more global explanations. Overall, the results demonstrate that identifying necessary edges is an effective way to strengthen propagation and significantly reduce the explored search space.
...
Constraint Programming with Lazy Clause Generation (LCG) relies on effective propagation to reduce the search space. We study the integration of strong bridge detection into a circuit propagator, where strong bridges identify edges that must be present to maintain strong connectivity in the graph induced by current domains. Compared to a baseline that only prevents subcycles, this approach substantially reduces search effort, with reductions of up to three orders of magnitude in the satisfaction setting and one order of magnitude in the optimization setting. These gains often translate into runtime improvements, particularly for satisfaction. The extension also produces shorter nogoods, while its effect on LBD is mixed, reflecting more global explanations. Overall, the results demonstrate that identifying necessary edges is an effective way to strengthen propagation and significantly reduce the explored search space.