极小化有限个阶梯函数和的一种分枝定界算法

A branch-and-bound algorithm for minimizing a finite sum of staircase function under linear constraints

该文首先给出了求在线性约束下极小化有限个阶梯函数和的一种分枝定界算法。该算法是Ｂｒｏｎｓｔｅｉｎ和Ｒｕｓｔ所提算法的扩展。文中的关键是给出了一种新的目标函数的线性化方法。其次证明了该算法的收敛性并对计算量进行了粗略的估计，同时给出了一些数值例子。计算结果表明该算法是可行的、有效的。

This paper first presents a branch-and-bound algorithm to minimize a finite sum of stair-case functions under linear constraints.The algorithm is an extension of the method presentedby Bornstein and Rust.The key of the paper is to present a new linearization method of theobjective function.Then the convergence of the algorithm is proved, the computational com-plexity is discussed,and some numerical results are given. Computational results show that thealgorithm is feasible and efficient.