{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T06:19:20Z","timestamp":1784182760971,"version":"3.55.0"},"reference-count":62,"publisher":"Association for Computing Machinery (ACM)","issue":"PLDI","license":[{"start":{"date-parts":[[2024,6,20]],"date-time":"2024-06-20T00:00:00Z","timestamp":1718841600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1908798;2110861;2312220"],"award-info":[{"award-number":["1908798;2110861;2312220"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2024,6,20]]},"abstract":"<jats:p>\n            This paper proposes a novel method to efficiently solve\n            <jats:italic toggle=\"yes\">infeasible<\/jats:italic>\n            low-dimensional linear programs (LDLPs) with billions of constraints and a small number of unknown variables, where all the constraints cannot be satisfied simultaneously. We focus on infeasible linear programs generated in the RL\n            <jats:sc>ibm<\/jats:sc>\n            project for creating correctly rounded math libraries. Specifically, we are interested in generating a floating point solution that satisfies the maximum number of constraints. None of the existing methods can solve such large linear programs while producing floating point solutions.\n          <\/jats:p>\n          <jats:p>\n            We observe that the convex hull can serve as an intermediate representation (IR) for solving infeasible LDLPs using the geometric duality between linear programs and convex hulls. Specifically, some of the constraints that correspond to points on the convex hull are precisely those constraints that make the linear program infeasible. Our key idea is to split the entire set of constraints into two subsets using the convex hull IR: (a) a set\n            <jats:inline-formula>\n              <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\">\n                <mml:mi mathvariant=\"script\">X<\/mml:mi>\n              <\/mml:math>\n            <\/jats:inline-formula>\n            of feasible constraints and (b) a superset\n            <jats:inline-formula>\n              <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\">\n                <mml:mi mathvariant=\"script\">V<\/mml:mi>\n              <\/mml:math>\n            <\/jats:inline-formula>\n            of infeasible constraints. Using the special structure of the RL\n            <jats:sc>ibm<\/jats:sc>\n            constraints and the presence of a method to check whether a system is feasible or not. we identify a superset of infeasible constraints by computing the convex hull in 2-dimensions. Subsequently, we identify the key constraints (i.e., basis constraints) in the set of feasible constraints\n            <jats:inline-formula>\n              <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\">\n                <mml:mi mathvariant=\"script\">X<\/mml:mi>\n              <\/mml:math>\n            <\/jats:inline-formula>\n            and use them to create a new linear program whose solution identifies the maximum set of constraints satisfiable in\n            <jats:inline-formula>\n              <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\">\n                <mml:mi mathvariant=\"script\">V<\/mml:mi>\n              <\/mml:math>\n            <\/jats:inline-formula>\n            while satisfying all the constraints in\n            <jats:inline-formula>\n              <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\">\n                <mml:mi mathvariant=\"script\">X<\/mml:mi>\n              <\/mml:math>\n            <\/jats:inline-formula>\n            . This new solver enabled us to improve the performance of the resulting RL\n            <jats:sc>ibm<\/jats:sc>\n            polynomials while solving the corresponding linear programs significantly faster.\n          <\/jats:p>","DOI":"10.1145\/3656427","type":"journal-article","created":{"date-parts":[[2024,6,20]],"date-time":"2024-06-20T16:27:20Z","timestamp":1718900840000},"page":"1239-1263","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Maximum Consensus Floating Point Solutions for Infeasible Low-Dimensional Linear Programs with Convex Hull as the Intermediate Representation"],"prefix":"10.1145","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5286-8173","authenticated-orcid":false,"given":"Mridul","family":"Aanjaneya","sequence":"first","affiliation":[{"name":"Rutgers University, Piscataway, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5048-8548","authenticated-orcid":false,"given":"Santosh","family":"Nagarakatte","sequence":"additional","affiliation":[{"name":"Rutgers University, Piscataway, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,6,20]]},"reference":[{"key":"e_1_3_1_2_2","unstructured":"[n. d.]. Cyclic Polytope. https:\/\/en.wikipedia.org\/wiki\/Cyclic_polytope"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/3519939.3523447"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/3579990.3580022"},{"key":"e_1_3_1_5_2","author":"Aanjaneya Mridul","year":"2024","unstructured":"Mridul Aanjaneya and Santosh Nagarakatte. 2024. RLibm\u2019s Maximum Consensus LP Solver. https:\/\/github.com\/rutgers-apl\/The-RLIBM-Project\/tree\/main\/mcs-lp-solver","journal-title":"RLibm\u2019s Maximum Consensus LP Solver"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.5075\/epfl-thesis-1282"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48777-8_4"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-9094-6"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2001.989499"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45583-3_11"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/137097.137892"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2"},{"key":"e_1_3_1_13_2","unstructured":"Kevin Q. Brown. 1978. Fast Intersection of Half Spaces. https:\/\/apps.dtic.mil\/sti\/citations\/ADA058787 CMU Department of Computer Science Technical Report ADA058787."},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2014.6906997"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01934990"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2016.2631531"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02284627"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.9.2.164"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.3.2.157"},{"key":"e_1_3_1_20_2","volume-title":"Linear Programming","author":"Chvatal Vasek","year":"1983","unstructured":"Vasek Chvatal. 1983. Linear Programming. W. H. Freeman."},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/201019.201036"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(94)00366-1"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-61568-9"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2005.11.003"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33718-5_53"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/358669.358692"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/948109.948155"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2013.6696980"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.3.3.253"},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/152613.152619"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.5555\/2031416"},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.3929\/ethz-a-006250404"},{"key":"e_1_3_1_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/2535596"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1137\/0215021"},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2017.48"},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.2009.5459398"},{"key":"e_1_3_1_37_2","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2019.00276"},{"key":"e_1_3_1_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/3434310"},{"key":"e_1_3_1_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454049"},{"key":"e_1_3_1_40_2","author":"Lim Jay P","year":"2021","unstructured":"Jay P Lim and Santosh Nagarakatte. 2021. RLibm-32: High Performance Correctly Rounded Math Libraries for 32-bit Floating Point Representations. arXiv:2104.04043 Rutgers Department of Computer Science Technical Report DCS-TR-754.","journal-title":"RLibm-32: High Performance Correctly Rounded Math Libraries for 32-bit Floating Point Representations"},{"key":"e_1_3_1_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/3498664"},{"key":"e_1_3_1_42_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1012422931930"},{"key":"e_1_3_1_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/2422.322418"},{"key":"e_1_3_1_44_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4899-7983-4"},{"key":"e_1_3_1_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/3498704"},{"key":"e_1_3_1_46_2","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2008.4587757"},{"key":"e_1_3_1_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/3485539"},{"key":"e_1_3_1_48_2","doi-asserted-by":"publisher","DOI":"10.2514\/2.4943"},{"key":"e_1_3_1_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150444"},{"key":"e_1_3_1_50_2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(93)90079-V"},{"key":"e_1_3_1_51_2","doi-asserted-by":"publisher","DOI":"10.1145\/12130.12172"},{"key":"e_1_3_1_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/98524.98570"},{"key":"e_1_3_1_53_2","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454064"},{"key":"e_1_3_1_54_2","doi-asserted-by":"publisher","DOI":"10.1145\/1390156.1390286"},{"key":"e_1_3_1_55_2","doi-asserted-by":"publisher","DOI":"10.1016\/0305-0548(95)00018-H"},{"key":"e_1_3_1_56_2","doi-asserted-by":"publisher","DOI":"10.1145\/3591238"},{"key":"e_1_3_1_57_2","volume-title":"CGAL User and Reference Manual","author":"The CGAL Project","year":"2023","unstructured":"The CGAL Project. 2023. CGAL User and Reference Manual (5.6 ed.). CGAL Editorial Board. https:\/\/doc.cgal.org\/5.6\/Manual\/packages.html","edition":"5"},{"key":"e_1_3_1_58_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cag.2014.09.027"},{"key":"e_1_3_1_59_2","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(81)90177-6"},{"key":"e_1_3_1_60_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-7630-6"},{"key":"e_1_3_1_61_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2006.08.006"},{"key":"e_1_3_1_62_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2010.07.021"},{"key":"e_1_3_1_63_2","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2011.5995640"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3656427","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3656427","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T20:43:21Z","timestamp":1751661801000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3656427"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,20]]},"references-count":62,"journal-issue":{"issue":"PLDI","published-print":{"date-parts":[[2024,6,20]]}},"alternative-id":["10.1145\/3656427"],"URL":"https:\/\/doi.org\/10.1145\/3656427","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,6,20]]},"assertion":[{"value":"2024-06-20","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}