manbet体育手机客户端

目标

每一个优化模型的目标函数,这是决策变量的函数,你想最小化或最大化。目的是为了捕捉你的目标在解决这个问题。给定一组可行的解决方案,客观讲述了解决者优先。手机万博登录

大多数优化问题有多个最优解,再加上许多解决方案的目标是在一个小的最优值的差距。Gurobi返回的解决方案取决于你要解决的问题的类型。简单的规则是,Gurobi返回一个单一的连续模型的最优解(LP, QP, QCP),和一个序列离散模型的改进解决方案(MIP、MIQP MIQCP)。

Gurobi算法致力于解决一个模型,直到他们找到一个最佳的解决方案,在指定的公差。单纯形算法(包括与交叉屏障),有关宽容的OptimalityTol。屏障的算法(没有交叉),相关的公差是BarConvTol或BarQCPConvTol(根据问题类型)。你可以放松这些公差,但是请注意,这是罕见的显著改善解决方案。单纯形和障碍都返回一个最优解的算法。

离散模型,而你可以问MIP解算器找到最好的客观价值的解决方案,它停止时更常见解决方案的目标是在手机万博登录指定最优值的差距。最优控制的差距MIPGap参数,默认值为0.01%。

MIP解算器通常手机万博登录在路上发现多个最优解,最终找到最优的解决方案。这些中间解决方案可以查询优化完成后(使用Xn属性)。您可以使用溶液池特性采取更系统化的方法找到多种解决方案。这个特性允许您显示多少你想解决方案,指定最优值的最大差距你愿意接受,等等。

我们应该添加,可以指定一个单纯的可行性问题,唯一的目标是找到一个解决方案,满足约束条件。你能想到的一个可行性的问题作为一个恒定的目标函数优化问题。

可用的目标类型线性,分段线性,二次(凸和非凸),多目标。虽然有多个目标的属性似乎是正交的类型目标,Gurobi只支持多目标模型,所有目标都是线性的。

线性目标

最简单和最常见的目标函数是线性的,最小化或最大化决策变量的线性函数(例如,)。线性目标可以指定在几个方面。第一个是通过提供一个客观的术语,当决策变量添加到模型(通常通过addVar方法)。第二个是通过设置Obj属性变量。第三个也是最方便的方法,在面向对象的接口,是通过setObjective方法(在c++,Java,net,或Python)。该方法接受一个线性表达式对象作为其参数。

模型与一个线性目标,只有线性约束,只有连续变量是一个线性规划(LP)。它可以解决使用单纯形算法或障碍。

分段线性目标

一个线性目标是一个有用的变体分段单个变量的线性目标,目标是在一组线性片段。例如,假设我们想定义客观价值为变量如下:

函数的顶点出现在点,和,所以我们定义,和,其他客观值相邻点之间的线性插值。第一对最后一双分定义一个雷,所以外指定的值从这些点值外推。因此,在我们的例子中,和。

更正式,分段线性函数被定义为一组点:

这些定义以下分段线性函数:

我们也允许特殊情况下,如跳跃和单点,这是相当有用的定义固定费用或处罚。一个跳意味着左边和右边不相交,即我们有与和。对于左块,即。,点之间的线段和定义了为正确的部分,即。,点之间的线段和定义了。因为我们必须允许一些公差数值计算,这意味着,可以采取的价值或。一个单点意味着两个左右延伸到,但都有不同值比。它可以被描述为5分与和和。请注意,和可以等于或不同。因为宽容,这意味着,的价值吗,或。下面是一个例子一个跳跃和单点。

上面的分段函数变量是由7分 和。它有一个跳跃从来和一个单点。注意,左和右点都是一样的协调和在这个例子中两个点都是相同的。

注意,一个分段线性目标可以改变一个模型的类型。具体地说,包括一个非凸分段线性目标函数的连续模型变换成MIP模型。这可以显著增加的成本解决模型。

你确定分段线性凸是客观的?凸函数的属性,你不能获得一个更好的客观价值通过两点间插值函数。在下图中,您会注意到,所有的凸组合点的分段线性函数在阴影区域。

表示的另一种方法,连续的块会引入斜坡在凸分段线性目标(假设你是最小化)。

相反,在一个非凸分段线性函数插值点之间你可以得到一个更好的价值。在下面的图中,的价值分段线性函数插值得到的比的值。

分段线性目标上定义的变量(在使用一种特殊的方法C,c++,Java,net,或Python)。每个变量都可以有其自己的分段线性目标函数,每个函数需要一个单独的调用这个方法。

一个变量不能有线性和分段线性目标词。设置一个变量的分段线性目标设置Obj属性在该变量为0。同样,设置Obj属性将删除的分段线性目标变量。

我们应该指出,它是相当容易指定一个分段线性函数变量使用一些额外的变量和简单线性目标的条件。使用分段线性API方法的优点是双重的。首先是方便——指定函数直接导致更简单和更可读的代码。第二,Gurobi包括一个分段线性单纯形算法。如果你提供了一个模型,该模型只包含线性约束,只有连续变量,只有线性或凸分段线性的客观条件,那么这个专业单纯形算法将用于解决模型。如果你的分段线性函数包含大量的段,专业比标准单纯形算法的速度也会更快解决。手机万博登录

二次目标

你的优化目标也可以包含二次术语(例如,)。您指定的二次目标的面向对象的接口通过建立二次表达式,然后调用setObjective(c++,Java,net,或Python)。在C语言中,你输入你的二次使用GRBaddqpterms。

有四种不同的算法,可以用来解决模型与二次目标。适当的一个取决于几个特定属性的客观和其余的模型。

• 连续QP如果你的二次目标是凸和模型只包含线性约束和连续变量,那么你的模型是一个二次规划(QP)和可以解决使用单纯形算法或障碍。QP单工将返回一个最优的基本解决方案。Gurobi没有QP交叉,所以QP屏障将返回一个内部解决方案。
• 离散QP凸松弛如果你的二次目标是凸,但模型包含离散元素(整数变量,SOS约束,一般限制,等等),那么你的模型是一个混合整数二次规划(MIQP)和解决使用MIP的能手。手机万博登录MIP在很大程度上依赖于单纯形基地以来,根放松必须解决使用原始或对偶单纯形算法。
• 离散QP非凸松弛如果你的目标并不是凸二次,然后使用MIP模型将解决解决,即使你的模型没有明确的离散元素。手机万博登录然而,在这个版本你需要采取行动发生。具体地说,您需要设置非凸参数2。使用默认设置,导致非凸二次目标GRB_ERROR_Q_NOT_PSD错误。

检查这些属性在presolved模型。总是这样,presolve将试图简化模型。在这种情况下,它将试图将一个非凸MIQP成一个等效凸MIQP。这种简化会成功如果每个二次项包含至少一个二进制变量。

你怎么能确定你的二次目标凸吗?正如前面提到的,凸性的关键属性是插值任意两点之间在功能上不让你下面的函数(假设最小化)。在这个图中,所有点抛物线上的任何两个点之间的线段总是在阴影区域。

这转化为多个变量如何?二次函数是凸,相关的Q矩阵必须是半正定(PSD)。

多个目标

您还可以指定多个模型(线性)的目标,和Gurobi提供了工具,允许您探索它们之间的权衡。指的是多个目标部分额外的细节。