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 know...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 SVMBA 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 reMly 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 Mgorithms 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.展开更多
基金This work is supported by the National Natural Science Foundation of China under Grant No. 61170072, and the Chinese Academy of Sciences/State Administration of Foreign Experts Affairs （CAS/SAFEA） International Partnership Program for Creative Research Teams.
文摘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 SVMBA 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 reMly 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 Mgorithms 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.
