{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T20:40:48Z","timestamp":1768336848475,"version":"3.49.0"},"reference-count":25,"publisher":"MathDoc\/Centre Mersenne","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>Neural networks that include a combinatorial optimization layer can give surprisingly efficient heuristic policies for difficult combinatorial optimization problems. Three questions remain open: which architecture should be used, how should the parameters of the machine learning model be learned, and what performance guarantees can we expect from the resulting algorithms? Following the intuitions of geometric deep learning, we explain why equivariant layers should be used when designing such policies, and illustrate how to build such layers on routing, scheduling, and network design applications. We introduce a learning approach that enables to learn such policies when the training set contains only instances of the difficult optimization problem and not their optimal solutions, and show its numerical performance on our three applications. Finally, using tools from statistical learning theory, we prove a theorem showing the convergence speed of the estimator. As a corollary, we obtain that, if an approximation algorithm can be encoded by the neural network for some parametrization, then the learned policy will retain the approximation ratio guarantee. On our network design problem, our machine learning policy has the approximation ratio guarantee of the best approximation algorithm known and the numerical efficiency of the best heuristic.<\/jats:p>","DOI":"10.5802\/ojmo.43","type":"journal-article","created":{"date-parts":[[2025,12,2]],"date-time":"2025-12-02T10:22:33Z","timestamp":1764670953000},"page":"1-27","source":"Crossref","is-referenced-by-count":0,"title":["Learning structured approximations of combinatorial optimization problems"],"prefix":"10.5802","volume":"6","author":[{"given":"Axel","family":"Parmentier","sequence":"first","affiliation":[{"name":"CERMICS, ENPC, Institut Polytechnique de Paris, Marne-la-Vall\u00e9e, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"3842","published-online":{"date-parts":[[2025,12,2]]},"reference":[{"key":"key2025121212053915174_1","first-page":"136","article-title":"OptNet: Differentiable Optimization as a Layer in Neural Networks","author":"Amos, Brandon","year":"2017","unstructured":"[1] Amos, Brandon; Kolter, J. Zico OptNet: Differentiable Optimization as a Layer in Neural Networks, Proceedings of the 34th International Conference on Machine Learning, PMLR (2017), pp. 136-145","journal-title":"Proceedings of the 34th International Conference on Machine Learning"},{"key":"key2025121212053915174_2","doi-asserted-by":"publisher","first-page":"919","DOI":"10.1145\/3406325.3451036","article-title":"How Much Data Is Sufficient to Learn High-Performing Algorithms? Generalization Guarantees for Data-Driven Algorithm Design","author":"Balcan, Maria-Florina","year":"2021","unstructured":"[2] Balcan, Maria-Florina; DeBlasio, Dan; Dick, Travis; Kingsford, Carl; Sandholm, Tuomas; Vitercik, Ellen How Much Data Is Sufficient to Learn High-Performing Algorithms? Generalization Guarantees for Data-Driven Algorithm Design, Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, ACM Press (2021), pp. 919-932","journal-title":"Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing"},{"issue":"2","key":"key2025121212053915174_3","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1016\/j.ejor.2020.07.063","article-title":"Machine learning for combinatorial optimization: a methodological tour d\u2019horizon","volume":"290","author":"Bengio, Yoshua","year":"2021","unstructured":"[3] Bengio, Yoshua; Lodi, Andrea; Prouvost, Antoine Machine learning for combinatorial optimization: a methodological tour d\u2019horizon, Eur. J. Oper. Res., Volume 290 (2021) no. 2, pp. 405-421","journal-title":"Eur. J. Oper. Res."},{"key":"key2025121212053915174_4","article-title":"Learning with Differentiable Pertubed Optimizers","author":"Berthet, Quentin","year":"2020","unstructured":"[4] Berthet, Quentin; Blondel, Mathieu; Teboul, Olivier; Cuturi, Marco; Vert, Jean-Philippe; Bach, Francis Learning with Differentiable Pertubed Optimizers, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual (2020)","journal-title":"Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual"},{"issue":"2","key":"key2025121212053915174_5","first-page":"813","article-title":"Best Subset Selection Via a Modern Optimization Lens","volume":"44","author":"Bertsimas, Dimitris","year":"2016","unstructured":"[5] Bertsimas, Dimitris; King, Angela; Mazumder, Rahul Best Subset Selection Via a Modern Optimization Lens, Ann. Stat., Volume 44 (2016) no. 2, pp. 813-852","journal-title":"Ann. Stat."},{"key":"key2025121212053915174_6","first-page":"5230","article-title":"Efficient and Modular Implicit Differentiation","author":"Blondel, Mathieu","year":"2022","unstructured":"[6] Blondel, Mathieu; Berthet, Quentin; Cuturi, Marco; Frostig, Roy; Hoyer, Stephan; Llinares-L\u00f3pez, Felipe; Pedregosa, Fabian; Vert, Jean-Philippe Efficient and Modular Implicit Differentiation, NIPS\u201922: 36th International Conference on Neural Information Processing Systems (2022), pp. 5230-5242","journal-title":"NIPS\u201922: 36th International Conference on Neural Information Processing Systems"},{"key":"key2025121212053915174_7","article-title":"Learning with Fenchel\u2013Young Losses","volume":"21","author":"Blondel, Mathieu","year":"2020","unstructured":"[7] Blondel, Mathieu; Martins, Andr\u00e9 F. T.; Niculae, Vlad Learning with Fenchel\u2013Young Losses, J. Mach. Learn. Res., Volume 21 (2020), 35, 69 pages","journal-title":"J. Mach. Learn. Res."},{"key":"key2025121212053915174_8","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/978-3-540-28650-9_8","article-title":"Introduction to Statistical Learning Theory","volume":"3176","author":"Bousquet, Olivier","year":"2004","unstructured":"[8] Bousquet, Olivier; Boucheron, St\u00e9phane; Lugosi, G\u00e1bor Introduction to Statistical Learning Theory, Advanced Lectures on Machine Learning (Lecture Notes in Computer Science), Volume 3176, Springer, 2004, pp. 169-207","journal-title":"Advanced Lectures on Machine Learning"},{"key":"key2025121212053915174_9","author":"Bronstein, Michael M","year":"2021","unstructured":"[9] Bronstein, Michael M; Bruna, Joan; Cohen, Taco; Veli\u010dkovi\u0107, Petar Geometric deep learning: Grids, groups, graphs, geodesics, and gauges (2021)","journal-title":"Geometric deep learning: Grids, groups, graphs, geodesics, and gauges"},{"key":"key2025121212053915174_10","author":"Dalle, Guillaume","year":"2022","unstructured":"[10] Dalle, Guillaume; Baty, L\u00e9o; Bouvier, Louis; Parmentier, Axel Learning with Combinatorial Optimization Layers: A Probabilistic Approach (2022)","journal-title":"Learning with Combinatorial Optimization Layers: A Probabilistic Approach"},{"issue":"11","key":"key2025121212053915174_11","doi-asserted-by":"publisher","first-page":"1275","DOI":"10.1057\/palgrave.jors.2601389","article-title":"A recovering beam search algorithm for the one-machine dynamic total completion time scheduling problem","volume":"53","author":"Della Croce, Federico","year":"2002","unstructured":"[11] Della Croce, Federico; T\u2019kindt, Vincent A recovering beam search algorithm for the one-machine dynamic total completion time scheduling problem, J. Oper. Res. Soc., Volume 53 (2002) no. 11, pp. 1275-1280","journal-title":"J. Oper. Res. Soc."},{"issue":"1","key":"key2025121212053915174_12","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1287\/mnsc.2020.3922","article-title":"Smart \u201cPredict, Then Optimize\u201d","volume":"68","author":"Elmachtoub, Adam N.","year":"2021","unstructured":"[12] Elmachtoub, Adam N.; Grigas, Paul Smart \u201cPredict, Then Optimize\u201d, Manag. Sci., Volume 68 (2021) no. 1, pp. 9-26","journal-title":"Manag. Sci."},{"issue":"1","key":"key2025121212053915174_13","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/j.ejor.2009.12.004","article-title":"Two-Stage Stochastic Matching and Spanning Tree Problems: Polynomial Instances and Approximation","volume":"205","author":"Escoffier, Bruno","year":"2010","unstructured":"[13] Escoffier, Bruno; Gourv\u00e8s, Laurent; Monnot, J\u00e9r\u00f4me; Spanjaard, Olivier Two-Stage Stochastic Matching and Spanning Tree Problems: Polynomial Instances and Approximation, Eur. J. Oper. Res., Volume 205 (2010) no. 1, pp. 19-30","journal-title":"Eur. J. Oper. Res."},{"key":"key2025121212053915174_14","article-title":"The NLopt Nonlinear-Optimization Package","author":"Johnson, Steven G.","unstructured":"[14] Johnson, Steven G. The NLopt Nonlinear-Optimization Package (http:\/\/github.com\/stevengj\/nlopt, Accessed on 2021-07-04)"},{"issue":"1","key":"key2025121212053915174_15","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/BF00941892","article-title":"Lipschitzian Optimization without the Lipschitz Constant","volume":"79","author":"Jones, D. R.","year":"1993","unstructured":"[15] Jones, D. R.; Perttunen, C. D.; Stuckman, B. E. Lipschitzian Optimization without the Lipschitz Constant, J. Optim. Theory Appl., Volume 79 (1993) no. 1, pp. 157-181","journal-title":"J. Optim. Theory Appl."},{"key":"key2025121212053915174_16","doi-asserted-by":"publisher","first-page":"4475","DOI":"10.24963\/ijcai.2021\/610","article-title":"End-to-End Constrained Optimization Learning: A Survey","author":"Kotary, James","year":"2021","unstructured":"[16] Kotary, James; Fioretto, Ferdinando; Van Hentenryck, Pascal; Wilder, Bryan End-to-End Constrained Optimization Learning: A Survey, Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, International Joint Conferences on Artificial Intelligence Organization (2021), pp. 4475-4482","journal-title":"Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence"},{"key":"key2025121212053915174_17","doi-asserted-by":"publisher","first-page":"1603","DOI":"10.1609\/aaai.v34i02.5521","article-title":"Smart predict-and-optimize for hard combinatorial optimization problems","author":"Mandi, Jayanta","year":"2020","unstructured":"[17] Mandi, Jayanta; Stuckey, Peter J; Guns, Tias et al. Smart predict-and-optimize for hard combinatorial optimization problems, Proceedings of the AAAI Conference on Artificial Intelligence 34(02) (2020), pp. 1603-1610","journal-title":"Proceedings of the AAAI Conference on Artificial Intelligence 34(02)"},{"key":"key2025121212053915174_18","first-page":"3915","article-title":"BayesOpt: A Bayesian Optimization Library for Nonlinear Optimization, Experimental Design and Bandits","volume":"15","author":"Martinez-Cantin, Ruben","year":"2014","unstructured":"[18] Martinez-Cantin, Ruben BayesOpt: A Bayesian Optimization Library for Nonlinear Optimization, Experimental Design and Bandits, J. Mach. Learn. Res., Volume 15 (2014), pp. 3915-3919","journal-title":"J. Mach. Learn. Res."},{"key":"key2025121212053915174_19","author":"Nowak-Vila, Alex","year":"2019","unstructured":"[19] Nowak-Vila, Alex; Bach, Francis; Rudi, Alessandro A general theory for structured prediction with smooth convex surrogates (2019)","journal-title":"A general theory for structured prediction with smooth convex surrogates"},{"issue":"3-4","key":"key2025121212053915174_20","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1561\/0600000033","article-title":"Structured Learning and Prediction in Computer Vision","volume":"6","author":"Nowozin, Sebastian","year":"2010","unstructured":"[20] Nowozin, Sebastian Structured Learning and Prediction in Computer Vision, Found. Trends Comput. Graph. Vision, Volume 6 (2010) no. 3-4, pp. 185-365","journal-title":"Found. Trends Comput. Graph. Vision"},{"issue":"1","key":"key2025121212053915174_21","doi-asserted-by":"publisher","first-page":"606","DOI":"10.1287\/opre.2020.2094","article-title":"Learning to Approximate Industrial Problems by Operations Research Classic Problems","volume":"70","author":"Parmentier, Axel","year":"2022","unstructured":"[21] Parmentier, Axel Learning to Approximate Industrial Problems by Operations Research Classic Problems, Oper. Res., Volume 70 (2022) no. 1, pp. 606-623","journal-title":"Oper. Res."},{"issue":"3","key":"key2025121212053915174_22","doi-asserted-by":"publisher","first-page":"1032","DOI":"10.1016\/j.ejor.2022.06.040","article-title":"Structured learning based heuristics to solve the single machine scheduling problem with release times and sum of completion times","volume":"305","author":"Parmentier, Axel","year":"2023","unstructured":"[22] Parmentier, Axel; T\u2019kindt, Vincent Structured learning based heuristics to solve the single machine scheduling problem with release times and sum of completion times, Eur. J. Oper. Res., Volume 305 (2023) no. 3, pp. 1032-1041","journal-title":"Eur. J. Oper. Res."},{"key":"key2025121212053915174_23","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-2361-4","author":"Pinedo, Michael L","year":"2012","unstructured":"[23] Pinedo, Michael L Scheduling. Theory, algorithms, and systems, Springer, 2012, xx+673 pages","journal-title":"Scheduling. Theory, algorithms, and systems"},{"key":"key2025121212053915174_24","article-title":"Differentiation of Blackbox Combinatorial Solvers","author":"Pogan\u010di\u0107, Marin Vlastelica","year":"2020","unstructured":"[24] Pogan\u010di\u0107, Marin Vlastelica; Paulus, Anselm; Musil, Vit; Martius, Georg; Rolinek, Michal Differentiation of Blackbox Combinatorial Solvers, International Conference on Learning Representations (2020) (https:\/\/openreview.net\/forum?id=BkevoJSYPB)","journal-title":"International Conference on Learning Representations"},{"key":"key2025121212053915174_25","article-title":"Mathematical Foundations of Supervised Learning","author":"Wolf, Michael M.","year":"2018","unstructured":"[25] Wolf, Michael M. Mathematical Foundations of Supervised Learning, 2018 (https:\/\/www-m5.ma.tum.de\/foswiki\/pub\/M5\/Allgemeines\/MA4801_2018S\/ML_notes_main.pdf)"}],"container-title":["Open Journal of Mathematical Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/ojmo.centre-mersenne.org\/item\/10.5802\/ojmo.43.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,12]],"date-time":"2025-12-12T11:07:38Z","timestamp":1765537658000},"score":1,"resource":{"primary":{"URL":"https:\/\/ojmo.centre-mersenne.org\/articles\/10.5802\/ojmo.43\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,2]]},"references-count":25,"alternative-id":["10.5802\/ojmo.43"],"URL":"https:\/\/doi.org\/10.5802\/ojmo.43","relation":{},"ISSN":["2777-5860"],"issn-type":[{"value":"2777-5860","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,2]]},"article-number":"10"}}