背景

算法的可解释性是算法领域共同面临的问题，无论在机器学习、深度学习，还是运筹优化中的启发式、整数规划算法。在机器学习领域，关于算法可解释性的研究较多，有一本书《可解释的机器学习--黑盒模型可解释性理解指南》，其中包含了对算法结果和误差进行解释的技巧。但在运筹优化领域，这方面的研究较少。

本文将重点探讨运筹优化算法的可解释性，特别是整数规划MIP的可解释性。

工作中的常见问题

在智能补货领域，最常见的问题是为什么补货量会这么多或这么少。在VRP问题中，经常被问到的问题是为什么某些客户会被分到同一辆车上，而不是其他客户。这类问题都需要解释算法的逻辑和结果。

算法的可解释性对于说服他人理解和使用算法至关重要。

启发式算法的可解释性

启发式算法分为遗传算法和遗传算法。遗传算法在迭代过程中具有随机性，但只要解释清楚迭代进化的逻辑即可。

关于为什么是结果A而不是结果B的问题，我们可以通过将结果B输入到启发式模型中，执行相应的代码分支来解释。如果结果B不可行，可能是因为目标函数不够好或违反了某些约束。

整数规划MIP的可解释性

MIP问题的可解释性相对较难。虽然MIP问题是数学上可证明的最优解，但仍然会遇到为什么是结果A而不是结果B，以及为什么模型不可行的问题。

对于为什么是结果A而不是结果B的问题，我们可以通过将结果B输入到模型中，了解目标函数是否足够好或是否违反了约束。

MIP无解的原因

对于模型无解的问题，开源求解器没有提供计算IIS的高级功能。通常导致不可行解的原因有以下几点：

IIS

在运筹优化中，IIS代表不可约不可行子系统。它是一种诊断工具，用于确定导致线性规划或混合整数规划模型不可行性的原因。

IIS的定义

不可约：指的是子系统不能进一步减少任何约束或变量而仍保持不可行。换句话说，IIS是导致问题不可行的最小约束和变量集合。

不可行子系统：是指模型中一个子集，该子集中的约束和变量互相矛盾，使得没有解决方案能满足所有的约束条件。

IIS的作用

诊断工具：当一个复杂的优化模型报错为“不可行”时，IIS提供了一种方式来准确定位问题，通过识别导致不可行性的最小集合，使得模型开发者能够更容易地理解冲突并进行调整。

模型调整：一旦识别了IIS，可以通过放宽或修改IIS中的约束，或者调整变量的界来尝试解决不可行性。

IIS的局限性

尽管IIS很有用，但在实际工作中也有局限性。获取IIS后，需要小心验证多方分析，才能找到导致模型不可行的约束，需要较多的经验才能做到。此外，求解器输出的IIS往往较大，约束较多，经常无从下手。

冲突约束分析

除了IIS，还有其他方法可以解决MIP无解的问题。例如，可以尝试删除部分约束或处理不可行的sku，逐步删除约束，找出导致不可行性的约束。

工程实践

在建模框架msopt中，我们将MIP不可行的原因和解决方法应用到实践中。主要有两个要点需要在建模框架中支持。