{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:30:27Z","timestamp":1753893027681,"version":"3.41.2"},"reference-count":33,"publisher":"Frontiers Media SA","license":[{"start":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:00:00Z","timestamp":1750204800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["frontiersin.org"],"crossmark-restriction":true},"short-container-title":["Front. Artif. Intell."],"abstract":"<jats:p>Linear Programs (LPs) are one of the major building blocks of AI and have championed recent strides in differentiable optimizers for learning systems. While efficient solvers exist for even high-dimensional LPs, explaining their solutions has not received much attention yet, as explainable artificial intelligence (XAI) has mostly focused on deep learning models. LPs are mostly considered white-box and thus assumed simple to explain, but we argue that they are not easy to understand in terms of relationships between inputs and outputs. To mitigate this rather non-explainability of LPs we show how to adapt attribution methods by encoding LPs in a neural fashion. The encoding functions consider aspects such as the feasibility of the decision space, the cost attached to each input, and the distance to special points of interest. Using a variety of LPs, including a very large-scale LP with 10k dimensions, we demonstrate the usefulness of explanation methods using our neural LP encodings, although the attribution methods Saliency and LIME are indistinguishable for low perturbation levels. In essence, we demonstrate that LPs can and should be explained, which can be achieved by representing an LP as a neural network.<\/jats:p>","DOI":"10.3389\/frai.2025.1549085","type":"journal-article","created":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:46:58Z","timestamp":1750225618000},"update-policy":"https:\/\/doi.org\/10.3389\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Elucidating linear programs by neural encodings"],"prefix":"10.3389","volume":"8","author":[{"given":"Florian Peter","family":"Busch","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matej","family":"Ze\u010devi\u0107","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kristian","family":"Kersting","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Devendra Singh","family":"Dhami","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1965","published-online":{"date-parts":[[2025,6,18]]},"reference":[{"key":"B1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2211.14736","article-title":"Attribution-based xAI methods in computer vision: a review","author":"Abhishek","year":"2022","journal-title":"arXiv"},{"key":"B2","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-030-28954-6_9","article-title":"\u201cGradient-based attribution methods,\u201d","volume-title":"Explainable AI: Interpreting, Explaining and Visualizing Deep Learning","author":"Ancona","year":"2019"},{"volume-title":"Linear Programming and Network Flows","year":"2008","author":"Bazaraa","key":"B3"},{"key":"B4","article-title":"\u201cRandom forests,\u201d","volume-title":"Machine Learning","author":"Breiman","year":"2001"},{"key":"B5","article-title":"\u201cHow important is a neuron,\u201d","volume-title":"International Conference on Learning Representations","author":"Dhamdhere","year":"2019"},{"key":"B6","first-page":"34","article-title":"\u201cMIPaaL: Mixed integer program as a layer,\u201d","volume-title":"Proceedings of the AAAI Conference on Artificial Intelligence","author":"Ferber","year":"2020"},{"key":"B7","doi-asserted-by":"crossref","DOI":"10.1016\/j.ifacol.2018.08.289","article-title":"\u201cWorkforce scheduling linear programming formulation,\u201d","volume-title":"IFAC-PapersOnLine","author":"Garaix","year":"2018"},{"volume-title":"Darpa's Explainable Artificial Intelligence (xAI) Program","year":"2019","author":"Gunning","key":"B8"},{"key":"B9","first-page":"34","article-title":"\u201cFast axiomatic attribution for neural networks,\u201d","volume-title":"Advances in Neural Information Processing Systems","author":"Hesse","year":"2021"},{"key":"B10","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1137\/0101002","article-title":"Computational experience in solving linear programs","volume":"1","author":"Hoffman","year":"1953","journal-title":"J. Soc. Indust. Appl. Mathem"},{"key":"B11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0377-2217(97)00330-5","article-title":"A generalized linear programming model for nurse scheduling","volume":"107","author":"Jaumard","year":"1998","journal-title":"Eur. J. Operat. Res"},{"journal-title":"Captum: A Unified and Generic Model Interpretability Library for PyTorch","year":"2020","author":"Kokhlikyan","key":"B12"},{"key":"B13","article-title":"\u201cImageNet classification with deep convolutional neural networks,\u201d","volume-title":"Advances in Neural Information Processing Systems","author":"Krizhevsky","year":"2012"},{"key":"B14","article-title":"\u201cOn the power of small-size graph neural networks for linear programming,\u201d","volume-title":"The Thirty-Eighth Annual Conference on Neural Information Processing Systems","author":"Li","year":"2024"},{"key":"B15","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.1312.5602","article-title":"Playing atari with deep reinforcement learning","author":"Mnih","year":"2013","journal-title":"arXiv"},{"key":"B16","first-page":"25","article-title":"Infeasibility analysis for linear systems, a survey","volume":"2000","author":"Murty","year":"2000","journal-title":"Arab. J. Sci. Eng"},{"key":"B17","article-title":"\u201cComboptnet: Fit the right np-hard problem by learning integer programming constraints,\u201d","volume-title":"International Conference on Machine Learning","author":"Paulus","year":"2021"},{"key":"B18","doi-asserted-by":"crossref","DOI":"10.1145\/2939672.2939778","article-title":"\u201c\"why should i trust you?\" explaining the predictions of any classifier,\u201d","volume-title":"Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining","author":"Ribeiro","year":"2016"},{"key":"B19","doi-asserted-by":"publisher","first-page":"1508","DOI":"10.1016\/j.envsoft.2010.04.012","article-title":"How to avoid a perfunctory sensitivity analysis","volume":"25","author":"Saltelli","year":"2010","journal-title":"Environm. Model. Softw"},{"key":"B20","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/j.enpol.2011.12.040","article-title":"Transmission grid extensions for the integration of variable renewable energies in europe: Who benefits where?","volume":"43","author":"Schaber","year":"2012","journal-title":"Energy Policy"},{"key":"B21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10618-022-00867-8","article-title":"A comprehensive taxonomy for explainable artificial intelligence: a systematic survey of surveys on methods and concepts","volume":"2023","author":"Schwalbe","year":"2023","journal-title":"Data Mining Knowl. Discov"},{"key":"B22","doi-asserted-by":"crossref","DOI":"10.1109\/ICCV.2017.74","article-title":"\u201cGrad-CAM: Visual explanations from deep networks via gradient-based localization,\u201d","volume-title":"Proceedings of the IEEE International Conference on Computer Vision","author":"Selvaraju","year":"2017"},{"key":"B23","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.1807.09946","article-title":"Computationally efficient measures of internal neuron importance","author":"Shrikumar","year":"2018","journal-title":"arXiv"},{"key":"B24","article-title":"\u201cDeep inside convolutional networks: Visualising image classification models and saliency maps,\u201d","volume-title":"Workshop at International Conference on Learning Representations","author":"Simonyan","year":"2014"},{"key":"B25","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-030-81691-9_12","article-title":"\u201cFRaGenLP: A generator of random linear programming problems for cluster computing systems,\u201d","volume-title":"International Conference on Parallel Computational Technologies","author":"Sokolinsky","year":"2021"},{"key":"B26","doi-asserted-by":"crossref","DOI":"10.1109\/CVPR46437.2021.00362","article-title":"\u201cRight for the right concept: Revising neuro-symbolic concepts by interacting with their explanations,\u201d","volume-title":"Proceedings of the IEEE\/CVF Conference on Computer Vision and Pattern Recognition","author":"Stammer","year":"2021"},{"key":"B27","article-title":"\u201cAxiomatic attribution for deep networks,\u201d","volume-title":"International Conference on Machine Learning","author":"Sundararajan","year":"2017"},{"key":"B28","doi-asserted-by":"crossref","DOI":"10.1145\/3306618.3314293","article-title":"\u201cExplanatory interactive machine learning,\u201d","volume-title":"Proceedings of the 2019 AAAI\/ACM Conference on AI, Ethics, and Society","author":"Teso","year":"2019"},{"key":"B29","article-title":"\u201cAttention is all you need,\u201d","volume-title":"Advances in Neural Information Processing Systems","author":"Vaswani","year":"2017"},{"key":"B30","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/BF02055188","article-title":"Approaches to sensitivity analysis in linear programming","volume":"27","author":"Ward","year":"1990","journal-title":"Ann. Operations Res"},{"key":"B31","article-title":"\u201cMap estimation, linear programming and belief propagation with convex free energies,\u201d","volume-title":"Uncertainty in Artificial Intelligence","author":"Weiss","year":"2007"},{"key":"B32","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/j.neucom.2022.11.053","article-title":"A deep learning approach for solving linear programming problems","volume":"520","author":"Wu","year":"2023","journal-title":"Neurocomputing"},{"key":"B33","article-title":"\u201cVisualizing and understanding convolutional networks,\u201d","author":"Zeiler","year":"2014","journal-title":"European Conference on Computer Vision"}],"container-title":["Frontiers in Artificial Intelligence"],"original-title":[],"link":[{"URL":"https:\/\/www.frontiersin.org\/articles\/10.3389\/frai.2025.1549085\/full","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:47:08Z","timestamp":1750225628000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.frontiersin.org\/articles\/10.3389\/frai.2025.1549085\/full"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,18]]},"references-count":33,"alternative-id":["10.3389\/frai.2025.1549085"],"URL":"https:\/\/doi.org\/10.3389\/frai.2025.1549085","relation":{},"ISSN":["2624-8212"],"issn-type":[{"type":"electronic","value":"2624-8212"}],"subject":[],"published":{"date-parts":[[2025,6,18]]},"article-number":"1549085"}}