Propagating Polynomially (Integral) Linear Projection-Safe Global Cost Functions in WCSPs
Refereed conference paper presented and published in conference proceedings


引用次數
替代計量分析
.

其它資訊
摘要Lee and Shum consider cost functions that are Polynomially Linear Projection-Safe (PLPS), but whose minimum cost computation is usually NP-hard. They suggest how such cost functions can still be efficiently propagated using relaxed forms of common consistencies. In this paper, we show that conjunctions of PLPS cost functions are still PLPS, and Lee and Shum's relaxed consistency method is applicable to give better runtime behavior. We further introduce Polynomially Integral Linear Projection-Safe (PILPS) cost functions, a subclass of PLPS cost functions, which have (a) linear formulations with size polynomial to the number of variables and domain sizes, (b) optimal solutions of the linear relaxation always being integral and (c) the last two conditions unaffected by projections/extensions, even though the operations modify the structure of cost functions. We show that conjunctions of PILPS cost functions are PLPS, which still satisfy conditions (a) and (c). Given a standard WCSP consistency alpha, we give theorems showing that maintaining relaxed alpha on a conjunction of PILPS cost functions is stronger than maintaining alpha on the individual cost functions. A useful application of our method is on some PILPS global cost functions, whose minimum cost computations are tractable and yet those for their conjunctions are not. Experiments are conducted to confirm empirically that maintaining relaxed consistencies on the conjoined cost functions is orders of magnitude more efficient, both in runtime and search space reduction, than maintaining the corresponding standard consistencies on the individual cost functions.
著者Lee JHM, Leung KL, Shum YW
會議名稱IEEE 24th International Conference on Tools with Artificial Intelligence (ICTAI)
會議開始日07.11.2012
會議完結日09.11.2012
會議地點Athens
會議國家/地區希臘
期刊名稱2011 23RD IEEE INTERNATIONAL CONFERENCE ON TOOLS WITH ARTIFICIAL INTELLIGENCE (ICTAI 2011)
詳細描述organized by Nikolaos Bourbakis,
出版年份2012
月份1
日期1
出版社IEEE
頁次9 - 16
電子國際標準書號978-0-7695-4915-6
國際標準期刊號1082-3409
語言英式英語
Web of Science 學科類別Computer Science; Computer Science, Artificial Intelligence; Engineering; Engineering, Electrical & Electronic

上次更新時間 2020-24-10 於 01:59