A new network simplex algorithm to reduce consecutive degenerate pivots and prevent stalling
الموضوعات : مجله بین المللی ریاضیات صنعتی
Z. ‎Aghababazadeh‎‎
1
(Department of Mathematics, Science and Research Branch, Islamic Azad University, Tehran, Iran.)
M. ‎Rostamy-‎Malkhalifeh‎‎
2
(Department of Mathematics, Science and Research Branch, Islamic Azad University, Tehran, Iran.)
الکلمات المفتاحية: Network flow problem, Network simplex algorithm, Degeneracy, Strong feasible basis, Stalling,
ملخص المقالة :
It is well known that in operations research, degeneracy can cause a cycle in a network simplex algorithm which can be prevented by maintaining strong feasible bases in each pivot. Also, in a network consists of n arcs and m nodes, not considering any new conditions on the entering variable, the upper bound of consecutive degenerate pivots is equal $\left( \begin{array}{c} n-m+k \\ k \\ \end{array} \right)$ where $k$ is the number of degenerate arcs in the basis. As well as, the network simplex algorithm may stall if it goes through some long consecutive degenerate pivot. Through conditions such as (LRC) and (LRS) upon entering variable rules, this upper bound can be reduced to $mn$ and $m^2$ respectively. In this current paper we first suggest a new algorithm for anti--stalling in which a new condition is provided to the entering variable and then show that through this algorithm there are at most $k$ consecutive degenerate pivots.
