Polynomially decomposable global cost functions in weighted constraint satisfaction
Refereed conference paper presented and published in conference proceedings


摘要In maintaining consistencies, such as GAC*, FDGAC* and weak EDGAC*, for global cost functions, Weighted CSP (WCSP) solvers rely on the projection and extension operations, which entail the computation of the cost functions' minima. Tractability of this minimum computation is essential for efficient execution. Since projections/extensions modify the cost functions, an important issue is tractable projection-safety, concerning whether minimum cost computation remains tractable after projections/extensions. In this paper, we prove that tractable projection-safety is always possible for projections/extensions to/from the millary cost function (W Ø), and always impossible for projections/extensions to/from n-ary cost functions for n ≥ 2. When n = 1, the answer is indefinite. We give a simple negative example, while Lee and Leung's flow-based projection-safe cost functions are also tractable projection-safe. We propose polynomially decomposable cost functions, which are amenable to tractable minimum computation. We further prove that the polynomial decomposability property is unaffected by projections/extensions to/from unary cost functions. Thus, polynomially decomposable cost functions are tractable projection-safe. We show that the SOFT-AMONG, SOFT-REGULAR, SOFT-GRAMMAR and MAX-WEIGHT/MIN-WEIGHT are polynomially decomposable. They are embedded in a WCSP solver for extensive experiments to confirm the feasibility and efficiency of our proposal. Copyright © 2012, Association for the Advancement of Artificial Intelligence. All rights reserved.
著者Lee J.H.M., Leung K.L., Wu Y.
會議名稱26th AAAI Conference on Artificial Intelligence and the 24th Innovative Applications of Artificial Intelligence Conference, AAAI-12 / IAAI-12
會議地點Toronto, ON
頁次507 - 513

上次更新時間 2020-02-09 於 00:30