{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,15]],"date-time":"2026-09-15T12:29:56Z","timestamp":1789475396226,"version":"build-2803163510"},"reference-count":50,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>Despite the many advantages of interior-point algorithms over active-set methods for linear optimization, one of the remaining practical challenges is their current limitation to efficiently solve series of related problems by an effective warmstarting strategy. As a remedy, in this paper we present a new infeasible-interior-point approach to quickly reoptimize an initial problem instance after data perturbations, or a new linear programming relaxation after adding cutting planes for discrete or combinatorial problems. Based on the detailed complexity analysis of the underlying algorithm, we perform a comparative analysis to coldstart initialization schemes and present encouraging computational results with iteration savings of around 50% on average for perturbations of the Netlib linear programs (LPs) and successive linear programming relaxations of max-cut and the traveling salesman problem.<\/jats:p>","DOI":"10.1137\/080742786","type":"journal-article","created":{"date-parts":[[2010,2,19]],"date-time":"2010-02-19T18:11:59Z","timestamp":1266603119000},"page":"1828-1861","source":"Crossref","is-referenced-by-count":18,"title":["On Interior-Point Warmstarts for Linear and Combinatorial Optimization"],"prefix":"10.1137","volume":"20","author":[{"given":"Alexander","family":"Engau","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Miguel F.","family":"Anjos","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anthony","family":"Vannelli","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2010,2,19]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"E. D. Andersen, J. Gondzio, C. M\u00e9sz\u00e1ros, and X. Xu,\n                      Implementation of interior-point methods for large scale linear programs\n                      , in Interior Point Methods of Mathematical Programming, Appl. Optim. 5, Kluwer, Dordrecht, 1996, pp. 189\u2013252.","DOI":"10.1007\/978-1-4613-3449-1_6"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1137\/06066847X"},{"key":"R3","unstructured":"D. L. Applegate, R. E. Bixby, V. Chv\u00e1tal, and W. J. Cook,\n                      The Traveling Salesman Problem: A Computational Study\n                      , Princeton Ser. Appl. Math., Princeton University Press, Princeton, NJ, 2006."},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-007-9048-6"},{"key":"R5","unstructured":"G. B. Dantzig,\n                      Maximization of a linear function of variables subject to linear inequalities\n                      , in Activity Analysis of Production and Allocation, Cowles Commission Monograph 13, John Wiley & Sons Inc., New York; Chapman & Hall, Ltd., London, 1951, pp. 339\u2013347."},{"key":"R6","doi-asserted-by":"crossref","unstructured":"G. B. Dantzig,\n                      Linear Programming and Extensions\n                      , Princeton University Press, Princeton, NJ, 1963.","DOI":"10.7249\/R366"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1137\/1036003"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-003-0469-4"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"A. Engau, M. F. Anjos, and A. Vannelli,\n                      A primal-dual slack approach to warmstarting interior-point methods for linear programming\n                      , in Operations Research and Cyber-Infrastructure, J. W. Chinneck, B. Kristjansson, and M. J. Saltzman, eds., Springer, New York, 2009, pp. 195\u2013217.","DOI":"10.1007\/978-0-387-88843-9_10"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1007\/BF01582900"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(91)90265-X"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1007\/BF02206810"},{"key":"R13","first-page":"281","volume":"28","author":"Goffin J.-L.","year":"1992","journal-title":"Management Sci.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-1909","issn-type":"print"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623498340266"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1080\/1055678021000060829a"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1016\/S0025-5610(97)00076-2"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623401393141"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1137\/060678129"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008748810765"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1287\/opre.18.6.1138"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-007-9096-y"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579150"},{"key":"R23","first-page":"191","volume":"20","author":"Khachiyan L. G.","year":"1979","journal-title":"Soviet Math. Dokl.","ISSN":"https:\/\/id.crossref.org\/issn\/0197-6788","issn-type":"print"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1007\/BF01582151"},{"key":"R25","unstructured":"E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys, eds.\n                      The Traveling Salesman Problem\n                      , Wiley-Interscience Ser. Discrete Math. Optim., John Wiley & Sons, Chichester, 1990."},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1007\/BF01581140"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.6.1.1"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1080\/10556780600816692"},{"key":"R29","unstructured":"J. E. Mitchell,\n                      Karmarkar's Algorithm and Combinatorial Optimization Problems\n                      , Ph.D. thesis, School of Operations Research and Industrial Engineering, Cornell University, Ithaca, NY, 1988."},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1137\/0804023"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623497324242"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1007\/BF02206819"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580902"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580891"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1007\/BF01582216"},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1287\/moor.18.4.964"},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623400374148"},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1007\/BF01586050"},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.1007\/BF02206812"},{"key":"R40","unstructured":"C. Roos, T. Terlaky, and J.P. Vial,\n                      Interior Point Methods for Linear Optimization\n                      , Springer, New York, 2006."},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.1007\/BF02206818"},{"key":"R42","doi-asserted-by":"publisher","DOI":"10.1080\/10556789908805762"},{"key":"R43","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-002-0347-5"},{"key":"R44","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623497322279"},{"key":"R45","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479893260498"},{"key":"R46","doi-asserted-by":"crossref","unstructured":"S. J. Wright,\n                      Primal-Dual Interior-Point Methods\n                      , SIAM, Philadelphia, 1997.","DOI":"10.1137\/1.9781611971453"},{"key":"R47","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479894271093"},{"key":"R48","unstructured":"Y. Ye,\n                      Interior Point Algorithms\n                      , Wiley-Interscience Ser. Discrete Math. Optim., John Wiley & Sons, New York, 1997."},{"key":"R49","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623400369235"},{"key":"R50","doi-asserted-by":"publisher","DOI":"10.1137\/0804012"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/080742786","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:31:28Z","timestamp":1787333488000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/080742786"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":50,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1137\/080742786"],"URL":"https:\/\/doi.org\/10.1137\/080742786","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1]]}}}