尽管混合整数线性规划 (MILP) 确实是 NP 完全的，但也有混合整数线性规划的可解（非平凡）实例。

NP完全意味着混合整数线性规划是：

a) 可在多项式时间内用非确定性图灵机求解（NP 部分）

b) 多项式时间可简化为 3-SAT（完整部分；对于其余的讨论，这部分真的无关紧要）

实际上，由于我们没有非确定性的图灵机，也无法编写诸如“将我们的二元决策变量设置为所有可能的 0 和 1 组合，并求解由此产生的线性规划 (LP)”之类的算法。多项式时间，这意味着在渐近意义上，MILP 是$\mathcal{O}(2^{n})$， 在哪里$n$是二进制变量的数量。该声明意味着，随着问题实例变得非常大，它们将需要大量的计算能力来解决。

该声明并不意味着“小”实例是难以处理的。不幸的是，我无法准确说明小对于 MILP 实例的意义。我经常解决具有 3,000 个或更多二元决策变量的问题。根据问题的表述，这些问题可能需要不到 0.01 秒（这是相对约束不足的问题的情况）或超过一个小时（这是许多约束处于活动状态的问题的情况），因为问题似乎要有良好的结构。我可以说，最先进的 LP 求解器可以求解具有数百万个连续决策变量的 LP，而且如果没有特殊结构，问题实例不太可能在 1,000 到 10 之间，

如果您认为您有 MILP 的可解实例，您将需要使用分支定界或分支切算法。最好的实现是CPLEX和Gurobi。如果您充分挖掘，它们都是具有免费学术许可的商业产品。如果你真的需要一个开源求解器，COIN-OR社区中的项目更合适，尽管源包有时可能很挑剔。最相关的项目是CBC 分支切割求解器、SYMPHONY 求解器、BCP 分支切割价格求解器和ABACUS 分支切割求解器。所有这些项目都需要来自COIN-OR 的多个包，由于其模块化结构。

如果您想尝试多个求解器，最好的办法是使用来自COIN-OR的Open Solver Interface。请注意，此界面的某些部分仅允许您设置基本求解器选项，而要为求解器设置高级选项，您应该查阅COIN-OR的邮件列表以获取更多详细信息。商业 MILP 求解器比开源求解器快得多（有时甚至一个数量级或更多）。原型设计的另一种选择是使用代数建模语言，如GAMS或AMPL。这两个软件包都是商业的，但都有可用于小问题实例的试用版。对于较大的问题实例，您可以将 GAMS 或 AMPL 文件提交给NEOS服务器待解决；该服务器可供公众使用。

如果您有足够大的 MILP 实例，那么这些求解器都不会很好地工作。您可以将整数变量放宽为连续变量，解决问题，然后四舍五入到最接近的整数变量集合，这是您的问题实例的可行解决方案。MILP 的 LP 松弛的最佳解决方案将为您提供 MILP 的最佳目标函数值的下限（当然，假设最小化），而 MILP 的可行解决方案将为您提供最佳目标的上限MILP 的函数值。

如果你真的很幸运并且你的约束矩阵是完全单模的，那么你可以使用 LP 求解器为你的 MILP 生成整数解，尽管它的尺寸很大，你也可以有效地解决你的问题。其他类型的问题具有快速逼近算法，例如背包问题和切割库存问题。对于具有特殊结构的问题，也存在专门的 MILP 分解算法，尽管我不熟悉细节，因为这些主题有些专业，超出了我的论文范围。

我不知道专门针对 MILP 的完全多项式时间逼近方案(FPTAS)，尽管存在包含 MILP 的问题类的 FPTAS（请参阅本文）。我的建议是使用上述混合整数线性规划求解器之一，并结合时间限制和对最优差距的适当容差。这样做将为您在时间限制内为您的 MILP 提供最佳可行解决方案，并且如果求解器在时间限制之前成功终止，则可行解决方案将在您设置的最优性差距容差内达到最优。这个行动过程仍然会给你解决方案的质量界限，因为你的可行解决方案将是一个上限，而求解器可以给你一个适当的下限。不能保证界限在某个因素的最佳解决方案内，但话又说回来，随着近似值变得更好，任何 FPTAS 都会变得更加昂贵。

在确定 MILP 公式之前，您可以做的最重要的事情是选择您能找到的最强公式；您可以在Bertsimas 和 Tsitsiklis的线性优化简介中找到有关如何选择强公式的建议。主要思想是选择一个公式，其约束定义了一个尽可能接近公式的凸包的多面体（另请参阅这些课程说明）。选择一个强有力的公式可以大大缩短解决问题的时间。