目标
目标
每个优化模型都有一个目标函数,它是关于你希望最小化或最大化的决策变量的函数。目标是为了抓住你解决问题的目标。给定一组可行的解决方案,目标告诉求解器哪个是首选。手机万博登录
大多数优化问题都有多个最优解,加上多个解的目标与最优值之间的距离很小。Gurobi返回的解决方案取决于您要解决的问题的类型。简单的规则是,Gurobi返回连续模型(LP、QP和QCP)的单个最优解,以及离散模型(MIP、MIQP和MIQCP)的一系列改进解。
Gurobi算法的工作是解决一个模型,直到他们找到一个解决方案是最优的,在指定的公差。对于单纯形算法(包括带交叉的barrier),相应的容差为OptimalityTol.对于barrier算法(无交叉),相应的容差为BarConvTol或BarQCPConvTol(取决于问题类型)。您可以放宽这些容忍度,但请注意,这样做很少会显著提高解决方案时间。单纯形算法和障碍算法都只返回一个最优解。
对于离散模型,虽然您可以要求MIP求解器找到一个可能的最佳目标值的解决方案,但更常见的是,当解手机万博登录决方案目标与最优值之间的指定差距时停止。此最优间隙由MIPGap参数,默认值为0.01%。
MIP求解器通常手机万博登录会在最终找到最优解的过程中找到多个次优解。一旦优化完成,就可以查询这些中间解(使用Xn属性)。你可以使用溶液池采用更系统的方法来寻找多个解决方案。这个功能允许您指出您想要多少解决方案,指定您愿意接受的最佳值之间的最大差距,等等。
我们应该补充的是,指定一个纯粹的可行性问题是可能的,其中的唯一目标是找到一个满足约束的解决方案。你可以把可行性问题想象成一个目标函数不变的优化问题。
可用的目标类型是线性,分段线性,二次(包括凸和非凸),以及多目标.虽然拥有多个目标的属性可能与目标的类型是正交的,但Gurobi只支持所有目标都是线性的多目标模型。
最简单和最常见的目标函数是线性函数——对决策变量(如:).线性目标可以通过几种方式指定。第一种方法是在将决策变量添加到模型时(通常通过addVar
方法)。第二个是通过设置Obj属性。第三种也是最方便的方法(在面向对象的接口中可用)是通过setObjective
方法(在c++,Java,net,或Python).这个方法接受一个线性表达式对象作为它的参数。
一个有线性目标、只有线性约束和只有连续变量的模型是一个线性规划(LP)。它可以用单纯形算法或障碍算法来解决。
线性目标的一个有用的变体是A分段-线性目标,其中单个变量的目标被捕获在一组线性片段中。例如,假设我们想要定义客观值为变量如下:
更正式地说,分段线性函数定义为点:
我们还允许特殊情况,如跳跃和单点,这对于定义固定收费或惩罚非常有用。一个跳意味着左边和右边不相交,即我们有与和.对于左边的部分,也就是。,点之间的线段和定义了,对于正确的部分,即。,点之间的线段和定义了.因为我们必须允许一些数值计算的公差,这意味着,可以取任意一个的值吗或.单点在意味着左右两边都延伸到,但两者都有不同值比.它可以用五点来描述与和和.请注意,和可以相等,也可以不同。因为宽容,就意味着at,可以取的值,或.下面是一个带有跳跃和单点的示例。
注意分段线性目标可以改变模型的类型。具体来说,在一个连续模型中包含一个非凸分段线性目标函数将把该模型转换为一个MIP。这将显著增加求解模型的成本。
如何确定分段线性目标是否是凸的?凸函数具有这样的特性:你不能通过插值函数上的两点来获得一个更好的目标值。在下面的图中,你会注意到分段线性函数上所有点的凸组合都在阴影区域内。
相反,在非凸分段线性函数中,通过插值点可以得到更好的值。在下面的图中,值对于分段线性函数比插值得到的值差。
分段线性目标是用一种特殊的方法在变量上定义的C,c++,Java,net,或Python).每个变量都可以有自己的分段线性目标函数,每个函数都需要单独调用这个方法。
一个变量不能同时具有线性和分段线性的目标项。为变量设置分段线性目标将设置Obj属性把这个变量设为0。同样,设置Obj
属性将删除该变量上的分段线性目标。
我们应该指出,使用一些额外的变量和简单的线性目标项来指定一个变量上的分段线性函数是相当容易的。使用分段线性API方法的优点有两个。第一个是方便——直接指定函数会导致代码更简单、可读性更强。第二,Gurobi包含了一个分段线性单纯形算法。如果您提供的模型仅包含线性约束,仅包含连续变量,且仅包含线性或凸分段线性目标项,那么将使用这种专门的单纯形算法来求解模型。如果分段线性函数包含大量的分段,专用算法将比标准的单纯形求解器快得多。手机万博登录
你的优化目标也可以包含二次项(例如,).通过构建二次表达式,然后调用,可以在面向对象的接口中指定二次目标setObjective(c++,Java,net,或Python).在C语言中,你输入二次项GRBaddqpterms.
有四种不同的算法可用于求解具有二次目标的模型。合适的方法取决于目标的一些特定属性和模型的其余部分。
- 连续QP如果你的二次目标是凸的,你的模型只包含线性约束和连续变量,那么你的模型是一个二次规划(QP),可以使用单纯形算法或障碍算法求解。QP单纯形将返回一个最优的基本解。古罗比没有一个QP交叉,所以QP障碍将返回一个内部解决方案。
- 具有凸松弛的离散QP如果你的二次目标是凸的,但模型包含离散元素(整数变量,SOS约束,一般约束等),那么你的模型是一个混合整数二次规划(MIQP),并使用MIP求解器求解。手机万博登录由于MIP很大程度上依赖于单纯形基,因此必须使用原始单纯形算法或对偶单纯形算法来求解根松弛。
- 具有非凸松弛的离散QP如果你的二次目标不是凸的,那么模型将使用MIP求解器来解决,即使你的模型没有显式的离散元素。手机万博登录然而,在这个版本中,你需要采取行动来实现这一点。具体来说,您需要设置非凸参数2。在默认设置下,非凸二次目标导致GRB_ERROR_Q_NOT_PSD错误。
在预解模型上检查这些属性。一如既往,presolve将尝试简化模型。在这种情况下,它将尝试将非凸MIQP转换为等效的凸MIQP。如果每个二次项至少包含一个二进制变量,这种简化总是成功的。
如何确定二次目标是否是凸的?正如前面提到的,凸性的关键属性是函数上任意两点之间的插值永远不会让你低于函数(假设函数最小化)。在这个图中,抛物线上任意两点之间的线段上的所有点总是在阴影区域内。
您还可以为您的模型指定多个(线性的)目标,Gurobi提供了工具,允许您探索它们之间的权衡。指的是多个目标部分的更多细节。