混合整数规划(MIP) -基础入门

注意，您还可以看到一个代码示例列表，跨越我们的一系列编程语言2019新万博appmanbetⅩ 页面。

混合整数规划基础

Gurobi并行混合整数规划求解器最常解决的问题为:手机万博登录

摘要目的:	减少cTx
约束:	A x = b(线性约束)
	L≤x≤u(有界约束)
	部分或全部xj必须取整数值(完整性约束)

完整性约束允许MIP模型捕获某些决策的离散性质。例如，一个变量的值被限制为0或1，称为二进制变量，可以用来决定是否采取某些行动，例如建立一个仓库或购买一台新机器。

Gurobi MIP求解器还可手机万博登录以求解具有二次目标和/或二次约束的模型:

摘要目的:	减少xTQ x + QTx
约束:	A x = b(线性约束)
	L≤x≤u(有界约束)
	xT问我x +问我Tx≤b我(二次约束)
	部分或全部x必须取整数值(完整性约束)

具有二次目标但没有二次约束的MIP模型称为混合整数二次规划(MIQP)问题。具有二次约束的MIP模型称为混合整数二次约束规划(MIQCP)问题。没有任何二次特征的模型通常被称为混合整数线性规划(MILP)问题。

下面是Gurobi用来解决MILP模型的算法的描述。MIQP和MIQCP的扩展非常简单，但我们不会在这里描述它们。

和

混合整数线性规划问题通常采用基于线性规划的分支定界算法求解。

概述

基于lsp的基本分支与bound描述如下。我们从最初的MIP开始。由于不知道如何直接解决这个问题，我们取消了所有的完整性限制。得到的LP称为线性规划放松的资料。然后我们可以解这个LP。如果结果碰巧满足所有的完整性限制，即使这些限制没有被明确地强加，那么我们就非常幸运了。这个解是原MIP的一个最优解，我们可以停止。如果不是，就像通常的情况一样，那么通常的步骤是选择一些被限制为整数的变量，但其值在LP松弛中是小数。为了便于讨论，假设这个变量为x，它在LP松弛中的值为5.7。然后，我们可以通过依次施加x≤5.0和x≥6.0的限制来排除这个值。

如果原始MIP表示为P₀，那么我们可以用P来表示这两个新的mip₁，其中x≤5.0,P₂，其中x≥6.0。然后将变量x称为a分支变量，据说我们有支在x上，生成两个子mips P₁和P₂．很明显，如果我们能计算出每一个P的最优解₁和P₂，那么我们可以取这两个解中较好的一个，它将是原始问题P的最优解₀．这样我们就替换了P₀两个更简单(或至少更受限制)的mip。现在，我们将同样的思想应用于这两个MIPs，解决相应的LP松弛，并在必要时选择分支变量。这样我们就得到了a搜索树．由搜索过程生成的mip称为节点和P₀指定的根节点．树的叶子是我们还没有分枝的所有结点。一般来说，如果我们到达了可以求解或以其他方式处理所有叶节点的点，那么我们就已经求解了原始的MIP。

已测节点和在位节点

为了完成我们对(基于lp的)分支和绑定的描述，我们需要描述在处理搜索树的节点时应用的附加逻辑。假设我们的目标是最小化目标，假设我们刚刚解决了搜索树中某个节点的LP松弛。如果在此节点的解满足了原MIP中所有的完整性限制，那么我们就知道我们已经找到了原MIP的一个可行解。接下来我们要采取两个重要步骤。首先，我们将此节点指定为堂哥．没有必要在这个节点上进行分支;它是搜索树上的一片永久的叶子。其次，我们对刚刚找到的可行方案提供的信息进行分析，如下所示。让我们表示在搜索中任何一点找到的最佳整数解为现任．在搜索之初，我们没有在任者。如果我们刚刚找到的整数可行解具有比当前在位者更好的目标函数值(或者如果我们没有在位者)，那么我们将这个解记录为新的在位者，以及它的目标函数值。否则，没有现任更新是必要的，我们只是继续搜索。

还有另外两种可能导致节点被深度挖掘。首先，导致当前节点的分支可能会增加限制，使LP松弛不可行的情况。显然，如果这个节点不包含LP松弛的可行解，那么它就不包含整数可行解。第二种可能性是找到了一个最优松弛解，但其客观值大于当前在位者的松弛解。显然，这个节点不能产生一个更好的整体解决方案，再次可以被理解。

最佳边界和间隙

为了完成对分支和边界的描述，我们还需要引入两个额外的重要值。首先观察，一旦我们有一个任职者，这个任职者的目标值，假设原始的MIP是一个最小化问题，是给定的MIP的最优解的一个有效上界。也就是说，我们不需要接受一个大于这个值的整数解。不太明显的是，在分支定界搜索的任何时候，我们都有一个有效的下界，有时称为最好的肯定．该边界是通过取当前所有叶节点的最优目标值的最小值来获得的。最后，当前上界和下界之间的差称为差距．当间隙为零时，我们已经证明了最优性。

预解，切割平面，启发式，平行度

在混合整数规划领域中，MIP算法的性能近年来有了显著的提高。贡献最大的国家有四个presolve，减少飞机，启发式和并行性．现在，我们将对这四个组件进行概述。

Presolve

预解决是指通常在分支和绑定过程开始之前应用的问题缩减集合。这些裁减的目的是缩小问题的规模，并加强问题的拟订。

