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.‎
