约束条件#
Gurobi中的约束捕获了一组变量可能取值上的限制。最简单的例子是线性约束，它规定了一组变量上的线性表达式取值要么小于等于、大于等于，要么等于另一个线性表达式。还支持更复杂的约束，包括二次约束（例如，\(x^2 + y^2 \leq z^2\)）、逻辑约束（例如，二进制变量上的逻辑与、如果-那么等），以及一些非线性函数（例如，\(y = \sin(x)\)）。
我们现在考虑一些关于 线性, SOS, 二次（包括凸和非凸）以及 一般 约束的更多细节。一般约束是我们用于那些不适合其他类别的约束类型的统称。
回想一下，Gurobi 在有限精度算术中工作，因此约束只能满足到容忍度。可以收紧容忍度以减少此类违规，但违规的程度是有限制的——误差是浮点算术中固有的。这一点将在本节中的多个地方重申。
线性约束#
线性约束允许您限制线性表达式的值。例如，您可能要求任何可行解满足约束\(3 x + 4 y \leq 5z\)。请注意，面向矩阵的Gurobi API（C、MATLAB和R）要求线性约束的右侧为常数，而面向对象的API（C++、Java、.NET和Python）允许比较符两侧的任意线性表达式。
计算出的解应满足所述约束条件，误差在FeasibilityTol范围内（尽管在数值不稳定的情况下可能不满足——我们稍后会讨论这一点）。
Gurobi 支持一组有限的比较器。具体来说，你可以将一个表达式约束为小于等于、大于等于或等于另一个表达式。我们不支持严格小于、严格大于或不等于的比较器。虽然这些其他比较器在数学编程中可能看起来合适，但我们排除了它们，以避免与数值容差相关的潜在混淆。考虑一个简单的例子，即对一对连续变量的严格不等式约束：\(x > y\)。为了满足约束条件，\(x-y\) 需要多大？与其尝试在求解器中嵌入一种微妙且可能令人困惑的处理此类约束的策略，我们选择不支持它们。
SOS约束#
特殊有序集（Special-Ordered Set，简称SOS约束）是一种高度专业化的约束，它对给定列表中变量可以取的值施加限制。SOS约束有两种类型。在类型1的SOS约束（SOS1约束）中，指定列表中最多允许一个变量取非零值。在类型2的SOS约束（SOS2约束）中，指定有序列表中最多允许两个变量取非零值，并且这些非零变量在列表中必须是连续的。SOS约束中的变量可以是连续的、整数的或二进制的。
再次强调，容差在SOS约束中起着重要作用。 具体来说，对于确定SOS约束是否满足的目的，取值小于 IntFeasTol（绝对值）的变量被视为零。
一个SOS约束是通过使用变量列表和相应的权重列表来描述的。虽然权重在历史上具有与之相关的直观含义，但我们仅使用它们来对变量列表进行排序。权重应该是唯一的。这对于SOS2约束尤其重要，因为它依赖于连续变量的概念。由于SOS中的变量是按权重排序的，当多个变量具有相同的权重时，连续性就会变得模糊。
通常使用线性约束而不是SOS约束来捕捉SOS结构更为高效。优化器通常会自动执行这种重构。这是通过四个参数控制的：PreSOS1BigM、PreSOS1Encoding、PreSOS2BigM和PreSOS2Encoding。
重新表述添加了形式为\(x \leq M b\)的约束，其中 \(x\)是参与SOS约束的变量， \(b\)是一个二进制变量，而\(M\)是变量 \(x\)值的上限。\(M\)的大值可能导致 数值问题。两个参数PreSOS1BigM和 PreSOS2BigM控制通过此重新表述可以引入的 \(M\)的最大值。需要更大值的SOS约束 不会被转换。将其中一个参数设置为0会禁用相应的重新表述。
此外，SOS1和SOS2约束有几种已知的整数公式。这些重新公式化在引入问题的变量数量、结果LP松弛的复杂性以及它们在分支和切割平面方面的特性上有所不同。两个参数PreSOS1Encoding和PreSOS2Encoding控制所执行的重新公式化的选择。
二次约束#
二次约束允许您限制二次表达式的值。例如，您可能要求任何可行解满足约束\(3 x^2 + 4 y^2 + 5 z \leq 10\)。请注意，面向矩阵的Gurobi API（C、MATLAB和R）要求二次约束的右侧为常数，而面向对象的API（C++、Java、.NET和Python）允许比较符两侧的任意二次表达式。
计算出的解应满足所述约束，误差在FeasibilityTol范围内。二次约束通常比线性约束更难满足，因此收紧该参数可能会显著增加运行时间。
Gurobi 可以处理凸和非凸的二次约束。然而，在处理不同类型的约束时存在一些微妙而重要的差异。通常，解决所有约束都具有凸可行域的模型要容易得多。实际上，识别所有这些情况相当困难，但以下形式总是被识别：
\(x^TQx + q^Tx \le b\), 其中 \(Q\) 是半正定 (PSD)
\(x^TQx \le y^{2}\)，其中 \(Q\) 是半正定 (PSD)，\(x\) 是变量向量，\(y\) 是 非负变量（如果 \(Q = I\)，单位矩阵，则为二阶锥约束）
\(x^TQx \le y z\)，其中 \(Q\) 是半正定 (PSD)，\(x\) 是变量向量，\(y\) 和 \(z\) 是非负变量（如果 \(Q = I\)，单位矩阵，则为旋转二阶锥 约束）
更准确地说，如果预求解能够将二次约束转换为以下形式之一，那么它总是会被识别为凸的。请注意，如果二次约束中的所有二次项至少包含一个二元变量，那么预求解总是能够将其转换为凸形式。
为什么要区分凸和非凸二次约束？在某些情况下，您可能知道您的问题应该是凸的，因此如果您的模型未被识别为凸的，这可能是建模错误的迹象。为了避免意外解决比您预期更困难的问题，您可以将非凸参数设置为0或1。在默认设置-1或如果非凸参数设置为2时，Gurobi将接受任意二次约束，并尝试使用适当的算法解决生成的模型。
请注意，其他非凸二次求解器通常只能找到局部最优解。Gurobi中的算法探索整个搜索空间，因此它们提供了一个全局有效的下界，用于最优目标值，并且如果有足够的时间，它们将找到一个全局最优解（受限于容差）。
我们想在这里指出一个关于术语的微妙之处。一个仅涉及不相交变量对乘积的二次约束通常被称为双线性约束，而包含双线性约束的模型通常被称为双线性规划。双线性约束是非凸二次约束的一个特例，Gurobi用于处理后者的算法也非常适合解决双线性规划问题。
一般约束#
Gurobi 包含一组额外的高级约束，我们统称为一般约束。这些约束允许您直接建模变量之间的复杂关系。我们认为这些约束属于三种类型，Gurobi 对它们的处理方式不同：简单约束、函数约束和非线性约束。
简单约束 是一种建模便利。它们允许你声明变量之间的相当简单的关系（最小值、最大值、绝对值、逻辑或等）。将这些约束转换为较低级别的建模对象（通常使用辅助二进制变量和线性或SOS约束）的技术是众所周知的，并且可以在优化建模教科书中找到。通过自动化这些转换并消除建模者执行它们的需要，希望这些简单的通用约束将使你能够编写更具可读性和更易维护的模型。
其他两种类型的约束允许您通过非线性函数\(y=f(x)\)来声明模型中变量之间的关系。这两种约束类型在它们所能表示的函数的通用性上有所不同。使用函数约束，您只能声明从预定义列表中选择的单变量函数：\(f: \mathbf{R} \rightarrow \mathbf{R}\)。使用非线性约束，您可以声明多变量函数：\(f: \mathbf{R}^n \rightarrow \mathbf{R}\)，这些函数由各种操作的组合产生，可能涉及多个变量。
非线性约束 是更一般的形式，可以用来表示所有函数约束（以及线性和二次约束）。根据你使用的API，编写非线性约束可能比编写函数约束更复杂。在Python中，非线性约束可以自然地表达，除了在非常特殊的情况下，应该更方便且更好用。
注意
类似于非凸二次约束，Gurobi旨在解决包含非线性约束的模型以达到全局最优。请注意，这与寻求局部最优解且不旨在证明全局最优性的求解器不同。
简单约束#
Gurobi 支持以下简单的通用约束，每个约束都有其自己的语法和语义：
MAX 约束： 约束 \(r = \max\{x_1,\ldots,x_k,c\}\) 表示 结果变量 \(r\) 应等于 操作变量 \(x_1,\ldots,x_k\) 和 常数 \(c\) 的最大值。例如，解 \((r=3, x_1=2, x_2=3, x_3=0)\) 对于约束 \(r = \max\{x_1,x_2,x_3,1.7\}\) 是可行的，因为 \(3\) 确实是 \(2\)、\(3\)、\(0\) 和 \(1.7\) 的最大值。
MIN约束： 类似于MAX约束，约束 \(r = \min\{x_1,\ldots,x_k,c\}\) 表示结果变量 \(r\) 应等于操作变量 \(x_1,\ldots,x_k\) 和常数 \(c\) 的最小值。
ABS约束：约束\(r = \mbox{abs}\{x\}\)表示 结果变量\(r\)应等于 操作数变量\(x\)的绝对值。例如，一个 解\((r=3, x=-3)\)对于约束 \(r = \mbox{abs}\{x\}\)是可行的。
AND 约束： 约束 \(r = \mbox{and}\{x_1,\ldots,x_k\}\) 表示二进制 结果变量 \(r\) 应该为 \(1\) 当且仅当所有 二进制 操作数变量 \(x_1,\ldots,x_k\) 都等于 \(1\)。例如，解 \((r=1, x_1=1, x_2=1, x_3=1)\) 对于约束 \(r = \mbox{and}\{x_1,x_2,x_3\}\) 是可行的。注意，任何涉及的 非二进制变量都会被转换为二进制。
OR 约束： 类似于 AND 约束，约束 \(r = \mbox{or}\{x_1,\ldots,x_k\}\) 表示二进制 结果变量 \(r\) 应该为 \(1\) 当且仅当至少一个二进制 操作数变量 \(x_1,\ldots,x_k\) 等于 \(1\)。请注意，任何未已经是二进制的相关变量都将被转换为二进制。
NORM约束： 约束 \(r = \mbox{norm}\{x_1,\ldots,x_k\}\) 表示结果变量 \(r\) 应等于 操作变量 \(x_1,\ldots,x_k\) 的向量范数。有几种选项可用：0-范数、1-范数、2-范数和无穷范数。
INDICATOR 约束： 一个指示器约束 \(y = f \rightarrow a^Tx \leq b\) 表示如果二进制 指示变量 \(y\) 在给定解中等于 \(f\)，其中 \(f \in \{0,1\}\)，则线性约束 \(a^Tx \leq b\) 必须被满足。另一方面，如果 \(y \neq f\)（即 \(y = 1-f\)），则线性约束 可能被违反。请注意，线性约束的方向也可以是 \(=\) 或 \(\geq\)；请参阅 前面的部分 以获取 关于线性约束的更详细描述。还请注意， 声明一个 INDICATOR 约束会隐式声明指示变量为二进制类型。
分段线性约束： 分段线性约束 \(y = f(x)\) 表示点 \((x, y)\) 必须位于由一组点 \((x_1, y_1), (x_2, y_2), ..., (x_n, y_n)\) 定义的分段线性函数 \(f\) 上。有关分段线性函数如何定义的详细信息，请参阅 分段线性目标 的描述。
请注意，将任何这些约束添加到原本连续的模型中会将其转换为MIP。
如上所述，每个简单的通用约束都有一个等效的MIP公式，该公式由线性和SOS约束组成，可能还包括辅助变量。因此，您始终可以自己建模这些约束，而不使用Gurobi的通用约束。例如，MAX约束\(r = \max\{x_1,\ldots,x_k,c\}\)可以如下建模：
前两个约束条件表明 \(r \geq \max\{x_1,\ldots,x_k,c\}\)，即结果变量 \(r\) 必须至少与每个操作数变量 \(x_j\) 和常数 \(c\) 一样大。这可以使用不等式来建模，但显式的松弛变量在接下来的约束条件中起着重要作用。
接下来的两个约束强制 \(r \leq \max\{x_1,\ldots,x_k,c\}\)，这确保了\(r\)等于MAX表达式。强制等式的这一边实际上要复杂得多。我们需要引入二进制辅助变量\(z_j \in \{0,1\}\)，以及SOS1约束，要求两个变量\(s_j\)和\(z_j\)中最多只能有一个非零，这模拟了\(z_j = 1 \rightarrow s_j = 0\)的含义。由于第三个约束，一个\(z_j\)将等于\(1\)，因此至少有一个\(s_j\)将为零。因此，由于第一个约束，至少有一个\(j\)使得\(r = x_j\)，或者由于第二个约束使得\(r = c\)。
容差在一般约束中起着作用，尽管正如你所预期的，具体的作用取决于约束类型。一般来说，结果中的违规将小于可行性容差，而整数结果中的完整性违规也将满足完整性容差。
在大多数情况下，通用约束只是一种简洁地捕捉变量之间关系的手段，同时消除了创建等效MIP公式的负担。然而，通用约束还有另一个潜在的优势：如果Gurobi在预处理过程中能够证明简化版本足以保证模型的正确性，那么它可能能够简化MIP公式。因此，Gurobi可能能够生成比最通用公式更小或更紧凑的通用约束表示。例如，可能\(r \leq \max\{x_1,\ldots,x_k,c\}\)已经被模型中的其他约束所隐含，因此只需要一组简单的不等式。
描述 \(r \geq \max\{x_1,\ldots,x_k,c\}\) 足以建模 MAX 约束的相关部分。
范数约束#
范数约束引入了一些需要注意的复杂性。如上所述，此约束允许您将一个变量设置为变量向量的范数。有几种范数可用。L1范数等于操作数变量绝对值的总和。L-无穷范数等于任何操作数的最大绝对值。L2范数等于操作数平方和的平方根。L0范数计算操作数中非零值的数量。
关于L2范数，一个明显的复杂性来自于这样一个事实：强制执行它需要一个二次约束。如果你的模型只从上方限制结果（例如，\(r = ||x|| \leq 1\)），那么得到的约束将是凸的。如果你的模型在其他方面是凸的，那么得到的模型将是一个（凸的）QCP。然而，如果你试图从下方限制结果（例如，\(r = ||x|| \geq y\)），添加L2范数约束将导致一个非凸的QCP模型，这通常会显著增加求解的难度。
关于L0范数，需要注意的是，使用此约束获得的结果可能会违反直觉。这是因为对于几乎任何变量恰好为0的可行解，您都可以向该变量添加一个小值，同时仍然满足所有相关约束的容差。最终结果是，L0范数的下限通常通过“作弊”来满足——通过将足够多的变量设置为略微不同于零的值。我们强烈建议您仅从上方限制结果。也就是说，您应避免在模型激励较大值的情况下使用结果。这包括目标系数为负的情况，以及变量较大值有助于满足约束的情况（例如，结果以正系数出现的大于约束）。
函数约束#
Gurobi 支持以下函数约束，每种约束的语法和语义略有不同（下面的 \(x\) 和 \(y\) 是 Gurobi 决策变量，其他项是在将约束添加到模型时作为输入提供的常量）：
多项式: \(y = p_0 x^n + p_1 x^{n-1} + ... + p_{n-1} x + p_n\)
自然指数： \(y = \exp(x)\) 或 \(y = e^x\)
指数函数: \(y = a^x\), 其中 \(a > 0\) 是指数函数的底数
自然对数： \(y = \log_e(x)\) 或 \(y = \ln(x)\)
对数： \(y = \log_a(x)\)，其中 \(a > 0\) 是对数函数的底数
逻辑回归: \(y = \frac{1}{1 + \exp(-x)}\) 或 \(y = \frac{1}{1 + e^{-x}}\)
幂函数: \(y = x^a\), 其中 \(x \geq 0\) 对于任何分数 \(a\) 且 \(x > 0\) 对于 \(a < 0\)
正弦: \(y = \sin(x)\)
余弦: \(y = \cos(x)\)
正切函数: \(y = \tan(x)\)
函数约束可以直接使用我们的空间分支定界法处理，或者在将相应的约束替换为（静态）分段线性近似后作为MIP求解。这可以通过参数FuncNonlinear全局控制，或者通过属性FuncNonlinear为每个约束单独控制。如果选择了静态分段线性近似，可以使用各种属性和参数来控制其精度。章节解决方案策略讨论了这些选择。在动态分段线性逼近中，我们概述了空间分支定界法，在静态分段线性近似中，我们概述了静态分段线性近似。
非线性约束#
我们称非线性约束为形式为\(y = f(x)\)的关系，其中 \(x\)是一个包含\(n\)个Gurobi变量的向量，\(y\)是一个单独的 Gurobi变量，而\(f\)是一个函数\(f: \mathbf{R}^n \rightarrow \mathbf{R}\)。函数\(f\)可以由 算术运算（加法、减法、乘法）和各种单变量非线性函数组成。函数\(f\)基本上 可以使用与上述函数约束相同的非线性单变量函数，但它们的不同之处在于这些函数可以组合在一起， 并与算术运算一起用于表示复合多变量函数。
在内部，函数 \(f\) 由一个表达式树表示。 这样的树编码了函数 \(f\) 是如何由各种基本操作组成的。 树的叶子节点要么是 Gurobi 变量，要么是常量， 内部节点是对每个节点的子节点应用的操作。
在我们的Python API中，您可以使用算术运算符和非线性函数助手自然地编写非线性函数。您可以参考NLExpr的文档以获取详细信息。在其他API中，您必须构建表示函数\(f\)的表达式树。这被认为是高级用法。您可以参考表达式树部分以了解如何构建这些树。
在下面的表格非线性约束中的操作中，我们给出了可以在非线性约束中使用的各种操作的简明列表。我们通过相应的数学函数来描述每个操作。函数的参数由\(u\)和\(v\)表示。它们可能是Gurobi变量，但也可能是常量或表达式的另一部分。表格的最后一列给出了表达式树中相应的操作代码。建议读者参考这些操作代码以了解每个操作的详细信息。
操作名称 |
公式 |
操作码 |
|---|---|---|
加法 |
\(\sum_{i=1}^n v_i\) |
|
减法 |
\(u - v\) |
|
否定 |
\(-v\) |
|
乘法 |
\(v_1 \times v_2 \times \ldots \times v_n\) |
|
除法 |
\(\frac{u}{v}\) |
|
正方形 |
\(v^2\) |
|
平方根 |
\(\sqrt v\) |
|
自然指数 |
\(\exp(v)\) 或 \(e^v\) |
|
自然对数 |
\(\log_e(v)\) 或 \(\ln(v)\) |
|
二进制对数 |
\(\log_2(v)\) |
|
十进制对数 |
\(\log_{10}(v)\) |
|
功率 |
\(u^v\) |
|
正弦 |
\(\sin(v)\) |
|
余弦 |
\(\cos(v)\) |
|
切线 |
\(\tan(v)\) |
|
逻辑回归 |
\(\frac{1}{1 + \exp(-v)}\) |