An efficient method to transform a sat problem to a mixed integer linear programming problem
文献类型：会议论文
| 作者 | Guo, Wenxia1; Wang, Jin2; He, Majun1; Ren, Xiaoqin1; Wang, Qingxian1; Tian, Wenhong1
|
| 出版日期 | 2018 |
| 会议日期 | December 7, 2018 - December 10, 2018 |
| 会议地点 | Chengdu, China |
| DOI | 10.1109/CompComm.2018.8780844 |
| 页码 | 1992-1996 |
| 英文摘要 | There exists a method to reduce a 3-SAT (Satifiability) problem to a Subset Sum Problem (SSP) in the literature, however, it can only be applied to small or medium size problems. Our study is to find an efficient method to transform general SAT problems to binary integer linear programming (BILP) problems in larger size. Observing the feature of variable-clauses constraints in SAT, we apply linear inequality model (LIM) to the problem and propose a method called LIMSAT which is based on the reduction from 3SAT to Sub-set Sum problem (SSP). Being different from the classical one, the new method treats each bit as an element in the matrix of SSP, sets matrix as A without those slack variables, sets b as the target value and x as the binary solution. Therefore, we build the model as \mathbf{xA}\leq \mathbf{b}. The experimental results show that the new method works efficiently for very large size problems with thousands of variables and clauses and has comparable performance against the best solver tested by one of the hardest SAT 2016 competition benchmarks. © 2018 IEEE. |
| 会议录 | 4th IEEE International Conference on Computer and Communications, ICCC 2018
 |
| 语种 | 英语 |
| 源URL | [http://119.78.100.138/handle/2HOD01W0/9775]  |
| 专题 | 中国科学院重庆绿色智能技术研究院 |
| 作者单位 | 1.School of Information and Software Engineering, University of Electronic Science and Technology of China, Chengdu, China; 2.Chongqing Institute of Green and Intelligent Technology, Chinese Academy of Sciences, Chongqing, China |
| 推荐引用方式 GB/T 7714 | Guo, Wenxia,Wang, Jin,He, Majun,et al. An efficient method to transform a sat problem to a mixed integer linear programming problem[C]. 见:. Chengdu, China. December 7, 2018 - December 10, 2018. |
入库方式： OAI收割
来源：重庆绿色智能技术研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。