One-for-Many Counterfactual Explanations by Column Generation

References

• Angwin J, Larson J, Mattu S, Kirchner L (2019) Machine bias: There’s software used across the country to predict future criminals and it’s biased against blacks. Accessed February 3, 2026, https://www.propublica.org/article/machine-bias-risk-assessments-in-criminal-sentencing.Google Scholar
• Artelt A, Gregoriades A (2024) A two-stage algorithm for cost-efficient multi-instance counterfactual explanations. Preprint, submitted March 2, https://arxiv.org/abs/2403.01221.Google Scholar
• Artelt A, Hammer B (2019) On the computation of counterfactual explanations: A survey. Preprint, submitted November 15, https://arxiv.org/abs/1911.07749.Google Scholar
• Baesens B, Setiono R, Mues C, Vanthienen J (2003) Using neural network rule extraction and decision tables for credit-risk evaluation. Management Sci. 49(3):312–329.Link, Google Scholar
• Barnhart C, Johnson EL, Nemhauser GL, Savelsbergh MW, Vance PH (1998) Branch-and-price: Column generation for solving huge integer programs. Oper. Res. 46(3):316–329.Link, Google Scholar
• Bergman D, Huang T, Brooks P, Lodi A, Raghunathan AU (2022) JANOS: An integrated predictive and prescriptive modeling framework. INFORMS J. Comput. 34(2):807–816.Link, Google Scholar
• Bewley T, Amoukou SI, Mishra S, Magazzeni D, Veloso M (2024) Counterfactual metarules for local and global recourse. Salakhutdinov R, Kolter Z, Heller K, Weller A, Oliver N, Scarlett J, Berkenkamp F, eds. Proc. 41st Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 235 (PMLR, Cambridge, MA), 3707–3724.Google Scholar
• Cacciola M, Frangioni A, Lodi A (2024) Structured pruning of neural networks for constraints learning. Oper. Res. Lett. 57:107194.Google Scholar
• Carrizosa E, Ramírez-Ayerbe J, Romero Morales D (2024a) Generating collective counterfactual explanations in score-based classification via mathematical optimization. Expert Systems Appl. 238 (Part D):121954.Google Scholar
• Carrizosa E, Ramírez-Ayerbe J, Romero Morales D (2024b) Mathematical optimization modelling for group counterfactual explanations. Eur. J. Oper. Res. 319(2):399–412.Google Scholar
• Ceccon F, Jalving J, Haddad J, Thebelt A, Tsay C, Laird CD, Misener R (2022) OMLT: Optimization & machine learning toolkit. J. Machine Learn. Res. 23(349):1–8.Google Scholar
• Cortez P (2014) Student performance [dataset]. UCI Machine Learning Repository, Accessed February 3, 2026, https://doi.org/10.24432/C5TG7T.Google Scholar
• Cortez P, Silva AMG (2008) Using data mining to predict secondary school student performance. https://api.semanticscholar.org/CorpusID:16621299.Google Scholar
• Du M, Liu N, Hu X (2019) Techniques for interpretable machine learning. Comm. ACM 63(1):68–77.Google Scholar
• Dua D, Graff C (2019) UCI machine learning repository. Accessed February 3, 2026, http://archive.ics.uci.edu/ml.Google Scholar
• Fischetti M, Jo J (2018) Deep neural networks and mixed integer linear optimization. Constraints 23(3):296–309.Google Scholar
• Guidotti R (2024) Counterfactual explanations and how to find them: Literature review and benchmarking. Data Mining Knowledge Discovery 38(5):2770–2824.Google Scholar
• Gurobi Optimization, LLC (2024) Gurobi Optimizer reference manual. Accessed February 3, 2026, https://www.gurobi.com.Google Scholar
• Jung J, Concannon C, Shroff R, Goel S, Goldstein D (2020) Simple rules to guide expert classifications. J. Roy. Statist. Soc. Ser. A (Statist. Soc.) 183(3):771–800.Google Scholar
• Kanamori K, Takagi T, Kobayashi K, Ike Y (2022) Counterfactual explanation trees: Transparent and consistent actionable recourse with decision trees. Camps-Valls G, Ruiz FJR, Valera I, eds. Proc. 25th Internat. Conf. Artificial Intelligence Statist., Proceedings of Machine Learning Research, vol. 151 (PMLR, Cambridge, MA), 1846–1870.Google Scholar
• Karimi AH, Barthe G, Balle B, Valera I (2020) Model-agnostic counterfactual explanations for consequential decisions. Chiappa S, Calandra R, eds. Proc. 23rd Internat. Conf. Artificial Intelligence Statist., Proceedings of Machine Learning Research, vol. 108 (PMLR, Cambridge, MA), 895–905.Google Scholar
• Karimi AH, Barthe G, Schölkopf B, Valera I (2022) A survey of algorithmic recourse: Contrastive explanations and consequential recommendations. ACM Comput. Survey 55(5):1–29.Google Scholar
• Keane M, Smyth B (2020) Good counterfactuals and where to find them: A case-based technique for generating counterfactuals for explainable AI (XAI). Watson I, Weber R, eds. Proc. 28th Internat. Conf. Case-Based Reasoning (ICCBR), Lecture Notes in Computer Science, vol. 12311 (Springer, Cham, Switzerland), 163–178.Google Scholar
• Ley D, Mishra S, Magazzeni D (2023) Globe-ce: A translation-based approach for global counterfactual explanations. Krause A, Brunskill E, Cho K, Engelhardt B, Sabato S, Scarlett J, eds. Proc. 40th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 202 (PMLR, Cambridge, MA), 19315–19342.Google Scholar
• Martens D, Provost F (2014) Explaining data-driven document classifications. MIS Quart. 38(1):73–99.Google Scholar
• Miller T (2019) Explanation in artificial intelligence: Insights from the social sciences. Artificial Intelligence 267:1–38.Google Scholar
• Mitsos A, Chachuat B, Barton PI (2009) McCormick-based relaxations of algorithms. SIAM J. Optim. 20(2):573–601.Google Scholar
• Molnar C, Casalicchio G, Bischl B (2020) Interpretable machine learning: A brief history, state-of-the-art and challenges. Koprinska I, Kamp M, Appice A, Loglisci C, Antonie L, Zimmermann A, Guidotti R, et al., eds. ECML PKDD 2020 Workshops, Communications in Computer and Information Science, vol. 1323 (Springer, Cham, Switzerland), 417–431.Google Scholar
• Mothilal R, Sharma A, Tan C (2020) Explaining machine learning classifiers through diverse counterfactual explanations. Hildebrandt M, Castillo C, Celis E, Ruggieri S, Taylor L, Zanfir-Fortuna G, eds. Proc. Conf. Fairness Accountability Transparency (Association for Computing Machinery, New York), 607–617.Google Scholar
• Parmentier A, Vidal T (2021) Optimal counterfactual explanations in tree ensembles. Meila M, Zhang T, eds. Proc. 38th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 139 (PMLR, Cambridge, MA), 8422–8431.Google Scholar
• Patel K (2023) Column generation estimator. Accessed February 3, 2026, https://github.com/krooonal/col_gen_estimator/tree/frameworkdev.Google Scholar
• Rawal K, Lakkaraju H (2020) Beyond individualized recourse: Interpretable and interactive summaries of actionable recourses. Adv. Neural Inform. Processing Systems 33:12187–12198.Google Scholar
• Rudin C, Chen C, Chen Z, Huang H, Semenova L, Zhong C (2022) Interpretable machine learning: Fundamental principles and 10 grand challenges. Statist. Survey 16:1–85.Google Scholar
• Sokol K, Flach P (2019) Counterfactual explanations of machine learning predictions: Opportunities and challenges for AI safety. Proc. AAAI Workshop Artificial Intelligence Safety 2019 (SafeAI), CEUR Workshop Proceedings, vol. 2301 (CEUR-WS.org, Aachen, Germany).Google Scholar
• Stepin I, Alonso J, Catala A, Pereira-Fariña M (2021) A survey of contrastive and counterfactual explanation generation methods for explainable artificial intelligence. IEEE Access 9:11974–12001.Google Scholar
• Ustun B, Spangher A, Liu Y (2019) Actionable recourse in linear classification. Proc. Conf. Fairness Accountability Transparency (Association for Computing Machinery, New York), 10–19.Google Scholar
• Verma S, Boonsanong V, Hoang M, Hines K, Dickerson J, Shah C (2020) Counterfactual explanations and algorithmic recourses for machine learning: A review. Preprint, submitted October 20, https://arxiv.org/abs/2010.10596.Google Scholar
• Wachter S, Mittelstadt B, Russell C (2017) Counterfactual explanations without opening the black box: Automated decisions and the GDPR. Harvard J. Law Tech. 31(2):841–887.Google Scholar
• Warren G, Keane MT, Gueret C, Delaney E (2023) Explaining groups of instances counterfactually for XAI: A use case, algorithm and user study for group-counterfactuals. Preprint, submitted March 16, https://arxiv.org/abs/2303.09297.Google Scholar
• Zeng J, Ustun B, Rudin C (2017) Interpretable classification models for recidivism prediction. J. Roy. Statist. Soc.: Ser. A 180(3):689–722.Google Scholar
• Zeng J, Gensheimer M, Rubin D, Athey S, Shachter R (2022) Uncovering interpretable potential confounders in electronic medical records. Nature Comm. 13(1):1014.Google Scholar
• Zhang Y, Song K, Sun Y, Tan S, Udell M (2019) “Why should you trust my explanation?” Understanding uncertainty in LIME explanations. Preprint, submitted April 29, https://arxiv.org/abs/1904.12991.Google Scholar