IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v329y2026i1p24-41.html

Counterfactual explanations for linear optimization

Author

Listed:
  • Kurtz, Jannis
  • Birbil, Ş. İlker
  • den Hertog, Dick

Abstract

In recent years, the concept of counterfactual explanations (CE) has become increasingly important in understanding the inner workings of complex AI systems. In this paper, we introduce the idea of CEs in the context of linear optimization and propose, explain, and analyze three different classes of CEs: relative, weak, and strong. We discuss in which situation each type of CE is needed and examine the structure of the optimization problems that arise from considering them. By detecting and leveraging the underlying convex structure of the relative CE problem, we demonstrate that computing the relative CEs takes the same order of time as solving the original problems. We also address the computational challenges associated with weak and strong CE problems. To illustrate our findings, we present a case study with data sourced from the World Food Programme in which we calculate each type of CE. Finally, we conduct comprehensive numerical experiments using the NETLIB library to demonstrate that relative CE problems can be solved as quickly as solving the original linear optimization problem.

Suggested Citation

  • Kurtz, Jannis & Birbil, Ş. İlker & den Hertog, Dick, 2026. "Counterfactual explanations for linear optimization," European Journal of Operational Research, Elsevier, vol. 329(1), pages 24-41.
    • Handle: RePEc:eee:ejores:v:329:y:2026:i:1:p:24-41
    DOI: 10.1016/j.ejor.2025.06.016
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221725004886
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2025.06.016?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to

    for a different version of it.

    References listed on IDEAS

    as
    1. Dimitris Bertsimas & Arthur Delarue & William Eger & John Hanlon & Sebastien Martin, 2020. "Bus Routing Optimization Helps Boston Public Schools Design Better Policies," Interfaces, INFORMS, vol. 50(1), pages 37-49, January.
    2. Leo Kroon & Dennis Huisman & Erwin Abbink & Pieter-Jan Fioole & Matteo Fischetti & Gábor Maróti & Alexander Schrijver & Adri Steenbeek & Roelof Ybema, 2009. "The New Dutch Timetable: The OR Revolution," Interfaces, INFORMS, vol. 39(1), pages 6-17, February.
    3. Koen Peters & Sérgio Silva & Tim Sergio Wolter & Luis Anjos & Nina van Ettekoven & Éric Combette & Anna Melchiori & Hein Fleuren & Dick den Hertog & Özlem Ergun, 2022. "UN World Food Programme: Toward Zero Hunger with Analytics," Interfaces, INFORMS, vol. 52(1), pages 8-26, January.
    4. Patrice Marcotte & Gilles Savard, 2005. "Bilevel Programming: A Combinatorial Perspective," Springer Books, in: David Avis & Alain Hertz & Odile Marcotte (ed.), Graph Theory and Combinatorial Optimization, chapter 0, pages 191-217, Springer.
    5. Carel Eijgenraam & Ruud Brekelmans & Dick den Hertog & Kees Roos, 2017. "Optimal Strategies for Flood Prevention," Management Science, INFORMS, vol. 63(5), pages 1644-1656, May.
    6. Ruud Brekelmans & Dick den Hertog & Kees Roos & Carel Eijgenraam, 2012. "Safe Dike Heights at Minimal Costs: The Nonhomogeneous Case," Operations Research, INFORMS, vol. 60(6), pages 1342-1355, December.
    7. Hossein Moosaei & Milan Hladík, 2021. "On the Optimal Correction of Infeasible Systems of Linear Inequalities," Journal of Optimization Theory and Applications, Springer, vol. 190(1), pages 32-55, July.
    8. Timothy C. Y. Chan & Rafid Mahmood & Ian Yihang Zhu, 2025. "Inverse Optimization: Theory and Applications," Operations Research, INFORMS, vol. 73(2), pages 1046-1074, March.
    9. Goerigk, Marc & Hartisch, Michael, 2023. "A framework for inherently interpretable optimization models," European Journal of Operational Research, Elsevier, vol. 310(3), pages 1312-1324.
    10. Bogetoft, Peter & Ramírez-Ayerbe, Jasone & Romero Morales, Dolores, 2024. "Counterfactual analysis and target setting in benchmarking," European Journal of Operational Research, Elsevier, vol. 315(3), pages 1083-1095.
    11. Dimitris Bertsimas & Nathan Kallus, 2020. "From Predictive to Prescriptive Analytics," Management Science, INFORMS, vol. 66(3), pages 1025-1044, March.
    12. repec:inm:orijoo:v:3:y:2021:i:2:p:200-226 is not listed on IDEAS
    13. Lizhi Wang, 2013. "Branch-and-bound algorithms for the partial inverse mixed integer linear programming problem," Journal of Global Optimization, Springer, vol. 55(3), pages 491-506, March.
    14. Donato Maragno & Holly Wiberg & Dimitris Bertsimas & Ş. İlker Birbil & Dick den Hertog & Adejuyigbe O. Fajemisin, 2025. "Mixed-Integer Optimization with Constraint Learning," Operations Research, INFORMS, vol. 73(2), pages 1011-1028, March.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Postek, Krzysztof & den Hertog, Dick & Kind, J. & Pustjens, Chris, 2016. "Adjustable Robust Strategies for Flood Protection," Discussion Paper 2016-038, Tilburg University, Center for Economic Research.
    2. Zwaneveld, P. & Verweij, G. & van Hoesel, S., 2018. "Safe dike heights at minimal costs: An integer programming approach," European Journal of Operational Research, Elsevier, vol. 270(1), pages 294-301.
    3. Alessio Ciullo & Jan H. Kwakkel & Karin M. De Bruijn & Neelke Doorn & Frans Klijn, 2020. "Efficient or Fair? Operationalizing Ethical Principles in Flood Risk Management: A Case Study on the Dutch‐German Rhine," Risk Analysis, John Wiley & Sons, vol. 40(9), pages 1844-1862, September.
    4. Thomas David Pol & Jochen Hinkel, 2019. "Uncertainty representations of mean sea-level change: a telephone game?," Climatic Change, Springer, vol. 152(3), pages 393-411, March.
    5. Phouratsamay, Siao-Leu & Scaparra, Maria Paola & Tran, Trung Hieu & Laporte, Gilbert, 2024. "Strategic flood impact mitigation in developing countries’ urban road networks: Application to Hanoi," European Journal of Operational Research, Elsevier, vol. 319(3), pages 862-876.
    6. Postek, Krzysztof & den Hertog, Dick & Kind, J. & Pustjens, Chris, 2016. "Adjustable Robust Strategies for Flood Protection," Other publications TiSEM 6e85c2ff-32dd-4c7e-8d95-a, Tilburg University, School of Economics and Management.
    7. Klerk, Wouter Jan & Kanning, Wim & Kok, Matthijs & Wolfert, Rogier, 2021. "Optimal planning of flood defence system reinforcements using a greedy search algorithm," Reliability Engineering and System Safety, Elsevier, vol. 207(C).
    8. Serrano, Breno & Minner, Stefan & Schiffer, Maximilian & Vidal, Thibaut, 2024. "Bilevel optimization for feature selection in the data-driven newsvendor problem," European Journal of Operational Research, Elsevier, vol. 315(2), pages 703-714.
    9. Giovanni Cerulli & Francesco Caracciolo, 2025. "Risk-Adjusted Policy Learning and the Social Cost of Uncertainty: Theory and Evidence from CAP evaluation," Papers 2510.05007, arXiv.org.
    10. Keliang Wang & Leonardo Lozano & Carlos Cardonha & David Bergman, 2023. "Optimizing over an Ensemble of Trained Neural Networks," INFORMS Journal on Computing, INFORMS, vol. 35(3), pages 652-674, May.
    11. De Clercq, Djavan & Mahdi, Adam, 2024. "Feasibility of machine learning-based rice yield prediction in India at the district level using climate reanalysis and remote sensing data," Agricultural Systems, Elsevier, vol. 220(C).
    12. Meng Qi & Ying Cao & Zuo-Jun (Max) Shen, 2022. "Distributionally Robust Conditional Quantile Prediction with Fixed Design," Management Science, INFORMS, vol. 68(3), pages 1639-1658, March.
    13. Sivanandham, S. & Srivatsa Srinivas, S., 2025. "Enhancing food security at the last-mile: A light-weight and scalable decision support system for the public distribution system in India," Socio-Economic Planning Sciences, Elsevier, vol. 98(C).
    14. Michael F. Gorman & John-Paul Clarke & Amir Hossein Gharehgozli & Michael Hewitt & René de Koster & Debjit Roy, 2014. "State of the Practice: A Review of the Application of OR/MS in Freight Transportation," Interfaces, INFORMS, vol. 44(6), pages 535-554, December.
    15. Adam Behrendt & Martin Savelsbergh & He Wang, 2023. "A Prescriptive Machine Learning Method for Courier Scheduling on Crowdsourced Delivery Platforms," Transportation Science, INFORMS, vol. 57(4), pages 889-907, July.
    16. Luhao Zhang & Jincheng Yang & Rui Gao, 2024. "Optimal Robust Policy for Feature-Based Newsvendor," Management Science, INFORMS, vol. 70(4), pages 2315-2329, April.
    17. Shunichi Ohmori, 2021. "A Predictive Prescription Using Minimum Volume k -Nearest Neighbor Enclosing Ellipsoid and Robust Optimization," Mathematics, MDPI, vol. 9(2), pages 1-16, January.
    18. Twan Dollevoet & Dennis Huisman & Marie Schmidt & Anita Schöbel, 2012. "Delay Management with Rerouting of Passengers," Transportation Science, INFORMS, vol. 46(1), pages 74-89, February.
    19. Christopher Wissuchek & Patrick Zschech, 2025. "Prescriptive analytics systems revised: a systematic literature review from an information systems perspective," Information Systems and e-Business Management, Springer, vol. 23(2), pages 279-353, June.
    20. Tommaso Schettini & Michel Gendreau & Ola Jabali & Federico Malucelli, 2024. "A pattern-based timetabling strategy for a short-turning metro line," Public Transport, Springer, vol. 16(1), pages 1-37, March.

    More about this item

    Keywords

    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:329:y:2026:i:1:p:24-41. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.