Elucidating linear programs by neural encodings

Area of Science:

• Artificial Intelligence
• Operations Research
• Machine Learning

Background:

• Linear Programs (LPs) are fundamental to AI and optimization.
• Existing explainable AI (XAI) methods primarily focus on deep learning, neglecting LPs.
• LPs, despite being white-box, present challenges in understanding input-output relationships.

Purpose of the Study:

• To develop methods for explaining the solutions of Linear Programs.
• To adapt existing attribution methods for explaining LP outputs.
• To enhance the interpretability of AI systems that utilize LPs.

Main Methods:

• Encoding Linear Programs into a neural network format.
• Adapting attribution methods like Saliency and LIME for neural LP encodings.
• Evaluating explanation methods on various LPs, including large-scale instances (10k dimensions).

Main Results:

• Neural encoding successfully enables the application of attribution methods to LPs.
• The proposed approach demonstrates the explainability of LP solutions.
• Saliency and LIME show similar performance at low perturbation levels.

Conclusions:

• Linear Programs can and should be explained for better AI transparency.
• Representing LPs as neural networks is a viable strategy for enhancing their explainability.
• This work bridges the gap between optimization and explainable AI.