An Efficient Approach for Solving Optimization over Linear Arithmetic Constraints
文献类型：期刊论文
| 作者 | Chen, L ; Wu, JZ ; Lv, YR ; Wang, YJ |
| 刊名 | JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY
 |
| 出版日期 | 2016 |
| 卷号 | 31期号:5页码:987-1011 |
| 关键词 | constrained optimization Satisfiability Modulo Theories linear programming |
| ISSN号 | 1000-9000 |
| 中文摘要 | Satisfiability Modulo Theories (SMT) have been widely investigated over the last decade. Recently researchers have extended SMT to the optimization problem over linear arithmetic constraints. To the best of our knowledge, Symba and OPT-MathSAT are two most efficient solvers available for this problem. The key algorithms used by Symba and OPT-MathSAT consist of the loop of two procedures: 1) critical finding for detecting a critical point, which is very likely to be globally optimal, and 2) global checking for confirming the critical point is really globally optimal. In this paper, we propose a new approach based on the Simplex method widely used in operation research. Our fundamental idea is to find several critical points by constructing and solving a series of linear problems with the Simplex method. Our approach replaces the algorithms of critical finding in Symba and OPT-MathSAT, and reduces the runtime of critical finding and decreases the number of executions of global checking. The correctness of our approach is proved. The experiment evaluates our implementation against Symba and OPT-MathSAT on a critical class of problems in real-time systems. Our approach outperforms Symba on 99.6% of benchmarks and is superior to OPT-MathSAT in large-scale cases where the number of tasks is more than 24. The experimental results demonstrate that our approach has great potential and competitiveness for the optimization problem. |
| 英文摘要 | Satisfiability Modulo Theories (SMT) have been widely investigated over the last decade. Recently researchers have extended SMT to the optimization problem over linear arithmetic constraints. To the best of our knowledge, Symba and OPT-MathSAT are two most efficient solvers available for this problem. The key algorithms used by Symba and OPT-MathSAT consist of the loop of two procedures: 1) critical finding for detecting a critical point, which is very likely to be globally optimal, and 2) global checking for confirming the critical point is really globally optimal. In this paper, we propose a new approach based on the Simplex method widely used in operation research. Our fundamental idea is to find several critical points by constructing and solving a series of linear problems with the Simplex method. Our approach replaces the algorithms of critical finding in Symba and OPT-MathSAT, and reduces the runtime of critical finding and decreases the number of executions of global checking. The correctness of our approach is proved. The experiment evaluates our implementation against Symba and OPT-MathSAT on a critical class of problems in real-time systems. Our approach outperforms Symba on 99.6% of benchmarks and is superior to OPT-MathSAT in large-scale cases where the number of tasks is more than 24. The experimental results demonstrate that our approach has great potential and competitiveness for the optimization problem. |
| 收录类别 | SCI |
| 语种 | 英语 |
| WOS记录号 | WOS:000383055100009 |
| 公开日期 | 2016-12-09 |
| 源URL | [http://ir.iscas.ac.cn/handle/311060/17303]  |
| 专题 | 软件研究所_软件所图书馆_期刊论文 |
| 推荐引用方式 GB/T 7714 | Chen, L,Wu, JZ,Lv, YR,et al. An Efficient Approach for Solving Optimization over Linear Arithmetic Constraints[J]. JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY,2016,31(5):987-1011. |
| APA | Chen, L,Wu, JZ,Lv, YR,&Wang, YJ.(2016).An Efficient Approach for Solving Optimization over Linear Arithmetic Constraints.JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY,31(5),987-1011. |
| MLA | Chen, L,et al."An Efficient Approach for Solving Optimization over Linear Arithmetic Constraints".JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY 31.5(2016):987-1011. |
入库方式： OAI收割
来源：软件研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。