Abstract:
In the Temporal Constraint Optimization Problem(TCOP), the general optimization methods are inefficient. So this paper gives an efficient method for solution space contraction of TCOP by setting up a Dual Temporal Constraint Network(DTCN) and the method is a variation of Path Consistency(PC), so the efficient solution space contraction technique enables to discern the existence of feasible solution and eliminates some non-feasible solutions. Experimental results show that this method can reduce the steps of calculation and improve the efficiency of optimization algorithm.
Key words:
Temporal Constraint Optimization Problem(TCOP),
solution space contraction,
Dual Temporal Constraint Network(DTCN),
Simple Temporal Network(STN),
feasible solution extended algorithm,
restraint variable-dimension method
摘要： 在对时间约束优化问题的求解中，普通优化方法的计算效率较低。为此，提出一种时间约束优化问题的解空间压缩方法。获得其对偶时间约束网络，结合路径一致性的求解方法，判断可行解的存在性并剔除非可行解。实验结果表明，该方法能有效减少迭代次数，提高计算效率。
关键词:
时间约束优化问题,
解空间压缩,
对偶时间约束网络,
简单时间网络,
可行解扩展算法,
约束变尺度法
CLC Number:
ZHANG Bo-Xiang, SHU Yan-An, YANG Feng. Research on Solution Space Contraction Method for Temporal Constraint Optimization Problem[J]. Computer Engineering, 2012, 38(14): 262-265.
张博洋, 朱延广, 杨峰. 时间约束优化问题的解空间压缩方法研究[J]. 计算机工程, 2012, 38(14): 262-265.