摘要
本文对可靠性网络中串-并系统的费用最小化问题提出一种新的分枝定界算法.我们根据这类网络的特殊结构和性质,建立了新的最优性必要条件,在分枝搜索过程中增加新的剪枝准则,从而加速了算法的收敛速度.有效的数值试验表明,该算法可求解大规模可靠性网络的费用最小化问题.
In this paper we propose a new branch and bound algorithm for cost minimization problems arising in series-parallel reliability networks. By exploiting the special structures of the network, we derive a new necessary optimality condition. A new fathoming rule is introduced in the process of branch and search to prune the nodes in an early stage before the subproblem is solved. This fathoming rule speeds up the convergence of the algorithm. Valid numerical results show that the proposed branch and bound algorithm can solve large-scale cost minimization problems.
出处
《应用数学与计算数学学报》
2005年第1期39-45,共7页
Communication on Applied Mathematics and Computation
关键词
可靠性网络
费用最小化
分枝定界算法
非线性整数规划
连续松弛
冗余分配
Series-parallel reliability network, redundancy, cost minimization, nonlinear integer programming, branch and bound, continuous relaxation
