Problem Reduction Graph Model for Discrete Optimization Problems

摘要：

The paper proposes the problem reduction graph (PRG), an abstract model for discrete optimization problems which uses structural decomposition to reduce problem complexity and constructs the recurrence relations between the problem and its subproblems. We develop several important algorithm patterns for PRG construction, each leading to a special class of concrete problem-solving algorithms in a systematic way. The model supports logical transformation from specifications to algorithmic programs by deductive inference, and thus significantly promotes the automation and reusability of algorithm design.

关键词： combinatorial optimization problem reduction graph (PRG) algorithm derivation

作者: Yujun Zheng Jinyun Xue

作者单位: State Key Lab of Computer Science,Institute of Software,Chinese Academy of Sciences,Beijing,China Pr State Key Lab of Computer Science,Institute of Software,Chinese Academy of Sciences,Beijing,China Pr

会议类型: 国际会议

会议名称: The Third International Joint Conference on Computational Science and Optimization(第三届计算科学与优化国际大会 CSO 2010)

会议地点: 黄山

会议语种:英文

页码: 190-194

在线出版日期: 2010-05-28（万方平台首次上网日期，不代表论文的发表时间）