{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,14]],"date-time":"2026-04-14T22:48:50Z","timestamp":1776206930801,"version":"3.50.1"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,11,2]],"date-time":"2022-11-02T00:00:00Z","timestamp":1667347200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,11,2]],"date-time":"2022-11-02T00:00:00Z","timestamp":1667347200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100012352","name":"Universit\u00e0 degli Studi di Milano","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100012352","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Prog. Comp."],"published-print":{"date-parts":[[2023,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We face the issue of finding alternative paradigms for the resolution of generic Mixed Integer Programs (MIP), by considering the perspective option of general purpose solvers which switch to decomposition methods when pertinent. Currently, the main blocking factor in their design is the problem of automatic decomposition of MIPs, that is to produce good MIP decompositions algorithmically, looking only at the algebraic structure of the MIP instance. We propose to employ Dantzig\u2013Wolfe reformulation and machine learning methods to obtain a fully data driven automatic decomposition framework. We also design strategies and introduce algorithmic techniques in order to make such a framework computationally effective. An extensive experimental analysis shows our framework to grant substantial improvements, in terms of both solutions quality and computing time, with respect to state-of-the-art automatic decomposition techniques. It also allows us to gain insights into the relative impact of different techniques. As a side product of our research, we provide a dataset of more than 31 thousand random decompositions of MIPLIB instances, with 121 features, including computations of their root node relaxation.<\/jats:p>","DOI":"10.1007\/s12532-022-00230-4","type":"journal-article","created":{"date-parts":[[2022,11,2]],"date-time":"2022-11-02T19:12:35Z","timestamp":1667416355000},"page":"153-194","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["A data driven Dantzig\u2013Wolfe decomposition framework"],"prefix":"10.1007","volume":"15","author":[{"given":"Saverio","family":"Basso","sequence":"first","affiliation":[]},{"given":"Alberto","family":"Ceselli","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,11,2]]},"reference":[{"key":"230_CR1","doi-asserted-by":"crossref","unstructured":"Achterberg, T., Wunderling, R.: Mixed integer programming: analyzing 12 years of progress. In: Facets of Combinatorial Optimization, pp. 449\u2013481. Springer (2013)","DOI":"10.1007\/978-3-642-38189-8_18"},{"key":"230_CR2","unstructured":"IBM Cplex webpage: https:\/\/www.ibm.com\/analytics\/cplex-optimizer. Accessed November 2020"},{"key":"230_CR3","unstructured":"GUROBI webpage: http:\/\/www.gurobi.com. Accessed November 2020"},{"key":"230_CR4","unstructured":"FICO xpress webpage: http:\/\/www.fico.com\/en\/products\/fico-xpress-optimization-suite. Accessed November 2020"},{"issue":"1","key":"230_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s12532-008-0001-1","volume":"1","author":"T Achterberg","year":"2009","unstructured":"Achterberg, T.: SCIP: solving constraint integer programs. Math. Program. Comput. 1(1), 1\u201341 (2009)","journal-title":"Math. Program. Comput."},{"key":"230_CR6","volume-title":"50 Years of Integer Programming 1958\u20132008","author":"F Vanderbeck","year":"2010","unstructured":"Vanderbeck, F., Wolsey, L.: Reformulation and decomposition of integer programs. In: J\u00fcnger, M., Liebling, Th.M., Naddef, D., Nemhauser, G.L., Pulleyblank, W.R., Reinelt, G., Rinaldi, G., Wolsey, L.A. (eds.) 50 Years of Integer Programming 1958\u20132008. Springer, Berlin (2010)"},{"key":"230_CR7","unstructured":"SAS Viya webpage: https:\/\/www.sas.com\/en_us\/software\/viya.html. Accessed March 2022"},{"key":"230_CR8","doi-asserted-by":"crossref","unstructured":"Basso, S., Ceselli, A.: Asynchronous column generation. In: Proceedings of the Ninteenth Workshop on Algorithm Engineering and Experiments (ALENEX), pp. 197\u2013206. SIAM (2017)","DOI":"10.1137\/1.9781611974768.16"},{"issue":"1","key":"230_CR9","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/s10601-009-9085-0","volume":"16","author":"J Puchinger","year":"2011","unstructured":"Puchinger, J., Stuckey, P.J., Wallace, M.G., Brand, S.: Dantzig\u2013Wolfe decomposition and branch-and-price solving in G12. Constraints 16(1), 77\u201399 (2011)","journal-title":"Constraints"},{"key":"230_CR10","unstructured":"Ralphs, T.K., Galati, M.V.: DIP\u2014decomposition for integer programming. https:\/\/projects.coin-or.org\/Dip. Accessed March 2017"},{"key":"230_CR11","unstructured":"Coluna framework: https:\/\/github.com\/atoptima\/Coluna.jl. Accessed February 2021"},{"key":"230_CR12","unstructured":"Frangioni, A., Lobato, R.D.: SMS++: a Structured Modelling System with Applications to Energy Optimization. In: PGMO DAYS 2018. https:\/\/smspp.gitlab.io\/. Accessed November 2020"},{"key":"230_CR13","doi-asserted-by":"crossref","unstructured":"Gamrath, G., L\u00fcbbecke, M.E.; Experiments with a generic Dantzig\u2013Wolfe decomposition for integer programs. In: Lecture Notes in Computer Science, vol. 6049, pp. 239\u2013252 (2010)","DOI":"10.1007\/978-3-642-13193-6_21"},{"key":"230_CR14","unstructured":"Vanderbeck, F.: BaPCod\u2014a generic branch-and-price code. https:\/\/wiki.bordeaux.inria.fr\/realopt\/pmwiki.php\/Project\/BaPCod. Accessed March 2017"},{"key":"230_CR15","doi-asserted-by":"crossref","unstructured":"Frangioni, A., Sanchez, L.P.: Transforming mathematical models using declarative reformulation rules. In: Lecture Notes in Computer Science 6683, 5th Learning and Intelligent Optimization Conference, pp. 407\u2013422 (2011)","DOI":"10.1007\/978-3-642-25566-3_30"},{"key":"230_CR16","doi-asserted-by":"crossref","unstructured":"Wang, J., Ralphs, T.: Computational experience with hypergraph-based methods for automatic decomposition in discrete optimization. In: Gomes, C., Sellmann, M. (eds.) Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. LNCS vol. 7874, pp. 394\u2013402 (2013)","DOI":"10.1007\/978-3-642-38171-3_31"},{"issue":"1\u20132","key":"230_CR17","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1007\/s10107-014-0761-5","volume":"149","author":"M Bergner","year":"2015","unstructured":"Bergner, M., Caprara, A., Ceselli, A., Furini, F., L\u00fcbbecke, M., Malaguti, E., Traversi, E.: Automatic Dantzig\u2013Wolfe reformulation of mixed integer programs. Math. Program. A 149(1\u20132), 391\u2013424 (2015)","journal-title":"Math. Program. A"},{"issue":"1","key":"230_CR18","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/s12532-019-00171-5","volume":"12","author":"M Bastubbe","year":"2020","unstructured":"Bastubbe, M., L\u00fcbbecke, M.E.: A branch-and-price algorithm for capacitated hypergraph vertex separation. Math. Program. Comput. 12(1), 39\u201368 (2020)","journal-title":"Math. Program. Comput."},{"issue":"2","key":"230_CR19","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1007\/s12532-011-0025-9","volume":"3","author":"T Koch","year":"2011","unstructured":"Koch, T., Achterberg, T., Andersen, E., Bastert, O., Berthold, T., Bixby, R.E., Danna, E., Gamrath, G., Gleixner, A.M., Heinz, S., Lodi, A., Mittelmann, H., Ralphs, T., Salvagnin, D., Steffy, D.E., Wolter, K.: MIPLIB 2010. Math. Program. Comput. 3(2), 103\u2013163 (2011)","journal-title":"Math. Program. Comput."},{"key":"230_CR20","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1007\/s10479-018-3067-9","volume":"284","author":"S Basso","year":"2018","unstructured":"Basso, S., Ceselli, A., Tettamanzi, A.: Random sampling and machine learning to understand good decompositions. Ann. Oper. Res. 284, 501\u2013526 (2018)","journal-title":"Ann. Oper. Res."},{"key":"230_CR21","doi-asserted-by":"crossref","unstructured":"Basso, S., Ceselli, A.: Computational evaluation of ranking models in an automatic decomposition framework. In: Proceedings of EURO\/ALIO 2018, Electronic Notes in Discrete Mathematics, Volume 69, pp. 245\u2013252 (2018)","DOI":"10.1016\/j.endm.2018.07.032"},{"key":"230_CR22","doi-asserted-by":"crossref","unstructured":"Basso, S., Ceselli, A.: Computational evaluation of data driven local search for MIP decompositions. In: Proceedings of ODS 2019, Advances in Optimization and Decision Science for Society, Services and Enterprises. AIRO Springer Series, vol. 3, pp. 207\u2013217 (2019)","DOI":"10.1007\/978-3-030-34960-8_19"},{"key":"230_CR23","doi-asserted-by":"crossref","unstructured":"Kruber, M., L\u00fcbbecke, M.E., Parmentier, A.: Learning when to use a decomposition. In: Integration of AI and OR Techniques in Constraint Programming, Lecture Notes in Computer Science, vol. 10335, pp. 202\u2013210. Springer (2017)","DOI":"10.1007\/978-3-319-59776-8_16"},{"issue":"2","key":"230_CR24","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1016\/j.ejor.2020.07.063","volume":"290","author":"Y Bengio","year":"2021","unstructured":"Bengio, Y., Lodi, A., Prouvost, A.: Machine learning for combinatorial optimization: a methodological tour d\u2019Horizon. Eur. J. Oper. Res. 290(2), 405\u2013421 (2021)","journal-title":"Eur. J. Oper. Res."},{"key":"230_CR25","unstructured":"Prouvost, A., Dumouchelle, J., Scavuzzo, L., Gasse, M., Ch\u00e9telat, D., Lodi, A.: Ecole: a gym-like library for machine learning in combinatorial optimization solvers. arXiv:2011.06069 (2020)"},{"key":"230_CR26","doi-asserted-by":"crossref","unstructured":"Iommazzo, G., D\u2019Ambrosio, C., Frangioni, A., Liberti, L.: A learning-based mathematical programming formulation for the automatic configuration of optimization solvers. In: Lecture Notes in Computer Science, 6th International Conference on Machine Learning, Optimization and Data science\u2014LOD 2020 (2020)","DOI":"10.1007\/978-3-030-64583-0_61"},{"key":"230_CR27","volume-title":"Column Generation","year":"2005","unstructured":"Desaulniers, G., Desrosiers, J., Solomon, M.M. (eds.): Column Generation. Springer, Berlin (2005)"},{"key":"230_CR28","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1016\/j.disopt.2018.07.001","volume":"30","author":"ME L\u00fcbbecke","year":"2018","unstructured":"L\u00fcbbecke, M.E., Witt, J.T.: The strength of Dantzig-Wolfe reformulations for the stable set and related problems. Discrete Optim. 30, 168\u2013187 (2018)","journal-title":"Discrete Optim."},{"key":"230_CR29","unstructured":"Bastubbe, M., L\u00fcbbecke, M.E., Witt, J.T.: A computational investigation on the strength of Dantzig\u2013Wolfe reformulations. In: 17th International Symposium on Experimental Algorithms (SEA 2018), Leibniz International Proceedings in Informatics (LIPIcs), Vol. 103, pp. 11:1\u201311:12. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik (2018)"},{"key":"230_CR30","doi-asserted-by":"crossref","unstructured":"Iommazzo, G., D\u2019Ambrosio, C., Frangioni, A., Liberti, L.: \u2019Learning to configure mathematical programming solvers by mathematical programming. In: Lecture Notes in Computer Science 12096. Learning and Intelligent Optimization\u2014LION, vol. 2020, pp. 377\u2013389 (2020)","DOI":"10.1007\/978-3-030-53552-0_34"},{"key":"230_CR31","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/s12532-015-0096-0","volume":"8","author":"M Fischetti","year":"2016","unstructured":"Fischetti, M., Lodi, A., Monaci, M., Salvagnin, D., Tramontani, A.: Improving branch-and-cut performance by random sampling. Math. Program. Comput. 8, 113\u2013132 (2016)","journal-title":"Math. Program. Comput."},{"key":"230_CR32","unstructured":"MIPLIB 2017: http:\/\/miplib.zib.de Accessed April 2019"},{"key":"230_CR33","doi-asserted-by":"crossref","unstructured":"Ross, S.: Simulation, 5th edn. Academic Press (2014)","DOI":"10.1016\/B978-0-12-407948-9.00011-6"},{"key":"230_CR34","unstructured":"Larose, D.T., Larose, C.D.: Data Mining and Predictive Analytics. Wiley (2015)"},{"issue":"4","key":"230_CR35","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1016\/j.orl.2005.07.009","volume":"34","author":"T Achterberg","year":"2006","unstructured":"Achterberg, T., Koch, T., Martin, A.: MIPLIB 2003. Oper. Res. Lett. 34(4), 361\u2013372 (2006)","journal-title":"Oper. Res. Lett."},{"key":"230_CR36","doi-asserted-by":"publisher","unstructured":"Basso, S., Ceselli, A.: \u201cMIPLib random decompositions dataset\u201d. https:\/\/urldefense.com\/v3\/https:\/\/doi.org\/10.13130\/RD_UNIMI\/T99WYI UNIMI Dataverse V1 (2022)","DOI":"10.13130\/RD_UNIMI\/T99WYI"},{"issue":"3","key":"230_CR37","doi-asserted-by":"publisher","first-page":"570","DOI":"10.1287\/ijoc.2017.0797","volume":"30","author":"T Khaniyev","year":"2018","unstructured":"Khaniyev, T., Elhedhli, S., Erenay, F.S.: Structure detection in mixed-integer programs. INFORMS J. Comput. 30(3), 570\u2013587 (2018)","journal-title":"INFORMS J. Comput."},{"key":"230_CR38","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2022.105894","volume":"146","author":"S Basso","year":"2022","unstructured":"Basso, S., Ceselli, A.: Distributed asynchronous column generation. Comput. Oper. Res. 146, 105894 (2022)","journal-title":"Comput. Oper. Res."}],"container-title":["Mathematical Programming Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12532-022-00230-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s12532-022-00230-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12532-022-00230-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,29]],"date-time":"2023-11-29T23:42:46Z","timestamp":1701301366000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s12532-022-00230-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,2]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,3]]}},"alternative-id":["230"],"URL":"https:\/\/doi.org\/10.1007\/s12532-022-00230-4","relation":{},"ISSN":["1867-2949","1867-2957"],"issn-type":[{"value":"1867-2949","type":"print"},{"value":"1867-2957","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,11,2]]},"assertion":[{"value":"3 May 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 September 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 November 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"The full code was made available for review. We remark that a set of packages were used in this study, that were either open source or available for academic use. Specific references are included in this published article.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Code availability"}}]}}