Research Reports from the Department of Operations
Document Type
Report
Publication Date
1-1-1988
Abstract
The rudimentary primal algorithm (RPA) is a simple and convenient algorithm to solve all-integer integer programs; its considerably more complex alternative is the "simplified primal algorithm" (SPA) of Young [3] and Glover [1]. The RPA has not been demonstrated to converge, however; Mathis [3] and Salkin [4] have in fact presented counterexamples for which it cycles indefinitely with period six. The counterexamples depend critically, though, on a rigid choice of the "optimal" pivot columns; Mathis' example converges if alternative columns are selected, and we observe here that Salkin's converges quickly too. The issue thus remained open whether the RPA might not yet yield a convergent algorithm when combined with an appropriate column selection procedure. In this paper we settle the issue negatively, with an improved counterexample. We describe a method for generalizing and modifying linear programs, and use it to obtain from Salkin's counterexample a new one which again cycles indefinitely with period six, but which in contrast has a unique possible pivot column at each tableau. Thus neither the RPA nor any simple variant of the RPA will converge on this counterexample, and added complexities as of the SPA are essential.
Keywords
Operations research, Algorithms, Integer programming, Mathematical optimization, Computational complexity
Publication Title
Technical Memorandums from the Department of Operations, School of Management, Case Western Reserve University
Issue
Technical memorandum no. 676
Rights
This work is in the public domain and may be freely downloaded for personal or academic use
Recommended Citation
Haas, Robert; Mathur, Kamlesh; and Salkin, Harvey M., "An Improved Counterexample to the Rudimentary Primal Algorithm" (1988). Research Reports from the Department of Operations. 241.
https://commons.case.edu/wsom-ops-reports/241
