{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,30]],"date-time":"2025-12-30T15:41:14Z","timestamp":1767109274577,"version":"3.37.3"},"reference-count":50,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2023,8,10]],"date-time":"2023-08-10T00:00:00Z","timestamp":1691625600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,8,10]],"date-time":"2023-08-10T00:00:00Z","timestamp":1691625600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2024,7]]},"DOI":"10.1007\/s10107-023-02004-9","type":"journal-article","created":{"date-parts":[[2023,8,10]],"date-time":"2023-08-10T14:03:38Z","timestamp":1691676218000},"page":"239-281","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["LP-based approximations for disjoint bilinear and two-stage adjustable robust optimization"],"prefix":"10.1007","volume":"206","author":[{"given":"Omar","family":"El Housni","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8782-4699","authenticated-orcid":false,"given":"Ayoub","family":"Foussoul","sequence":"additional","affiliation":[]},{"given":"Vineet","family":"Goyal","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,8,10]]},"reference":[{"issue":"10","key":"2004_CR1","doi-asserted-by":"crossref","first-page":"1274","DOI":"10.1287\/mnsc.32.10.1274","volume":"32","author":"WP Adams","year":"1986","unstructured":"Adams, W.P., Sherali, H.D.: A tight linearization and an algorithm for zero-one quadratic programming problems. Manag. Sci. 32(10), 1274\u20131290 (1986)","journal-title":"Manag. Sci."},{"issue":"2","key":"2004_CR2","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1287\/opre.38.2.217","volume":"38","author":"WP Adams","year":"1990","unstructured":"Adams, W.P., Sherali, H.D.: Linearization strategies for a class of zero-one mixed integer programming problems. Oper. Res. 38(2), 217\u2013226 (1990)","journal-title":"Oper. Res."},{"key":"2004_CR3","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/BF01581249","volume":"59","author":"WP Adams","year":"1993","unstructured":"Adams, W.P., Sherali, H.D.: Mixed-integer bilinear programming problems. Math. Program. 59, 279\u2013305 (1993)","journal-title":"Math. Program."},{"key":"2004_CR4","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1007\/s101079900106","volume":"87","author":"C Audet","year":"2000","unstructured":"Audet, C., Hansen, P., Jaumard, B., Savard, G.: A branch and cut algorithm for nonconvex quadratically constrained quadratic programming. Math. Program. 87, 131\u2013152 (2000)","journal-title":"Math. Program."},{"issue":"1","key":"2004_CR5","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1007\/s10107-012-0567-2","volume":"134","author":"C Bandi","year":"2012","unstructured":"Bandi, C., Bertsimas, D.: Tractable stochastic analysis in high dimensions via robust optimization. Math. Program. 134(1), 23\u201370 (2012)","journal-title":"Math. Program."},{"key":"2004_CR6","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/s10107-019-01385-0","volume":"182","author":"A Ben-Tal","year":"2020","unstructured":"Ben-Tal, A., El Housni, O., Goyal, V.: A tractable approach for designing piecewise affine policies in two-stage adjustable robust optimization. Math. Program. 182, 57\u2013102 (2020)","journal-title":"Math. Program."},{"key":"2004_CR7","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1007\/s10107-003-0454-y","volume":"99","author":"A Ben-Tal","year":"2004","unstructured":"Ben-Tal, A., Goryashko, A., Guslitzer, E., Nemirovski, A.: Adjustable robust solutions of uncertain linear programs. Math. Program. 99, 351\u2013376 (2004)","journal-title":"Math. Program."},{"issue":"2","key":"2004_CR8","doi-asserted-by":"crossref","first-page":"577","DOI":"10.1007\/s10107-014-0818-5","volume":"153","author":"D Bertsimas","year":"2015","unstructured":"Bertsimas, D., Bidkhori, H.: On the performance of affine policies for two-stage adaptive optimization: a geometric perspective. Math. Program. 153(2), 577\u2013594 (2015)","journal-title":"Math. Program."},{"issue":"3","key":"2004_CR9","doi-asserted-by":"crossref","first-page":"464","DOI":"10.1137\/080734510","volume":"53","author":"D Bertsimas","year":"2011","unstructured":"Bertsimas, D., Brown, D.B., Caramanis, C.: Theory and applications of robust optimization. SIAM Rev. 53(3), 464\u2013501 (2011)","journal-title":"SIAM Rev."},{"key":"2004_CR10","doi-asserted-by":"crossref","first-page":"491","DOI":"10.1007\/s10107-011-0444-4","volume":"134","author":"D Bertsimas","year":"2012","unstructured":"Bertsimas, D., Goyal, V.: On the power and limitations of affine policies in two-stage adaptive optimization. Math. Program. 134, 491\u2013531 (2012)","journal-title":"Math. Program."},{"issue":"2","key":"2004_CR11","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1287\/moor.1100.0444","volume":"35","author":"D Bertsimas","year":"2010","unstructured":"Bertsimas, D., Iancu, D.A., Parrilo, P.A.: Optimality of affine policies in multistage robust optimization. Math. Oper. Res. 35(2), 363\u2013394 (2010)","journal-title":"Math. Oper. Res."},{"key":"2004_CR12","doi-asserted-by":"crossref","first-page":"500","DOI":"10.1287\/ijoc.2016.0689","volume":"28","author":"D Bertsimas","year":"2016","unstructured":"Bertsimas, D., Ruiter, F.: Duality in two-stage adaptive linear optimization: faster computation and stronger bounds. Informs J. Comput. 28, 500\u2013511 (2016)","journal-title":"Informs J. Comput."},{"key":"2004_CR13","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1287\/opre.1030.0065","volume":"52","author":"D Bertsimas","year":"2004","unstructured":"Bertsimas, D., Sim, M.: The price of robustness. Oper. Res. 52, 35\u201353 (2004)","journal-title":"Oper. Res."},{"issue":"3","key":"2004_CR14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1516512.1516516","volume":"56","author":"X Chen","year":"2009","unstructured":"Chen, X., Deng, X., Teng, S.H.: Settling the complexity of computing two-player Nash equilibria. J. ACM 56(3), 1\u201357 (2009)","journal-title":"J. ACM"},{"issue":"4","key":"2004_CR15","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1214\/aoms\/1177729330","volume":"23","author":"H Chernoff","year":"1952","unstructured":"Chernoff, H.: A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. Math. Stat. 23(4), 493\u2013507 (1952)","journal-title":"Ann. Math. Stat."},{"issue":"1\u20132","key":"2004_CR50","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1007\/s10107-017-1111-1","volume":"166","author":"A \u0106usti\u0107","year":"2017","unstructured":"\u0106usti\u0107, A., Sokol, V., Punnen, A.P., Bhattacharya, B.: The bilinear assignment problem: complexity and polynomially solvable special cases. Math. Program. 166(1\u20132), 185\u2013205 (2017)","journal-title":"Math. Program."},{"key":"2004_CR16","doi-asserted-by":"crossref","unstructured":"Dhamdhere, K., Goyal, V., Ravi, R., Singh, M.: How to pay, come what may: approximation algorithms for demand-robust covering problems. In: 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201905), pp. 367\u2013376 (2005)","DOI":"10.1109\/SFCS.2005.42"},{"key":"2004_CR17","unstructured":"El\u00a0Housni, O., Goyal, V.: Beyond worst-case: a probabilistic analysis of affine policies in dynamic optimization. In: Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 4759\u20134767 (2017)"},{"issue":"2","key":"2004_CR18","doi-asserted-by":"crossref","first-page":"674","DOI":"10.1287\/moor.2020.1082","volume":"46","author":"O El Housni","year":"2021","unstructured":"El Housni, O., Goyal, V.: On the optimality of affine policies for budgeted uncertainty sets. Math. Oper. Res. 46(2), 674\u2013711 (2021)","journal-title":"Math. Oper. Res."},{"key":"2004_CR19","unstructured":"El\u00a0Housni, O., Goyal, V., Hanguir, O., Stein, C.: Matching drivers to riders: a two-stage robust approach. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2021), vol. 207, pp. 12:1\u201312:22 (2021)"},{"key":"2004_CR20","doi-asserted-by":"crossref","unstructured":"El\u00a0Housni, O., Goyal, V., Shmoys, D.: On the power of static assignment policies for robust facility location problems. In: International Conference on Integer Programming and Combinatorial Optimization, pp. 252\u2013267 (2021)","DOI":"10.1007\/978-3-030-73879-2_18"},{"key":"2004_CR21","doi-asserted-by":"crossref","unstructured":"Feige, U., Jain, K., Mahdian, M., Mirrokni, V.: Robust combinatorial optimization with exponential scenarios. In: Fischetti, M., Williamson, D.P. (eds.) Integer Programming and Combinatorial Optimization, pp. 439\u2013453 (2007)","DOI":"10.1007\/978-3-540-72792-7_33"},{"issue":"1","key":"2004_CR22","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1109\/TCOMM.2015.2504085","volume":"64","author":"K Firouzbakht","year":"2016","unstructured":"Firouzbakht, K., Noubir, G., Salehi, M.: Linearly constrained bimatrix games in wireless communications. IEEE Trans. Commun. 64(1), 429\u2013440 (2016)","journal-title":"IEEE Trans. Commun."},{"issue":"2","key":"2004_CR23","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1016\/j.orl.2011.12.004","volume":"40","author":"AS Freire","year":"2012","unstructured":"Freire, A.S., Moreno, E., Vielma, J.P.: An integer linear programming approach for bilinear integer programming. Oper. Res. Lett. 40(2), 74\u201377 (2012)","journal-title":"Oper. Res. Lett."},{"key":"2004_CR24","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1007\/BF00934810","volume":"10","author":"A Geoffrion","year":"1972","unstructured":"Geoffrion, A.: Generalized benders decomposition. J. Optim. Theory Appl. 10, 237\u2013260 (1972)","journal-title":"J. Optim. Theory Appl."},{"key":"2004_CR25","first-page":"1139","volume":"50","author":"C Gounaris","year":"2014","unstructured":"Gounaris, C., Repoussis, P., Tarantilis, C., Wiesemann, W., Floudas, C.: An adaptive memory programming framework for the robust capacitated vehicle routing problem. Transp. Sci. 50, 1139\u20131393 (2014)","journal-title":"Transp. Sci."},{"key":"2004_CR26","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1007\/s10107-013-0705-5","volume":"146","author":"A Gupta","year":"2014","unstructured":"Gupta, A., Nagarajan, V., Ravi, R.: Thresholded covering algorithms for robust and max\u2013min optimization. Math. Program. 146, 583\u2013615 (2014)","journal-title":"Math. Program."},{"issue":"1","key":"2004_CR27","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2746226","volume":"12","author":"A Gupta","year":"2015","unstructured":"Gupta, A., Nagarajan, V., Ravi, R.: Robust and maxmin optimization under matroid and knapsack uncertainty sets. ACM Trans. Algorithms 12(1), 1\u201321 (2015)","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"2004_CR28","doi-asserted-by":"crossref","first-page":"721","DOI":"10.1137\/110836183","volume":"23","author":"A Gupte","year":"2013","unstructured":"Gupte, A., Ahmed, S., Cheon, M.S., Dey, S.: Solving mixed integer bilinear problems using milp formulations. SIAM J. Optim. 23(2), 721\u2013744 (2013)","journal-title":"SIAM J. Optim."},{"key":"2004_CR29","doi-asserted-by":"crossref","first-page":"631","DOI":"10.1007\/s10898-016-0434-4","volume":"67","author":"A Gupte","year":"2017","unstructured":"Gupte, A., Ahmed, S., Dey, S.S., Cheon, M.S.: Relaxations and discretizations for the pooling problem. J. Global Optim. 67, 631\u2013669 (2017)","journal-title":"J. Global Optim."},{"key":"2004_CR30","doi-asserted-by":"crossref","unstructured":"Hadjiyiannis, M.J., Goulart, P.J., Kuhn, D.: A scenario approach for estimating the suboptimality of linear decision rules in two-stage robust optimization. In: 2011 50th IEEE Conference on Decision and Control and European Control Conference, pp. 7386\u20137391. IEEE (2011)","DOI":"10.1109\/CDC.2011.6161342"},{"key":"2004_CR31","doi-asserted-by":"crossref","first-page":"594","DOI":"10.1016\/S0377-2217(97)00066-0","volume":"105","author":"I Harjunkoski","year":"1998","unstructured":"Harjunkoski, I., Westerlund, T., P\u00f6rn, R., Skrifvars, H.: Different transformations for solving non-convex trim-loss problems by minlp. Eur. J. Oper. Res. 105, 594\u2013603 (1998)","journal-title":"Eur. J. Oper. Res."},{"key":"2004_CR32","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1007\/BF01580367","volume":"11","author":"H Konno","year":"1976","unstructured":"Konno, H.: A cutting plane algorithm for solving bilinear programs. Math. Program. 11, 14\u201327 (1976)","journal-title":"Math. Program."},{"issue":"1","key":"2004_CR33","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1080\/07408170600729192","volume":"39","author":"C Lim","year":"2007","unstructured":"Lim, C., Smith, J.C.: Algorithms for discrete and continuous multicommodity flow network interdiction problems. IIE Trans. 39(1), 15\u201326 (2007)","journal-title":"IIE Trans."},{"issue":"3","key":"2004_CR34","doi-asserted-by":"crossref","first-page":"348","DOI":"10.1016\/0022-247X(64)90021-6","volume":"9","author":"O Mangasarian","year":"1964","unstructured":"Mangasarian, O., Stone, H.: Two-person nonzero-sum games and quadratic programming. J. Math. Anal. Appl. 9(3), 348\u2013355 (1964)","journal-title":"J. Math. Anal. Appl."},{"key":"2004_CR35","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1007\/s11590-009-0114-0","volume":"3","author":"S Rebennack","year":"2009","unstructured":"Rebennack, S., Nahapetyan, A., Pardalos, P.: Bilinear modeling solution approach for fixed charge network flow problems. Optim. Lett. 3, 347\u2013355 (2009)","journal-title":"Optim. Lett."},{"key":"2004_CR36","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, STOC \u201978, pp. 216\u2013226. Association for Computing Machinery, New York (1978)","DOI":"10.1145\/800133.804350"},{"issue":"3","key":"2004_CR37","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1137\/0403036","volume":"3","author":"HD Sherali","year":"1990","unstructured":"Sherali, H.D., Adams, W.P.: A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Discret. Math. 3(3), 411\u2013430 (1990)","journal-title":"SIAM J. Discret. Math."},{"issue":"1","key":"2004_CR38","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/0166-218X(92)00190-W","volume":"52","author":"HD Sherali","year":"1994","unstructured":"Sherali, H.D., Adams, W.P.: A hierarchy of relaxations and convex hull characterizations for mixed-integer zero-one programming problems. Discret. Appl. Math. 52(1), 83\u2013106 (1994)","journal-title":"Discret. Appl. Math."},{"issue":"6","key":"2004_CR39","doi-asserted-by":"crossref","first-page":"1319","DOI":"10.1016\/j.dam.2008.03.041","volume":"157","author":"HD Sherali","year":"2009","unstructured":"Sherali, H.D., Adams, W.P.: A reformulation-linearization technique (rlt) for semi-infinite and convex programs under mixed 0\u20131 and general discrete restrictions. Discret. Appl. Math. 157(6), 1319\u20131333 (2009)","journal-title":"Discret. Appl. Math."},{"key":"2004_CR40","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1007\/BF00122429","volume":"2","author":"HD Sherali","year":"1992","unstructured":"Sherali, H.D., Alameddine, A.: A new reformulation-linearization technique for bilinear programming problems. J. Global Optim. 2, 379\u2013410 (1992)","journal-title":"J. Global Optim."},{"issue":"1\u20133","key":"2004_CR41","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1016\/S0166-218X(99)00225-5","volume":"101","author":"HD Sherali","year":"2000","unstructured":"Sherali, H.D., Smith, J.C., Adams, W.P.: Reduced first-level representations via the reformulation-linearization technique: results, counterexamples, and computations. Discret. Appl. Math. 101(1\u20133), 247\u2013267 (2000)","journal-title":"Discret. Appl. Math."},{"key":"2004_CR42","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1007\/BF00121304","volume":"2","author":"HD Sherali","year":"1992","unstructured":"Sherali, H.D., Tuncbilek, C.H.: A global optimization algorithm for polynomial programming problems using a reformulation-linearization technique. J. Global Optim. 2, 101\u2013112 (1992)","journal-title":"J. Global Optim."},{"key":"2004_CR43","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1287\/opre.22.2.373","volume":"22","author":"R Soland","year":"1974","unstructured":"Soland, R.: Optimal facility location with concave costs. Oper. Res. 22, 373\u2013382 (1974)","journal-title":"Oper. Res."},{"issue":"1\u20132","key":"2004_CR44","doi-asserted-by":"crossref","first-page":"481","DOI":"10.1007\/s10107-010-0374-6","volume":"124","author":"M Tawarmalani","year":"2010","unstructured":"Tawarmalani, M., Richard, J.P.P., Chung, K.: Strong valid inequalities for orthogonal disjunctions and bilinear covering sets. Math. Program. 124(1\u20132), 481\u2013512 (2010)","journal-title":"Math. Program."},{"issue":"1\u20133","key":"2004_CR45","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1007\/BF01580766","volume":"41","author":"TV Thieu","year":"1988","unstructured":"Thieu, T.V.: A note on the solution of bilinear programming problems by reduction to concave minimization. Math. Program. 41(1\u20133), 249\u2013260 (1988)","journal-title":"Math. Program."},{"issue":"2","key":"2004_CR46","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1002\/nav.3800230212","volume":"23","author":"H Vaish","year":"1976","unstructured":"Vaish, H., Shetty, C.M.: The bilinear programming problem. Naval Res. Logist. Q. 23(2), 303\u2013309 (1976)","journal-title":"Naval Res. Logist. Q."},{"issue":"1","key":"2004_CR47","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/s10589-017-9974-x","volume":"70","author":"G Xu","year":"2018","unstructured":"Xu, G., Burer, S.: A copositive approach for two-stage adjustable robust optimization with uncertain right-hand sides. Comput. Optim. Appl. 70(1), 33\u201359 (2018)","journal-title":"Comput. Optim. Appl."},{"issue":"4","key":"2004_CR48","doi-asserted-by":"crossref","first-page":"1086","DOI":"10.1287\/opre.2017.1714","volume":"66","author":"J Zhen","year":"2018","unstructured":"Zhen, J., den Hertog, D., Sim, M.: Adjustable robust optimization via Fourier\u2013Motzkin elimination. Oper. Res. 66(4), 1086\u20131100 (2018)","journal-title":"Oper. Res."},{"key":"2004_CR49","doi-asserted-by":"crossref","unstructured":"Zhen, J., Marandi, A., de\u00a0Moor, D., den Hertog, D., Vandenberghe, L.: Disjoint bilinear optimization: a two-stage robust optimization perspective. INFORMS J. Comput. (2022)","DOI":"10.1287\/ijoc.2022.1163"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-023-02004-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-023-02004-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-023-02004-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,26]],"date-time":"2024-10-26T00:19:23Z","timestamp":1729901963000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-023-02004-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,10]]},"references-count":50,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2024,7]]}},"alternative-id":["2004"],"URL":"https:\/\/doi.org\/10.1007\/s10107-023-02004-9","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2023,8,10]]},"assertion":[{"value":"11 July 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 July 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 August 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}