摘要
为了提高有序组合树法的运算效率,必须充分利用约束条件中的有关信息.通过深入分析,提出了极差、必选变量、不可选变量等概念,将多个约束条件联系成为一个整体.提出了用检验约束条件的相容性,并以相容性为判据进行截枝的新办法.证明了如果必选变量全部取值为1是可行解,则必是最优解。给出了改进后的有序组合树法的计算步骤流程.
To increase the efficiency of sequential combination tree method, it is necessary to make full use of information in the constraint conditions. Based on a thorough analysis of the method, the concepts such as ultimate difference, necessary variables, and ineligible variables were proposed to combine constraints as a whole. A new algorithm was presented, in which the compatibility of constraints are determined and taken as a criterion to cut branches. It was proved that if all the necessary variables taking 1 is a feasible solution, it is the optimum solution. The flow chart of the new algorithm was presented.
出处
《西南交通大学学报》
EI
CSCD
北大核心
2006年第5期560-566,共7页
Journal of Southwest Jiaotong University
关键词
0-1规划
约束条件
搜索算法
有序组合树
0-1 programming
constraint
searching algorithm
sequential combination tree