下面是缩小大小转换的一个简单示例。假设一个给定的问题包含以下约束:

x₁+ x₂+ x_3.≥15
x₁≤7
x₂≤3
x_3.≤5

显然，满足所有这些约束条件的唯一方法是x₁x = 7,₂= 3, x_3.=5．在这种情况下，我们可以代入这些变量，将它们和上述四个约束完全从公式中删除。这类可能的削减的清单，其中只有一项，是相当广泛的，可对问题的总体规模产生巨大的影响。

上述约简就是我们所说的lp - pressolve约简，因为它的有效性不依赖于完整性限制。下面是一个特定于mip的减少示例。假设x1和x2是非负整数变量，我们的公式包含如下形式的约束:

2 x₁+ 2倍₂≤1。

约束的两边同时除以2得到:

x₁+ x₂≤½。

自从x₁和x₂两者都必须是积分吗，这个不等式清楚地表明x₁+ x₂≤0，所以由非负x₁= x₂= 0。因此，这两个变量和这个约束都可以从公式中去掉。还要注意的是，这个约简在性质上与第一个不同，我们实际上是将可行解集约简为LP松弛，尽管整数可行解集保持不变。这种紧化对整数规划的求解是至关重要的，这也是MIP预解在整数规划求解中比LP预解在线性规划求解中更重要的原因之一。

减少飞机

现在让我们考虑切割平面的想法。我们应该在一开始就说，切割平面的理论是深刻而广泛的。它也被普遍接受为一个最重要的贡献者的计算进步，已经在整数规划在过去几年里。切割平面的想法是，它们通过去除不需要的分式解来加强公式，就像MIP预解的情况一样，但它们在求解过程中这样做，而且不会产生产生额外子问题的不良副作用(不像分支)。

这是一个简单的切割平面的例子。假设我们的公式包含以下约束条件:

6 x₁+ 5 x₂+ 7 x_3.+ 4 x₄+ 5 x₅≤15日

x₁通过x₅被限制为二进制。另外，假设我们刚刚解决了一个LP松弛，这些变量在这个LP松弛中取以下值:x₁x = 0,₂x = 1,_3.= x₄= x₅= 3/4。这个不理想的解可以通过以下观察来排除:因为7 + 4 + 5 = 16 > 15，所以x不可能_3.= x₄= x₅= 1，因此下面的新不等式是给定MIP的有效加法:x_3.+ x₄+ x₅≤2。因为3/4 + 3/4 + 3/4 = 9/4 > 2，新的不等式切断了当前的解。这种不平等就是所谓的背包的封面．

在这一点上，读者可能会问，为什么我们不简单地添加这个新的约束，或者在一开始就削减。有几个原因。一是通常存在大量这样的额外约束。要找到所有的模型太昂贵了，而且很可能不可能将它们全部添加到模型中。第二个原因是，增加约束使LP放松越来越难解决。只有当我们知道这些约束条件会有所帮助时，我们才会添加这些约束条件。明智地添加这些约束可以对解决方案过程产生巨大的有益影响。

启发式

我们讨论的下一个主题是启发式。我们在介绍分支与界时引入了任职者的概念。拥有优秀的在职者，并尽快找到他们，对于MIP搜索来说是非常有价值的，原因有很多。首先，解决可证明最优性的问题可能是不可能的。例如，底层的MIP可能太难了，或者可能存在一些用户强加的限制，限制了我们允许MIP算法运行的时间。在任何一种情况下，我们都希望在终止时得到最佳可行解。有好的可行的解决方案也有助于终止之前的搜索过程。任职者的客观值越好，则LP松弛的值越有可能超过它(在最小化问题中)，从而导致节点被求出。

上述言论旨在表明,它已被证明是非常宝贵的做一点额外的工作的一些搜索树的节点是否良好可以提取整数可行解,即使完整性尚未导致由于分支。例如，可能有许多整数变量，虽然不是整数，但其值非常接近于整数。然后，我们可以考虑将其中一些变量舍入到它们附近的值，将它们固定到这些值上，求解最终的LP松弛，并重复此过程几次，希望所有整数变量都符合要求。如果他们这样做了，如果由此产生的可行性比现任者有更好的客观价值，我们可以取代现任者并继续下去。Gurobi包含了多种不同口味的启发。

并行性

正如本讨论开始时提到的，Gurobi MIP求解器是并行运行的。手机万博登录并行性的主要来源是MIP树搜索中的不同节点可以独立处理。然而，很明显，根节点提供的并行性机会有限。因此，探索大型搜索树的模型可以非常有效地利用核心，而那些将大部分运行时间花在根节点上的模型在利用多个核心的能力方面受到了更多的限制。

其他重要的成分

除了上面讨论的技术之外，现代MIP求解器还将包括一长串附加技术。手机万博登录一些例子包括复杂的分支变量选择技术、节点预解、对称检测和不联合子树检测。在大多数情况下，目标是限制必须探索的分支绑定树的大小。

这里描述的大多数策略和技术的行为都可以使用Gurobi参数进行调整。虽然一些模型可以从参数调优中受益，但我们设计和构建Gurobi Optimizer的目标是让默认设置在广泛的模型中尽可能地发挥作用。通常不需要担心不同技术如何工作的细节，也不需要担心如何调整相关参数。