{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T18:47:28Z","timestamp":1776106048537,"version":"3.50.1"},"reference-count":74,"publisher":"Institute for Operations Research and the Management Sciences (INFORMS)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["INFORMS Journal on Computing"],"published-print":{"date-parts":[[2026,3]]},"abstract":"<jats:p>Nonconvex separable piecewise linear functions (PLFs) frequently appear in applications and to approximate nonlinearitites. The standard practice to formulate nonconvex PLFs is from the perspective of discrete optimization using special ordered sets and mixed-integer linear programs (MILPs). In contrast, we take the viewpoint of global continuous optimization and present a spatial branch-and-bound algorithm for optimizing a separable discontinuous PLF over a closed convex set. It offers slim and sparse linear programming relaxations, sharpness throughout the search tree, and an increased flexibility in branching decisions. The main feature of our algorithm is the generation of convex underestimators at the root node of the search tree and their quick and efficient updates at each node after branching. Convergence to the global optimum is achieved when the PLFs are lower semicontinuous. A Python implementation of our algorithm is tested on knapsack and network flow problems for both continuous and discontinuous PLFs. Our algorithm is compared with four logarithmic MILP formulations solved by Gurobi\u2019s MILP solver as well as Gurobi\u2019s PLF solver. We also compare our method against mixed-integer nonlinear program formulations solved by Gurobi. The numerical experiments indicate significant performance gains up to two orders of magnitude for medium- to large-sized PLFs. Finally, we also give an upper bound on the additive error from PLF approximations of nonconvex separable optimization.<\/jats:p>\n                  <jats:p>History: Accepted by Andrea Lodi, Area Editor for Design &amp; Analysis of Algorithms\u2013Discrete.<\/jats:p>\n                  <jats:p>Funding: The research of S. Rebennack is supported by the Deutsche Forschungsgemeinschaft [Grant 445857709].<\/jats:p>\n                  <jats:p>Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https:\/\/pubsonline.informs.org\/doi\/suppl\/10.1287\/ijoc.2024.0755 ) as well as from the IJOC GitHub software repository ( https:\/\/github.com\/INFORMSJoC\/2024.0755 ). The complete IJOC Software and Data Repository is available at https:\/\/informsjoc.github.io\/ .<\/jats:p>","DOI":"10.1287\/ijoc.2024.0755","type":"journal-article","created":{"date-parts":[[2025,6,27]],"date-time":"2025-06-27T12:04:18Z","timestamp":1751025858000},"page":"645-675","source":"Crossref","is-referenced-by-count":1,"title":["Spatial Branch-and-Bound for Nonconvex Separable Piecewise Linear Optimization"],"prefix":"10.1287","volume":"38","author":[{"given":"Thomas","family":"H\u00fcbner","sequence":"first","affiliation":[{"name":"Power Systems Laboratory, ETH Z\u00fcrich, 8092 Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7839-165X","authenticated-orcid":false,"given":"Akshay","family":"Gupte","sequence":"additional","affiliation":[{"name":"School of Mathematics, University of Edinburgh, Edinburgh EH9 3FD,  United Kingdom; and Maxwell Institute for Mathematical Sciences, University of Edinburgh, Edinburgh EH8 9BT, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8501-2785","authenticated-orcid":false,"given":"Steffen","family":"Rebennack","sequence":"additional","affiliation":[{"name":"Institute for Operations Research, Stochastic Optimization, Karlsruhe Institute of Technology, 76185 Karlsruhe, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"109","reference":[{"key":"B1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2004.04.002"},{"key":"B2","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-018-1246-8"},{"key":"B3","doi-asserted-by":"publisher","DOI":"10.1016\/S0098-1354(98)00027-1"},{"key":"B4","doi-asserted-by":"publisher","DOI":"10.1137\/S105262349935178X"},{"key":"B5","doi-asserted-by":"publisher","DOI":"10.1145\/235815.235821"},{"key":"B6","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-022-01243-y"},{"key":"B7","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-022-01184-6"},{"key":"B8","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580653"},{"key":"B9","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(90)90059-E"},{"key":"B10","doi-asserted-by":"publisher","DOI":"10.1016\/j.sorms.2012.08.001"},{"key":"B11","doi-asserted-by":"publisher","DOI":"10.1080\/10556788.2018.1556661"},{"key":"B12","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022512411995"},{"key":"B13","volume-title":"Introduction to Algorithms","author":"Cormen TH","year":"2009"},{"key":"B14","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.49.9.1268.16570"},{"key":"B15","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1060.0314"},{"key":"B16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-53262-8_9"},{"key":"B17","doi-asserted-by":"publisher","DOI":"10.2307\/1905292"},{"key":"B18","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2007.05.004"},{"key":"B19","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-012-0049-9"},{"key":"B20","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2015.1357"},{"key":"B21","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-18530-4_9"},{"key":"B22","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.15.9.550"},{"key":"B23","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.34.3.411"},{"key":"B24","doi-asserted-by":"publisher","DOI":"10.1007\/BF01582246"},{"key":"B25","doi-asserted-by":"publisher","DOI":"10.1016\/j.cam.2009.12.035"},{"key":"B26","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-021-01740-0"},{"key":"B27","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-1927-3_10"},{"key":"B28","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2022.0090"},{"key":"B29","doi-asserted-by":"publisher","DOI":"10.1137\/21M1402364"},{"key":"B30","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-008-9287-9"},{"key":"B31","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(72)90045-2"},{"key":"B32","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-020-00881-4"},{"key":"B33","first-page":"24:1","volume-title":"20th International Symposium on Experimental Algorithms: SEA 2022","volume":"233","author":"Gupte A","year":"2022"},{"key":"B34","unstructured":"Gurobi Optimization (2024) Documentation\u2014General constraints. https:\/\/www.gurobi.com\/documentation\/current\/refman\/general_constraints.html."},{"key":"B35","doi-asserted-by":"publisher","DOI":"10.1007\/BF00939825"},{"key":"B36","doi-asserted-by":"crossref","unstructured":"H\u00fcbner T, Gupte A, Rebennack S (2025) Spatial branch and bound for nonconvex separable piecewise linear optimization. https:\/\/github.com\/INFORMSJoC\/2024.0755.","DOI":"10.1287\/ijoc.2024.0755"},{"key":"B37","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2019.1973"},{"key":"B38","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(03)00059-2"},{"key":"B39","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1060.0277"},{"key":"B40","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-004-0503-1"},{"key":"B41","doi-asserted-by":"crossref","unstructured":"Kim J, Richard J-PP, Tawarmalani M (2024) Piecewise polyhedral relaxations of multilinear optimization.\n                      SIAM J. Optim\n                      . 34(4):3167\u20133193.","DOI":"10.1137\/22M1507486"},{"key":"B42","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2019.0949"},{"key":"B43","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.12.4.324.11877"},{"key":"B44","unstructured":"Leyffer S, Sartenaer A, Wanufelle E (2008) Branch-and-refine for mixed-integer nonconvex global optimization. Working Paper No. ANL\/MCS-P1547-0908, Mathematics and Computer Science Division, Argonne National Laboratory, Lemont, IL."},{"key":"B45","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972672"},{"key":"B46","doi-asserted-by":"crossref","unstructured":"Lyu B, Hicks IV, Huchette J (2025) Building formulations for piecewise linear relaxations of nonlinear functions.\n                      Oper. Res.\n                      , ePub ahead of print April 24, https:\/\/doi.org\/10.1287\/opre.2023.0187.","DOI":"10.1287\/opre.2023.0187"},{"key":"B47","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-25960-2_18"},{"key":"B48","doi-asserted-by":"publisher","DOI":"10.2307\/1907744"},{"key":"B49","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(76)90145-X"},{"key":"B50","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-018-00734-1"},{"key":"B51","doi-asserted-by":"publisher","DOI":"10.1080\/10556780802614507"},{"key":"B52","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2018.11.021"},{"key":"B53","doi-asserted-by":"publisher","DOI":"10.1007\/s00500-020-05254-3"},{"key":"B54","doi-asserted-by":"publisher","DOI":"10.1007\/s00186-016-0546-0"},{"key":"B55","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-014-0687-3"},{"key":"B56","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2019.0890"},{"key":"B57","doi-asserted-by":"publisher","DOI":"10.1007\/s11590-009-0114-0"},{"key":"B58","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008241411395"},{"key":"B59","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(01)00063-3"},{"key":"B60","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.17.11.759"},{"key":"B61","doi-asserted-by":"publisher","DOI":"10.1007\/s11081-021-09609-z"},{"key":"B62","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-003-0467-6"},{"key":"B63","doi-asserted-by":"publisher","DOI":"10.1137\/0134059"},{"key":"B64","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2011.12.030"},{"key":"B65","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-31484-6"},{"key":"B66","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580762"},{"key":"B67","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-009-0295-4"},{"key":"B68","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1090.0721"},{"key":"B69","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2007.07.001"},{"key":"B70","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2021.1114"},{"key":"B71","doi-asserted-by":"publisher","DOI":"10.1080\/24725854.2023.2299809"},{"key":"B72","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-013-0060-3"},{"key":"B73","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2013.09.004"},{"key":"B74","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-012-0517-z"}],"container-title":["INFORMS Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pubsonline.informs.org\/doi\/pdf\/10.1287\/ijoc.2024.0755","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T08:24:56Z","timestamp":1776068696000},"score":1,"resource":{"primary":{"URL":"https:\/\/pubsonline.informs.org\/doi\/10.1287\/ijoc.2024.0755"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3]]},"references-count":74,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,3]]}},"alternative-id":["10.1287\/ijoc.2024.0755"],"URL":"https:\/\/doi.org\/10.1287\/ijoc.2024.0755","relation":{},"ISSN":["1091-9856","1526-5528"],"issn-type":[{"value":"1091-9856","type":"print"},{"value":"1526-5528","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3]]}}}