微信服务号

微信订阅号

2025年4月6日 18:17 星期日
首页 > 过刊浏览>2017年第28卷第10期 >2525-2538. DOI:10.13328/j.cnki.jos.005133
PDF HTML阅读 XML下载 导出引用 引用提醒
基于混合搜索的含逻辑“与”“或”的RM优化算法
作者:
基金项目:

中国科学院-国家外国专家局创新团队国际合作伙伴计划；国家自然科学基金（61170072）；青年科学基金（61303057）


Hybrid Search Method for Rate-Monotonic Optimal Problem with Logic OR AND Constraints
Author:
  • LÜ Yin-Run

    LÜ Yin-Run

    State Key Laboratory of Computer Science (Institute of Software, The Chinese Academy of Sciences), Beijing 100190, China;National Engineering Research Center for Fundamental Software, Institute of Software, The Chinese Academy of Sciences, Beijing 100190, China;University of Chinese Academy of Sciences, Beijing 100190, China
    在期刊界中查找
    在百度中查找
    在本站中查找
  • CHEN Li

    CHEN Li

    State Key Laboratory of Computer Science (Institute of Software, The Chinese Academy of Sciences), Beijing 100190, China;National Engineering Research Center for Fundamental Software, Institute of Software, The Chinese Academy of Sciences, Beijing 100190, China;University of Chinese Academy of Sciences, Beijing 100190, China
    在期刊界中查找
    在百度中查找
    在本站中查找
  • WANG Chong

    WANG Chong

    State Key Laboratory of Computer Science (Institute of Software, The Chinese Academy of Sciences), Beijing 100190, China;National Engineering Research Center for Fundamental Software, Institute of Software, The Chinese Academy of Sciences, Beijing 100190, China;University of Chinese Academy of Sciences, Beijing 100190, China
    在期刊界中查找
    在百度中查找
    在本站中查找
  • WU Jing-Zheng

    WU Jing-Zheng

    National Engineering Research Center for Fundamental Software, Institute of Software, The Chinese Academy of Sciences, Beijing 100190, China;University of Chinese Academy of Sciences, Beijing 100190, China
    在期刊界中查找
    在百度中查找
    在本站中查找
  • WANG Yong-Ji

    WANG Yong-Ji

    State Key Laboratory of Computer Science (Institute of Software, The Chinese Academy of Sciences), Beijing 100190, China;National Engineering Research Center for Fundamental Software, Institute of Software, The Chinese Academy of Sciences, Beijing 100190, China;Laboratory for Interact Software Technologies, Institute of Software, The Chinese Academy of Sciences, Beijing 100190, China;University of Chinese Academy of Sciences, Beijing 100190, China
    在期刊界中查找
    在百度中查找
    在本站中查找
Fund Project:

The CAS/SAFEA Int’l Partnership Program for Creative Research Teams; National Natural Science Foundation of China (61170072); Youth Science Foundation (61303057)

  • 摘要
    • | |
  • 访问统计
    • |
  • 参考文献
    • |
  • 相似文献
    • |
  • 引证文献
    • | |
  • 文章评论
    摘要:

    相对于标准约束优化问题，广义约束优化问题（或称析取优化问题）的等式或不等式约束条件中不仅包含逻辑“与”关系，还含有逻辑“或”关系.单调速率（RM）优化问题是广义约束优化问题的一个重要应用.目前RM优化问题已有的解法包括函数变换、混合整数规划、线性规划搜索等算法.随着任务数的增多，这些算法的求解时间较长.提出一种基于线性规划的深度广度混合搜索算法（LPHS），将广义约束优化问题拆分成若干子问题，建立线性规划搜索树，合理选择搜索顺序，利用动态剪枝算法减小子问题的规模，最终求得最优解.实验结果表明，LPHS算法比其他方法有明显的效率提升.研究成果与计算机基础理论中的可满足性模理论的研究相结合，有助于提高可满足性模理论问题的求解效率，促进该理论在程序验证、符号执行等领域的进一步应用.

    Abstract:

    The logic relationship among equality and inequality constraints in a standard constrained optimization problem (SCOP) is only logic AND, however in a generalized constrained optimization problem (GCOP) it contains not only logic AND but also logic OR.GCOP is also known as disjunctive programming problem.The rate-monotonic (RM) optimal problem is an important instance of GCOP.Existing methods for the RM optimal problem include function transformation, mixed integer programming and linear programing search.But all these methods are not efficient enough with the increase of task volume.A linear programming based hybrid search (LPHS) method is proposed in this paper.First GCOP problem is partitioned into linear problemming sub-problems, and a linear search tree is constructed.Next, this tree is searched by the strategy of mixing depth-first-search and breadth-first-search, and an efficient pruning method is used during search progress.Then, the optimal solution is achieved.Experimental results illustrate that LPHS method is much more efficient than others.This work is related to satisfiability modulo therories (SMT), and is expected to improve the efficiency of SMT solvers and to promote applications of SMT in software verification, symbolic excecution and other fields.

    参考文献
    相似文献
    引证文献
引用本文

吕荫润,陈力,王翀,吴敬征,王永吉.基于混合搜索的含逻辑“与”“或”的RM优化算法.软件学报,2017,28(10):2525-2538

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2016-03-16
  • 最后修改日期:2016-08-09
  • 在线发布日期: 2016-10-19
文章二维码
友情链接:中国科学院软件研究所中国计算机学会中国科学院国家自然科学基金委员会CCF数字图书馆Int'l J of Softw Info计算机系统应用
您是第位访问者
版权所有：中国科学院软件研究所 京ICP备05046678号-3
地址：北京市海淀区中关村南四街4号,邮政编码：100190
电话：010-62562563 传真：010-62562533 Email：jos@iscas.ac.cn
技术支持：北京勤云科技发展有限公司

京公网安备 11040202500063号