{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T16:19:19Z","timestamp":1773332359778,"version":"3.50.1"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2020,6,26]],"date-time":"2020-06-26T00:00:00Z","timestamp":1593129600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,6,26]],"date-time":"2020-06-26T00:00:00Z","timestamp":1593129600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Prog. Comp."],"published-print":{"date-parts":[[2021,9]]},"DOI":"10.1007\/s12532-020-00188-1","type":"journal-article","created":{"date-parts":[[2020,6,26]],"date-time":"2020-06-26T15:45:34Z","timestamp":1593186334000},"page":"491-508","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A triangulation and fill-reducing initialization procedure for the simplex algorithm"],"prefix":"10.1007","volume":"13","author":[{"given":"Nikolaos","family":"Ploskas","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nikolaos V.","family":"Sahinidis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nikolaos","family":"Samaras","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,6,26]]},"reference":[{"key":"188_CR1","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1016\/j.cor.2010.07.001","volume":"38","author":"C Al-Najjar","year":"2011","unstructured":"Al-Najjar, C., Malakooti, B.: Hybrid-LP: finding advanced starting points for simplex, and pivoting LP methods. Comput. Oper. Res. 38, 427\u2013434 (2011)","journal-title":"Comput. Oper. Res."},{"key":"188_CR2","doi-asserted-by":"publisher","first-page":"886","DOI":"10.1137\/S0895479894278952","volume":"17","author":"PR Amestoy","year":"1996","unstructured":"Amestoy, P.R., Davis, T.A., Duff, I.S.: An approximate minimum degree ordering algorithm. SIAM J. Matrix Anal. Appl. 17, 886\u2013905 (1996)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"188_CR3","first-page":"221","volume":"71","author":"ED Andersen","year":"1995","unstructured":"Andersen, E.D., Andersen, K.D.: Presolving in linear programming. Math. Program. 71, 221\u2013245 (1995)","journal-title":"Math. Program."},{"key":"188_CR4","volume-title":"Introduction to Linear Optimization","author":"D Bertsimas","year":"1997","unstructured":"Bertsimas, D., Tsitsiklis, J.: Introduction to Linear Optimization. Athena Scientific, Boston (1997)"},{"key":"188_CR5","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1287\/ijoc.4.3.267","volume":"4","author":"RE Bixby","year":"1992","unstructured":"Bixby, R.E.: Implementing the simplex method: the initial basis. ORSA J. Comput. 4, 267\u2013284 (1992)","journal-title":"ORSA J. Comput."},{"key":"188_CR6","first-page":"131","volume-title":"Advanced Linear-Programming Computing Techniques","author":"DM Carstens","year":"1968","unstructured":"Carstens, D.M.: Crashing techniques. In: Orchard-Hays, W. (ed.) Advanced Linear-Programming Computing Techniques, pp. 131\u2013139. McGraw-Hill, New York (1968)"},{"key":"188_CR7","volume-title":"Linear Programming","author":"V Chv\u00e1tal","year":"1983","unstructured":"Chv\u00e1tal, V.: Linear Programming. W. H. Freeman, New York (1983)"},{"key":"188_CR8","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1093\/imamat\/10.1.118","volume":"10","author":"AR Curtis","year":"1972","unstructured":"Curtis, A.R., Reid, J.K.: On the automatic scaling of matrices for Gaussian elimination. J. Inst. Math. Appl. 10, 118\u2013124 (1972)","journal-title":"J. Inst. Math. Appl."},{"key":"188_CR9","doi-asserted-by":"publisher","first-page":"73","DOI":"10.2307\/1905523","volume":"17","author":"GB Dantzig","year":"1949","unstructured":"Dantzig, G.B.: Programming in a linear structure. Econometrica 17, 73\u201374 (1949)","journal-title":"Econometrica"},{"key":"188_CR10","doi-asserted-by":"publisher","DOI":"10.7249\/R366","volume-title":"Linear Programming and Extensions","author":"GB Dantzig","year":"1963","unstructured":"Dantzig, G.B.: Linear Programming and Extensions. Princeton University Press, Princeton (1963)"},{"key":"188_CR11","first-page":"8","volume":"38","author":"TA Davis","year":"2011","unstructured":"Davis, T.A.: Algorithm 915, SuiteSparseQR: multifrontal multithreaded rank-revealing sparse QR factorization. ACM Trans. Math. Softw. 38, 8\u201329 (2011)","journal-title":"ACM Trans. Math. Softw."},{"key":"188_CR12","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1145\/1024074.1024079","volume":"30","author":"TA Davis","year":"2004","unstructured":"Davis, T.A., Gilbert, J.R., Larimore, S.I., Ng, E.G.: A column approximate minimum degree ordering algorithm. ACM Trans. Math. Softw. 30, 353\u2013376 (2004)","journal-title":"ACM Trans. Math. Softw."},{"key":"188_CR13","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1145\/1024074.1024080","volume":"30","author":"TA Davis","year":"2004","unstructured":"Davis, T.A., Gilbert, J.R., Larimore, S.I., Ng, E.G.: Algorithm 836: COLAMD, a column approximate minimum degree ordering algorithm. ACM Trans. Math. Softw. 30, 377\u2013380 (2004)","journal-title":"ACM Trans. Math. Softw."},{"key":"188_CR14","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/s101070100263","volume":"91","author":"ED Dolan","year":"2002","unstructured":"Dolan, E.D., Mor\u00e9, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91, 201\u2013213 (2002)","journal-title":"Math. Program."},{"key":"188_CR15","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1504\/IJMOR.2012.048900","volume":"4","author":"JM Elble","year":"2012","unstructured":"Elble, J.M., Sahinidis, N.V.: A review of LU factorization in the simplex algorithm. Int. J. Math. Oper. Res. 4, 319\u2013365 (2012)","journal-title":"Int. J. Math. Oper. Res."},{"key":"188_CR16","doi-asserted-by":"publisher","first-page":"366","DOI":"10.1504\/IJMOR.2012.048901","volume":"4","author":"JM Elble","year":"2012","unstructured":"Elble, J.M., Sahinidis, N.V.: A review of the LU update in the simplex algorithm. Int. J. Math. Oper. Res. 4, 366\u2013399 (2012)","journal-title":"Int. J. Math. Oper. Res."},{"key":"188_CR17","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/s10589-011-9420-4","volume":"52","author":"JM Elble","year":"2012","unstructured":"Elble, J.M., Sahinidis, N.V.: Scaling linear optimization problems prior to application of the simplex method. Comput. Optim. Appl. 52, 345\u2013371 (2012)","journal-title":"Comput. Optim. Appl."},{"key":"188_CR18","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1137\/0722022","volume":"22","author":"AM Erisman","year":"1985","unstructured":"Erisman, A.M., Grimes, R.G., Lewis, J.G., Poole Jr., W.G.: A structurally stable modification of Hellerman\u2013Rarick\u2019s $$P^4$$ algorithm for reordering unsymmetric sparse matrices. SIAM J. Numer. Anal. 22, 369\u2013385 (1985)","journal-title":"SIAM J. Numer. Anal."},{"key":"188_CR19","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1007\/BF01581089","volume":"57","author":"JJ Forrest","year":"1992","unstructured":"Forrest, J.J., Goldfarb, D.: Steepest-edge simplex algorithms for linear programming. Math. Program. 57, 341\u2013374 (1992)","journal-title":"Math. Program."},{"key":"188_CR20","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/BF01584548","volume":"2","author":"JJH Forrest","year":"1972","unstructured":"Forrest, J.J.H., Tomlin, J.A.: Updated triangular factors of the basis to maintain sparsity in the product form simplex method. Math. Program. 2, 263\u2013278 (1972)","journal-title":"Math. Program."},{"key":"188_CR21","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1137\/0613024","volume":"13","author":"JR Gilbert","year":"1992","unstructured":"Gilbert, J.R., Moler, C.B., Schreiber, R.: Sparse matrices in MATLAB: design and implementation. SIAM J. Matrix Anal. Appl. 13, 333\u2013356 (1992)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"188_CR22","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1007\/BF01584343","volume":"13","author":"D Goldfarb","year":"1977","unstructured":"Goldfarb, D.: On the Bartels\u2013Golub decomposition for linear programming bases. Math. Program. 13, 272\u2013279 (1977)","journal-title":"Math. Program."},{"key":"188_CR23","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1007\/BF01589115","volume":"45","author":"NIM Gould","year":"1989","unstructured":"Gould, N.I.M., Reid, J.K.: New crash procedures for large systems of linear constraints. Math. Program. 45, 475\u2013501 (1989)","journal-title":"Math. Program."},{"key":"188_CR24","first-page":"95","volume":"100","author":"NIM Gould","year":"2004","unstructured":"Gould, N.I.M., Toint, P.L.: Preprocessing for quadratic programming. Math. Program. 100, 95\u2013132 (2004)","journal-title":"Math. Program."},{"key":"188_CR25","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1023\/A:1013548430005","volume":"21","author":"N G\u00fclpinar","year":"2002","unstructured":"G\u00fclpinar, N., Mitra, G., Maros, I.: Creating advanced bases for large scale linear programs exploiting embedded network structure. Comput. Optim. Appl. 21, 71\u201393 (2002)","journal-title":"Comput. Optim. Appl."},{"key":"188_CR26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01580108","volume":"5","author":"PMJ Harris","year":"1973","unstructured":"Harris, P.M.J.: Pivot selection methods of the Devex LP code. Math. Program. 5, 1\u201328 (1973)","journal-title":"Math. Program."},{"key":"188_CR27","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/s12532-017-0130-5","volume":"10","author":"Q Huangfu","year":"2018","unstructured":"Huangfu, Q., Hall, J.: Parallelizing the dual revised simplex method. Math. Program. Comput. 10, 119\u2013142 (2018)","journal-title":"Math. Program. Comput."},{"key":"188_CR28","doi-asserted-by":"publisher","first-page":"1983","DOI":"10.1016\/j.cor.2004.01.002","volume":"32","author":"HV Junior","year":"2005","unstructured":"Junior, H.V., Lins, M.P.E.: An improved initial basis for the simplex algorithm. Comput. Oper. Res. 32, 1983\u20131993 (2005)","journal-title":"Comput. Oper. Res."},{"key":"188_CR29","first-page":"355","volume":"35","author":"S Kaczmarz","year":"1937","unstructured":"Kaczmarz, S.: Angen\u00e4herte aufl\u00f6sung von systemen linearer gleichungen. Bull. Int. Acad. Pol. Sci. Lett. 35, 355\u2013357 (1937)","journal-title":"Bull. Int. Acad. Pol. Sci. Lett."},{"key":"188_CR30","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1137\/S1064827595287997","volume":"20","author":"G Karypis","year":"1998","unstructured":"Karypis, G., Kumar, V.: A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput. 20, 359\u2013392 (1998)","journal-title":"SIAM J. Sci. Comput."},{"key":"188_CR31","volume-title":"History of Mathematical Programming","year":"1991","unstructured":"Lenstra, J.K., Rinnoy Kan, A.H.G., Schrijver, A. (eds.): History of Mathematical Programming. CWI North Holland, Amsterdam (1991)"},{"key":"188_CR32","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/S0305-0548(00)00069-1","volume":"29","author":"H Luh","year":"2002","unstructured":"Luh, H., Tsaih, R.: An efficient search direction for linear programming problems. Comput. Oper. Res. 29, 195\u2013203 (2002)","journal-title":"Comput. Oper. Res."},{"key":"188_CR33","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1287\/mnsc.3.3.255","volume":"3","author":"HM Markowitz","year":"1957","unstructured":"Markowitz, H.M.: The elimination form of the inverse and its application to linear programming. Manag. Sci. 3, 255\u2013269 (1957). (Originally at The RAND Corporation, Research Memorandum RM-1452, 1955)","journal-title":"Manag. Sci."},{"key":"188_CR34","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-0257-9","volume-title":"Computational Techniques of the Simplex Method","author":"I Maros","year":"2003","unstructured":"Maros, I.: Computational Techniques of the Simplex Method. Kluwer Academic Publishers, Boston (2003)"},{"key":"188_CR35","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1287\/ijoc.10.2.248","volume":"10","author":"I Maros","year":"1998","unstructured":"Maros, I., Mitra, G.: Strategies for creating advanced bases for large-scale linear programming problems. INFORMS J. Comput. 10, 248\u2013260 (1998)","journal-title":"INFORMS J. Comput."},{"key":"188_CR36","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1007\/s00291-003-0130-x","volume":"25","author":"C M\u00e9sz\u00e1ros","year":"2003","unstructured":"M\u00e9sz\u00e1ros, C., Suhl, U.H.: Advanced preprocessing techniques for linear and quadratic programming. OR Spectr. 25, 575\u2013595 (2003)","journal-title":"OR Spectr."},{"key":"188_CR37","unstructured":"Murtagh, B.A., Saunders, M.A.: MINOS 5.1 User\u2019s Guide. Technical report, Department of Operations Research, Stanford University, Stanford, CA (1987)"},{"key":"188_CR38","first-page":"479","volume":"210","author":"H Nabli","year":"2009","unstructured":"Nabli, H.: An overview on the simplex algorithm. Appl. Math. Comput. 210, 479\u2013489 (2009)","journal-title":"Appl. Math. Comput."},{"key":"188_CR39","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1016\/j.ejor.2015.03.040","volume":"245","author":"H Nabli","year":"2015","unstructured":"Nabli, H., Chahdoura, S.: Algebraic simplex initialization combined with the nonfeasible basis methods. Eur. J. Oper. Res. 245, 384\u2013391 (2015)","journal-title":"Eur. J. Oper. Res."},{"key":"188_CR40","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40754-3","volume-title":"Linear Programming Computation","author":"PQ Pan","year":"2014","unstructured":"Pan, P.Q.: Linear Programming Computation. Springer, Berlin (2014)"},{"key":"188_CR41","volume-title":"Combinatorial Optimization: Algorithms and Complexity","author":"C Papadimitriou","year":"1998","unstructured":"Papadimitriou, C., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity. Dover Publications, Mineola (1998)"},{"key":"188_CR42","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jss.2014.04.047","volume":"96","author":"N Ploskas","year":"2014","unstructured":"Ploskas, N., Samaras, N.: GPU accelerated pivoting rules for the simplex algorithm. J. Syst. Softw. 96, 1\u20139 (2014)","journal-title":"J. Syst. Softw."},{"key":"188_CR43","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1080\/00207160.2014.890716","volume":"92","author":"N Ploskas","year":"2015","unstructured":"Ploskas, N., Samaras, N.: A computational comparison of scaling techniques for linear optimization problems on a graphical processing unit. Int. J. Comput. Math. 92, 319\u2013336 (2015)","journal-title":"Int. J. Comput. Math."},{"key":"188_CR44","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/BF02096264","volume":"46","author":"T Terlaky","year":"1993","unstructured":"Terlaky, T., Zhang, S.: Pivot rules for linear programming: a survey on recent theoretical developments. Ann. Oper. Res. 46, 203\u2013233 (1993)","journal-title":"Ann. Oper. Res."},{"key":"188_CR45","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1007\/BFb0120717","volume":"4","author":"JA Tomlin","year":"1975","unstructured":"Tomlin, J.A.: An accuracy test for updating triangular factors. Math. Program. Study 4, 142\u2013145 (1975)","journal-title":"Math. Program. Study"},{"key":"188_CR46","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1137\/0602010","volume":"2","author":"M Yannakakis","year":"1981","unstructured":"Yannakakis, M.: Computing the minimum fill-in is NP-complete. SIAM J. Algebr. Discrete Methods 2, 77\u201379 (1981)","journal-title":"SIAM J. Algebr. Discrete Methods"},{"key":"188_CR47","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/BF00940732","volume":"63","author":"Y Ye","year":"1989","unstructured":"Ye, Y.: Eliminating columns in the simplex method for linear-programming. J. Optim. Theory Appl. 63, 69\u201377 (1989)","journal-title":"J. Optim. Theory Appl."}],"container-title":["Mathematical Programming Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12532-020-00188-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s12532-020-00188-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12532-020-00188-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,17]],"date-time":"2021-08-17T17:04:30Z","timestamp":1629219870000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s12532-020-00188-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,26]]},"references-count":47,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,9]]}},"alternative-id":["188"],"URL":"https:\/\/doi.org\/10.1007\/s12532-020-00188-1","relation":{},"ISSN":["1867-2949","1867-2957"],"issn-type":[{"value":"1867-2949","type":"print"},{"value":"1867-2957","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,6,26]]},"assertion":[{"value":"8 February 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 June 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 June 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}