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