{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T02:26:34Z","timestamp":1743128794536,"version":"3.40.3"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030179526"},{"type":"electronic","value":"9783030179533"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-17953-3_30","type":"book-chapter","created":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T23:25:20Z","timestamp":1556753120000},"page":"399-412","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Linear Programming Using Limited-Precision Oracles"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0391-5903","authenticated-orcid":false,"given":"Ambros","family":"Gleixner","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0370-9555","authenticated-orcid":false,"given":"Daniel E.","family":"Steffy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,4,13]]},"reference":[{"issue":"3","key":"30_CR1","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1080\/10586458.2001.10504453","volume":"10","author":"J Abbott","year":"2001","unstructured":"Abbott, J., Mulders, T.: How tight is Hadamard\u2019s bound? Exp. Math. 10(3), 331\u2013336 (2001). http:\/\/projecteuclid.org\/euclid.em\/1069786341","journal-title":"Exp. Math."},{"key":"30_CR2","unstructured":"Applegate, D.L., Cook, W., Dash, S., Espinoza, D.G.: Qsopt$$\\_$$ex. http:\/\/www.dii.uchile.cl\/~daespino\/ESolver_doc\/"},{"issue":"6","key":"30_CR3","doi-asserted-by":"publisher","first-page":"693","DOI":"10.1016\/j.orl.2006.12.010","volume":"35","author":"DL Applegate","year":"2007","unstructured":"Applegate, D.L., Cook, W., Dash, S., Espinoza, D.G.: Exact solutions to linear programming problems. Oper. Res. Lett. 35(6), 693\u2013699 (2007). https:\/\/doi.org\/10.1016\/j.orl.2006.12.010","journal-title":"Oper. Res. Lett."},{"key":"30_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/3-540-49481-2_6","volume-title":"Principles and Practice of Constraint Programming \u2014 CP98","author":"D-O Azulay","year":"1998","unstructured":"Azulay, D.-O., Pique, J.-F.\u00c7.: Optimized Q-pivot for exact linear solvers. In: Maher, M., Puget, J.-F. (eds.) CP 1998. LNCS, vol. 1520, pp. 55\u201371. Springer, Heidelberg (1998). https:\/\/doi.org\/10.1007\/3-540-49481-2_6"},{"key":"30_CR5","doi-asserted-by":"publisher","unstructured":"Chen, Z., Storjohann, A.: A BLAS based C library for exact linear algebra on integer matrices. In: Proceedings of the 2005 International Symposium on Symbolic and Algebraic Computation, ISSAC 2005, pp. 92\u201399 (2005). https:\/\/doi.org\/10.1145\/1073884.1073899","DOI":"10.1145\/1073884.1073899"},{"issue":"3","key":"30_CR6","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/j.jco.2005.10.001","volume":"22","author":"D Cheung","year":"2006","unstructured":"Cheung, D., Cucker, F.: Solving linear programs with finite precision: II. Algorithms. J. Complex. 22(3), 305\u2013335 (2006). https:\/\/doi.org\/10.1016\/j.jco.2005.10.001","journal-title":"J. Complex."},{"issue":"4","key":"30_CR7","doi-asserted-by":"publisher","first-page":"39:1","DOI":"10.1145\/1916461.1916463","volume":"37","author":"W Cook","year":"2011","unstructured":"Cook, W., Steffy, D.E.: Solving very sparse rational systems of equations. ACM Trans. Math. Softw. 37(4), 39:1\u201339:21 (2011). https:\/\/doi.org\/10.1145\/1916461.1916463","journal-title":"ACM Trans. Math. Softw."},{"key":"30_CR8","unstructured":"Dhiflaoui, M., et al.: Certifying and repairing solutions to large LPs: how good are LP-solvers? In: Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2003, pp. 255\u2013256. SIAM (2003)"},{"issue":"4","key":"30_CR9","doi-asserted-by":"publisher","first-page":"241","DOI":"10.6028\/jres.071B.033","volume":"71B","author":"J Edmonds","year":"1967","unstructured":"Edmonds, J.: Systems of distinct representatives and linear algebra. J. Res. Natl. Bur. Stan. 71B(4), 241\u2013245 (1967)","journal-title":"J. Res. Natl. Bur. Stan."},{"key":"30_CR10","doi-asserted-by":"crossref","unstructured":"Edmonds, J., Maurras, J.F.: Note sur les $$Q$$-matrices d\u2019Edmonds. RAIRO. Recherche Op\u00e9rationnelle 31(2), 203\u2013209 (1997). http:\/\/www.numdam.org\/item?id=RO_1997__31_2_203_0","DOI":"10.1051\/ro\/1997310202031"},{"issue":"4","key":"30_CR11","doi-asserted-by":"publisher","first-page":"677","DOI":"10.1287\/ijoc.2015.0653","volume":"27","author":"AR Escobedo","year":"2015","unstructured":"Escobedo, A.R., Moreno-Centeno, E.: Roundoff-error-free algorithms for solving linear systems via Cholesky and LU factorizations. INFORMS J. Comput. 27(4), 677\u2013689 (2015). https:\/\/doi.org\/10.1287\/ijoc.2015.0653","journal-title":"INFORMS J. Comput."},{"issue":"3","key":"30_CR12","doi-asserted-by":"publisher","first-page":"829","DOI":"10.1137\/16M1089630","volume":"38","author":"AR Escobedo","year":"2017","unstructured":"Escobedo, A.R., Moreno-Centeno, E.: Roundoff-error-free basis updates of LU factorizations for the efficient validation of optimality certificates. SIAM J. Matrix Anal. Appl. 38(3), 829\u2013853 (2017). https:\/\/doi.org\/10.1137\/16M1089630","journal-title":"SIAM J. Matrix Anal. Appl."},{"issue":"2","key":"30_CR13","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/S0925-7721(99)00012-7","volume":"13","author":"B G\u00e4rtner","year":"1999","unstructured":"G\u00e4rtner, B.: Exact arithmetic at low cost - a case study in linear programming. Comput. Geom. 13(2), 121\u2013139 (1999). https:\/\/doi.org\/10.1016\/S0925-7721(99)00012-7","journal-title":"Comput. Geom."},{"issue":"3","key":"30_CR14","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1287\/ijoc.2016.0692","volume":"28","author":"AM Gleixner","year":"2016","unstructured":"Gleixner, A.M., Steffy, D.E., Wolter, K.: Iterative refinement for linear programming. INFORMS J. Comput. 28(3), 449\u2013464 (2016). https:\/\/doi.org\/10.1287\/ijoc.2016.0692","journal-title":"INFORMS J. Comput."},{"key":"30_CR15","series-title":"Algorithms and Combinatorics","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-78240-4","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M Gr\u00f6tschel","year":"1988","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Algorithms and Combinatorics, vol. 2. Springer, Heidelberg (1988). https:\/\/doi.org\/10.1007\/978-3-642-78240-4"},{"issue":"4","key":"30_CR16","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/BF02579150","volume":"4","author":"N Karmarkar","year":"1984","unstructured":"Karmarkar, N.: A new polynomial-time algorithm for linear programming. Combinatorica 4(4), 373\u2013395 (1984). https:\/\/doi.org\/10.1007\/BF02579150","journal-title":"Combinatorica"},{"issue":"1","key":"30_CR17","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0041-5553(80)90061-0","volume":"20","author":"L.G. Khachiyan","year":"1980","unstructured":"Khachiyan, L.G.: Polynomial algorithms in linear programming (in Russian). Zhurnal Vychislitel\u2019noi Matematiki i Matematicheskoi Fiziki 20(1), 51\u201368 (1980). https:\/\/doi.org\/10.1016\/0041-5553(80)90061-0. English translation: USSR Computational Mathematics and Mathematical Physics, 20(1):53-72, 1980","journal-title":"USSR Computational Mathematics and Mathematical Physics"},{"issue":"2","key":"30_CR18","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1016\/S0167-6377(03)00094-4","volume":"32","author":"T Koch","year":"2004","unstructured":"Koch, T.: The final NETLIB-LP results. Oper. Res. Lett. 32(2), 138\u2013142 (2004). https:\/\/doi.org\/10.1016\/S0167-6377(03)00094-4","journal-title":"Oper. Res. Lett."},{"key":"30_CR19","unstructured":"Kwappik, C.: Exact linear programming. Master\u2019s thesis, Universit\u00e4t des Saarlandes, May 1998"},{"issue":"4","key":"30_CR20","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/BF01457454","volume":"261","author":"AK Lenstra","year":"1982","unstructured":"Lenstra, A.K., Lenstra, H.W., Lov\u00e1sz, L.: Factoring polynomials with rational coefficients. Mathematische Annalen 261(4), 515\u2013534 (1982). https:\/\/doi.org\/10.1007\/BF01457454","journal-title":"Mathematische Annalen"},{"issue":"1\u20133","key":"30_CR21","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/BF01580724","volume":"40","author":"J Renegar","year":"1988","unstructured":"Renegar, J.: A polynomial-time algorithm based on Newton\u2019s method, for linear programming. Math. Program. 40(1\u20133), 59\u201393 (1988). https:\/\/doi.org\/10.1007\/BF01580724","journal-title":"Math. Program."},{"key":"30_CR22","volume-title":"Theory of Linear and Integer Programming","author":"A Schrijver","year":"1986","unstructured":"Schrijver, A.: Theory of Linear and Integer Programming. Wiley, New York (1986)"},{"issue":"3\/4","key":"30_CR23","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1145\/1940475.1940513","volume":"44","author":"DE Steffy","year":"2011","unstructured":"Steffy, D.E.: Exact solutions to linear systems of equations using output sensitive lifting. ACM Commun. Comput. Algebra 44(3\/4), 160\u2013182 (2011). https:\/\/doi.org\/10.1145\/1940475.1940513","journal-title":"ACM Commun. Comput. Algebra"},{"issue":"32","key":"30_CR24","doi-asserted-by":"publisher","first-page":"548","DOI":"10.1137\/S0097539702408636","volume":"2","author":"X Wang","year":"2003","unstructured":"Wang, X., Pan, V.Y.: Acceleration of Euclidean algorithm and rational number reconstruction. SIAM J. Comput. 2(32), 548\u2013556 (2003)","journal-title":"SIAM J. Comput."},{"key":"30_CR25","unstructured":"Zuse Institute Berlin: SoPlex. Sequential object-oriented simPlex. http:\/\/soplex.zib.de\/"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-17953-3_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T12:43:49Z","timestamp":1709815429000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-17953-3_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030179526","9783030179533"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-17953-3_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"13 April 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"IPCO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Integer Programming and Combinatorial Optimization","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Ann Arbor, MI","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 May 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 May 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ipco2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/umich.edu\/~ipco2019conf\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"113","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"33","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"29% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"2.5","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}