About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Mathematical Programming
Paper
The zero pivot phenomenon in transportation and assignment problems and its computational implications
Abstract
Transportation and assignment models have been widely used in many applications. Their use was motivated, among other reasons, by the existence of efficient solution methods and their occurrence as sub-problems in the solution of combinatorial problems. A previous study [10] observed that, in large-scale Transportation and Assignment Problems, 95 percent of the pivots were zero or degenerate pivots. This study investigates the ratio of zero pivots to the total number of pivots and verifies the above observation under conditions of small rim variability. Rules are introduced that pay special attention to the zero pivot phenomenon, and significantly reduce CPU time in both phase-1 (generating the initial basic feasible solution) and in phase-2 (selecting the variable leaving the base and the variable entering the base). When these rules were applied, they reduced the CPU time substantially: a 500×500 assignment problem was solved in 1.3 seconds. © 1977 The Mathematical Programming Society.