期刊
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS
卷 E98D, 期 6, 页码 1121-1127出版社
IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG
DOI: 10.1587/transinf.2014FOP0007
关键词
reduced ordered BDD; Pesudo-Boolean constraint; optimization problem
资金
- Austrian Science Fund (FWF) [I963]
- Japan Society for the Promotion of Science
- Grants-in-Aid for Scientific Research [26330248] Funding Source: KAKEN
- Austrian Science Fund (FWF) [I963] Funding Source: Austrian Science Fund (FWF)
Pseudo-Boolean (PB) problems are Integer Linear Problem restricted to 0-1 variables. This paper discusses on acceleration techniques of PB-solvers that employ SAT-solving of combined CNFs each of which is produced from each PB-constraint via a binary decision diagram (BDD). Specifically, we show (i) an efficient construction of a reduced ordered BDD (ROBDD) from a constraint in band form l <= < Linear term > <= h, (ii) a CNF coding that produces two clauses for some nodes in an ROBDD obtained by (i), and (iii) an incremental SAT-solving of the binary/alternative search for minimizing values of a given goal function. We implemented the proposed constructions and report on experimental results.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据