Improved Primal Simplex: A More General Theoretical Framework and an Extended Experimental Analysis

References

• Benichou M, Gauthier JM, Hentges G, Ribière G (1977) The efficient solution of large-scale linear programming problems: Some algorithmic techniques and computational results. Math. Programming 13:280–322.Crossref, Google Scholar
• Dantzig GB (1955) The general simplex method for minimizing a linear form under inequality constraints. Pacific J. Math. 5:183–195.Crossref, Google Scholar
• Elhallaoui I, Metrane A, Desaulniers G, Soumis F (2011) An improved primal simplex algorithm for degenerate linear programs. INFORMS J. Comput. 23:569–577.Link, Google Scholar
• Elhallaoui I, Villeneuve D, Soumis F, Desaulniers G (2005) Dynamic aggregation of set-partitioning constraints in column generation. Oper. Res. 53:632–645.Link, Google Scholar
• Gill PE, Murray W, Saunders MA, Wright MH (1989) A practical anti-cycling procedure for linearly constrained optimization. Math. Programming 45:437–474.Crossref, Google Scholar
• Goldfarb D, Reid J (1977) A practicable steepest-edge simplex algorithm. Math. Programming 12:361–371.Crossref, Google Scholar
• Greenberg HJ (1978) Design and Implementation of Optimization Software, Nato Science Series E, Vol. 28 (Sijthoff & Noordhoff, Netherlands).Crossref, Google Scholar
• Harris PMJ (1973) Pivot selection method of the Devex LP code. Math. Programming 5:1–28.Crossref, Google Scholar
• Kallio M, Porteus EL (1978) A class of methods for linear programming. Math. Programming 14:161–169.Crossref, Google Scholar
• Maros I (2003) Computational Techniques of the Simplex Method, International Series in Operations Research and Management Science (Kluwer Academic Publishers, New York).Crossref, Google Scholar
• McCormick ST, Shioura A (2000) Minimum ratio canceling is oracle polynomial for linear programming but not strongly polynomial even for networks. Oper. Res. Lett. 27:199–207.Crossref, Google Scholar
• Metrane A, Soumis F, Elhallaoui I (2010) Column generation decomposition with the degenerate constraints in the subproblem. Eur. J. Oper. Res. 207:37–44.Crossref, Google Scholar
• Murtagh BA, Saunders MA (1978) Large-scale linearly constrained optimization. Math. Programming 14:41–72.Crossref, Google Scholar
• Pan P-Q (2008) A primal deficient-basis simplex algorithm for linear programming. Appl. Math. Comput. 196:898–912.Crossref, Google Scholar
• Perold AF (1980) A degeneracy exploiting LU factorization for the simplex method. Math. Programming 19:239–254.Crossref, Google Scholar
• Raymond V, Soumis F, Orban D (2010a) A new version of the improved primal simplex for degenerate linear programs. Comput. Oper. Res. 37:91–98.Crossref, Google Scholar
• Raymond V, Soumis F, Metrane A, Desrosiers J (2010b) Positive edge: A pricing criterion for the identification of non-degenerate simplex pivots. Les Cahiers du GERAD G-2010-61, GERAD, Montreal, Quebec.Google Scholar
• Rosat S, Elhallaoui I, Soumis F, Lodi A (2014) Integral simplex using decomposition with primal cuts. Gudmundsson J, Katajainen J, eds. Experimental Algorithms, Lecture Notes in Computer Science, Vol. 8504 (Springer, Switzerland), 22–33.Crossref, Google Scholar
• Towhidi M, Desrosiers J, Soumis F (2014) The positive edge criterion within COIN-OR’s CLP. Comp. Oper. Res. 49:41–46.Crossref, Google Scholar