{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,6]],"date-time":"2026-04-06T10:14:01Z","timestamp":1775470441637,"version":"3.50.1"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2021,5,22]],"date-time":"2021-05-22T00:00:00Z","timestamp":1621641600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,5,22]],"date-time":"2021-05-22T00:00:00Z","timestamp":1621641600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004770","name":"Universit\u00e0 degli Studi di Parma","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100004770","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comput Optim Appl"],"published-print":{"date-parts":[[2021,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper we address game theory problems arising in the context of network security. In traditional game theory problems, given a defender and an attacker, one searches for mixed strategies which minimize a linear payoff functional. In the problems addressed in this paper an additional quadratic term is added to the minimization problem. Such term represents <jats:italic>switching costs<\/jats:italic>, i.e., the costs for the defender of switching from a given strategy to another one at successive rounds of a Nash game. The resulting problems are nonconvex QP ones with linear constraints and turn out to be very challenging. We will show that the most recent approaches for the minimization of nonconvex QP functions over polytopes, including commercial solvers such as  and , are unable to solve to optimality even test instances with <jats:inline-formula><jats:alternatives><jats:tex-math>$$n=50$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mn>50<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> variables. For this reason, we propose to extend with them the current benchmark set of test instances for QP problems. We also present a spatial branch-and-bound approach for the solution of these problems, where a predominant role is played by an optimality-based domain reduction, with multiple solutions of LP problems at each node of the branch-and-bound tree. Of course, domain reductions are standard tools in spatial branch-and-bound approaches. However, our contribution lies in the observation that, from the computational point of view, a rather aggressive application of these tools appears to be the best way to tackle the proposed instances. Indeed, according to our experiments, while they make the computational cost per node high, this is largely compensated by the rather slow growth of the number of nodes in the branch-and-bound tree, so that the proposed approach strongly outperforms the existing solvers for QP problems.<\/jats:p>","DOI":"10.1007\/s10589-021-00282-7","type":"journal-article","created":{"date-parts":[[2021,5,22]],"date-time":"2021-05-22T13:02:47Z","timestamp":1621688567000},"page":"561-599","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Computing mixed strategies equilibria in presence of switching costs by the solution of nonconvex QP problems"],"prefix":"10.1007","volume":"79","author":[{"given":"G.","family":"Liuzzi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7138-8653","authenticated-orcid":false,"given":"M.","family":"Locatelli","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"V.","family":"Piccialli","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S.","family":"Rass","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,5,22]]},"reference":[{"key":"282_CR1","unstructured":"OpenStreetMap (2021). https:\/\/www.openstreetmap.org\/#map=15\/15.3368\/76.4601"},{"key":"282_CR2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17197-0","volume-title":"Network security: A decision and game-theoretic approach","author":"T Alpcan","year":"2010","unstructured":"Alpcan, T., Ba\u015far, T.: Network security: A decision and game-theoretic approach. Cambridge University Press (2010)"},{"key":"282_CR3","doi-asserted-by":"crossref","unstructured":"Alpern, S., Lidbetter, T., Morton, A., Papadaki, K.: Patrolling a Pipeline. In: Zhu, Q., Alpcan, T., Panaousis, E., Tambe, M., Casey, W. (eds.) Decision and Game Theory for Security. Lecture Notes in Computer Science, pp. 129\u2013138. Springer International Publishing, Cham (2016)","DOI":"10.1007\/978-3-319-47413-7_8"},{"issue":"5","key":"282_CR4","doi-asserted-by":"publisher","first-page":"1246","DOI":"10.1287\/opre.1110.0983","volume":"59","author":"S Alpern","year":"2011","unstructured":"Alpern, S., Morton, A., Papadaki, K.: Patrolling games. Operations Research 59(5), 1246\u20131257 (2011)","journal-title":"Operations Research"},{"key":"282_CR5","doi-asserted-by":"crossref","unstructured":"Basak, A., Fang, F., Nguyen, T.H., Kiekintveld, C.: Combining Graph Contraction and Strategy Generation for Green Security Games. In: Zhu, Q., Alpcan, T., Panaousis, E., Tambe, M., Casey, W. (eds.) Decision and Game Theory for Security. Lecture Notes in Computer Science, pp. 251\u2013271. Springer International Publishing, Cham (2016)","DOI":"10.1007\/978-3-319-47413-7_15"},{"key":"282_CR6","doi-asserted-by":"crossref","unstructured":"Bezanson, J., Edelman, A., Karpinski, S., Shah, V.B.: Julia: A fresh approach to numerical computing. SIAM review 59(1), 65\u201398 (2017). https:\/\/doi.org\/10.1137\/141000671","DOI":"10.1137\/141000671"},{"key":"282_CR7","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/s12532-018-0133-x","volume":"10","author":"P Bonami","year":"2018","unstructured":"Bonami, P., G\u00fcnl\u00fck, O., Linderoth, J.: Globally solving nonconvex quadratic programming problems with box constraints via integer programming methods. Mathematical Programming Computation 10, 333\u2013382 (2018)","journal-title":"Mathematical Programming Computation"},{"issue":"1","key":"282_CR8","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1007\/s10107-008-0263-4","volume":"125","author":"A Caprara","year":"2010","unstructured":"Caprara, A., Locatelli, M.: Global optimization problems and domain reduction strategies. Mathematical Programming 125(1), 123\u2013137 (2010)","journal-title":"Mathematical Programming"},{"issue":"1","key":"282_CR9","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/s12532-011-0033-9","volume":"4","author":"J Chen","year":"2012","unstructured":"Chen, J., Burer, S.: Globally solving nonconvex quadratic programming problems via completely positive programming. Mathematical Programming Computation 4(1), 33\u201352 (2012)","journal-title":"Mathematical Programming Computation"},{"key":"282_CR10","unstructured":"Fang, F., Jiang, A.X., Tambe, M.: Optimal patrol strategy for protecting moving targets with multiple mobile resources. In: Proceedings of the 2013 international conference on Autonomous agents and multi-agent systems, AAMAS \u201913, pp. 957\u2013964. International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC (2013)"},{"issue":"2","key":"282_CR11","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/s12532-018-0147-4","volume":"11","author":"F Furini","year":"2019","unstructured":"Furini, F., Traversi, E., Belotti, P., Frangioni, A., Gleixner, A., Gould, N., Liberti, L., Lodi, A., Misener, R., Mittelmann, H., et al.: Qplib: a library of quadratic programming instances. Mathematical Programming Computation 11(2), 237\u2013265 (2019)","journal-title":"Mathematical Programming Computation"},{"key":"282_CR12","doi-asserted-by":"publisher","first-page":"731","DOI":"10.1007\/s10898-016-0450-4","volume":"67","author":"A Gleixner","year":"2017","unstructured":"Gleixner, A., Berthold, T., M\u00fcller, B., Weltge, S.: Three enhancements for optimization-based bound tightening. Journal of Global Optimization 67, 731\u2013757 (2017)","journal-title":"Journal of Global Optimization"},{"key":"282_CR13","doi-asserted-by":"crossref","unstructured":"Gondzio, J., Yildirim, E.A.: Global solutions of nonconvex standard quadratic programs via mixed integer linear programming reformulations. Journal of Global Optimization to appear (2021)","DOI":"10.1007\/s10898-021-01017-y"},{"key":"282_CR14","doi-asserted-by":"crossref","unstructured":"Hansen, K.A., Koucky, M., Lauritzen, N., Miltersen, P.B., Tsigaridas, E.P.: Exact algorithms for solving stochastic games. In: Proceedings of the forty-third annual ACM symposium on Theory of computing, pp. 205\u2013214 (2011)","DOI":"10.1145\/1993636.1993665"},{"key":"282_CR15","unstructured":"Horst, R., Tuy, H.: Global optimization: Deterministic approaches (2nd edition). Springer Science & Business Media (2013)"},{"key":"282_CR16","unstructured":"Lozovanu, D., Solomon, D., Zelikovsky, A.: Multiobjective games and determining pareto-nash equilibria. Buletinul Academiei de \u015etiin\u0163e a Republicii Moldova. Matematica 3, 115\u2013122 (2005)"},{"issue":"1","key":"282_CR17","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/BF01580665","volume":"10","author":"GP McCormick","year":"1976","unstructured":"McCormick, G.P.: Computability of global solutions to factorable nonconvex programs: Part i-convex underestimating problems. Mathematical Programming 10(1), 147\u2013175 (1976)","journal-title":"Mathematical Programming"},{"issue":"4","key":"282_CR18","doi-asserted-by":"publisher","first-page":"533","DOI":"10.4153\/CJM-1965-053-6","volume":"17","author":"T Motzkin","year":"1965","unstructured":"Motzkin, T., Straus, E.: Maxima for graphs and a new proof of a theorem of Tur\u00e1n. Canadian Journal of Mathematics 17(4), 533\u2013540 (1965)","journal-title":"Canadian Journal of Mathematics"},{"key":"282_CR19","doi-asserted-by":"crossref","unstructured":"Padgham, M.: dodgr: An r package for network flow aggregation. Transport Findings (2019). 10.32866\/6945","DOI":"10.32866\/6945"},{"key":"282_CR20","unstructured":"Padgham, M.: GitHub - ATFutures\/dodgr: Distances on Directed Graphs in R (2021). https:\/\/github.com\/ATFutures\/dodgr"},{"issue":"6","key":"282_CR21","doi-asserted-by":"publisher","first-page":"1256","DOI":"10.1287\/opre.2016.1511","volume":"64","author":"K Papadaki","year":"2016","unstructured":"Papadaki, K., Alpern, S., Lidbetter, T., Morton, A.: Patrolling a Border. Operations Research 64(6), 1256\u20131269 (2016). https:\/\/doi.org\/10.1287\/opre.2016.1511","journal-title":"Operations Research"},{"key":"282_CR22","doi-asserted-by":"publisher","unstructured":"Pita, J., Tambe, M., Kiekintveld, C., Cullen, S., Steigerwald, E.: GUARDS - Innovative Application of Game Theory for National Airport Security. IJCAI (2011). https:\/\/doi.org\/10.5591\/978-1-57735-516-8\/IJCAI11-451","DOI":"10.5591\/978-1-57735-516-8\/IJCAI11-451"},{"key":"282_CR23","doi-asserted-by":"crossref","unstructured":"P.M., P., S.A., V.: Quadratic programming with one negative eigenvalue is NP-hard. Journal of Global Optimization 1(1), 15\u201322 (1991)","DOI":"10.1007\/BF00120662"},{"key":"282_CR24","doi-asserted-by":"publisher","first-page":"8394","DOI":"10.1109\/ACCESS.2017.2693425","volume":"5","author":"S Rass","year":"2017","unstructured":"Rass, S., Alshawish, A., Abid, M.A., Schauer, S., Zhu, Q., De Meer, H.: Physical intrusion games-optimizing surveillance by simulation and game theory. IEEE Access 5, 8394\u20138407 (2017)","journal-title":"IEEE Access"},{"issue":"5","key":"282_CR25","doi-asserted-by":"publisher","first-page":"312","DOI":"10.3390\/e20050312","volume":"20","author":"S Rass","year":"2018","unstructured":"Rass, S., K\u00f6nig, S.: Password security as a game of entropies. Entropy 20(5), 312 (2018)","journal-title":"Entropy"},{"key":"282_CR26","doi-asserted-by":"crossref","unstructured":"Rass, S., K\u00f6nig, S., Schauer, S.: On the cost of game playing: How to control the expenses in mixed strategies. In: International Conference on Decision and Game Theory for Security, pp. 494\u2013505. Springer (2017)","DOI":"10.1007\/978-3-319-68711-7_26"},{"key":"282_CR27","doi-asserted-by":"crossref","unstructured":"Rass, S., Rainer, B.: Numerical computation of multi-goal security strategies. In: International Conference on Decision and Game Theory for Security, pp. 118\u2013133. Springer (2014)","DOI":"10.1007\/978-3-319-12601-2_7"},{"key":"282_CR28","doi-asserted-by":"crossref","unstructured":"Rass, S., Schauer, S., K\u00f6nig, S., Zhu, Q.: Cyber-Security in Critical Infrastructures: A Game-Theoretic Approach. SpringerNature (2020)","DOI":"10.1007\/978-3-030-46908-5"},{"issue":"2","key":"282_CR29","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/BF00138693","volume":"8","author":"NV Sahinidis","year":"1996","unstructured":"Sahinidis, N.V.: Baron: A general purpose global optimization software package. Journal of Global Optimization 8(2), 201\u2013205 (1996)","journal-title":"Journal of Global Optimization"},{"key":"282_CR30","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511973031","volume-title":"Security and game theory: algorithms, deployed systems, lessons learned","author":"M Tambe","year":"2011","unstructured":"Tambe, M.: Security and game theory: algorithms, deployed systems, lessons learned. Cambridge University Press (2011)"},{"issue":"3","key":"282_CR31","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1007\/s10107-003-0467-6","volume":"99","author":"M Tawarmalani","year":"2004","unstructured":"Tawarmalani, M., Sahinidis, N.V.: Global optimization of mixed-integer nonlinear programs: A theoretical and computational study. Mathematical Programming 99(3), 563\u2013591 (2004)","journal-title":"Mathematical Programming"},{"issue":"3","key":"282_CR32","doi-asserted-by":"publisher","first-page":"59","DOI":"10.3390\/g9030059","volume":"9","author":"J Wachter","year":"2018","unstructured":"Wachter, J., Rass, S., K\u00f6nig, S.: Security from the adversary\u2019s inertia-controlling convergence speed when playing mixed strategy equilibria. Games 9(3), 59 (2018)","journal-title":"Games"},{"issue":"1","key":"282_CR33","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1287\/ijoc.2018.0883","volume":"32","author":"W Xia","year":"2020","unstructured":"Xia, W., Vera, J.C., Zuluaga, L.F.: Globally solving nonconvex quadratic programs via linear integer programming techniques. INFORMS Journal on Computing 32(1), 40\u201356 (2020)","journal-title":"INFORMS Journal on Computing"}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-021-00282-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10589-021-00282-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-021-00282-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,17]],"date-time":"2021-06-17T19:22:25Z","timestamp":1623957745000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10589-021-00282-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,22]]},"references-count":33,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,7]]}},"alternative-id":["282"],"URL":"https:\/\/doi.org\/10.1007\/s10589-021-00282-7","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"value":"0926-6003","type":"print"},{"value":"1573-2894","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,5,22]]},"assertion":[{"value":"8 September 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 May 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 May 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}