混合整数线性规划算法- MATLAB和Simulink金宝app - 金宝app,下载188bet金宝搏,金宝搏官方网站

混合整数线性规划算法

混合整数线性规划定义

混合整数线性规划(MILP)是一个问题

线性目标函数，f^Tx,在那里f是常量的列向量，和x是未知数的列向量吗
边界和线性约束，但没有非线性约束(有关定义，请参阅写约束）
对某些成分的限制x要有整数值

用数学术语来说，就是给定的向量f，磅,乌兰巴托,矩阵一个而且Aeq，对应向量b而且说真的，和一组指标intcon，求一个向量x来解决

$\underset{x}{最小值} f^{T} x 受｛ \begin{array}{l} x （ intcon ）都是整数 \\ 一个 \cdot x \leq b \\ 一个 e 问 \cdot x ＝ b e 问 \\ l b \leq x \leq u b ． \end{array}$

算法概述

intlinprog利用这一基本策略求解混合整数线性规划。intlinprog可以在任何阶段解决问题。如果它在一个阶段解决了问题，intlinprog不执行后面的阶段。

减少问题的大小线性规划预处理．
用于解决初始松弛(非整数)问题线性规划．
执行混合整数程序预处理收紧混合整数问题的LP松弛。
试一试减少代进一步收紧混合整数问题的LP松弛。
尝试找出整数可行的解金宝搏官方网站启发式．
使用一个分支与界限系统搜索最优解的算法。该算法在整数变量的取值范围有限的情况下求解LP松弛问题。它试图在最优目标函数值上生成一系列更新的边界。

线性规划预处理

根据混合整数线性规划定义，有矩阵一个而且Aeq和相应的向量b而且说真的它编码了一系列线性不等式和线性等式

$\begin{matrix} 一个 \cdot x \leq b \\ 一个 e 问 \cdot x ＝ b e 问． \end{matrix}$

这些线性约束限制了解x．

通常，可以减少问题中变量的数量(的组成部分的数量)x)，并减少线性约束的数量。虽然执行这些简化操作会占用求解器时间，但它们通常会降低求解的总体时间，并可以使更大的问题得到解决。该算法能使解的数值稳定性提高。此外，这些算法有时可以检测到一个不可行的问题。

预处理步骤的目的是消除冗余的变量和约束，提高模型的可缩放性和约束矩阵的稀疏性，强化变量的边界，检测模型的原始和对偶不可行性。

详情请参见安徒生[２]Mészáros和Suhl[7]．

线性规划

最初的放松问题是具有相同目标和约束条件的线性规划问题混合整数线性规划定义，但没有整数约束。调用x_LP放松问题的解决方案x原整数约束问题的解。很明显,

f^Tx_LP≤f^Tx，

因为x_LP最小化相同的函数，但限制更少。

根节点初始放松LP (LP)和所有生成的LP的松弛和算法解决了使用线性规划解决方案技术。

混合整数程序预处理

在混合整数程序预处理过程中，intlinprog分析线性不等式A*x≤b以及完整性限制，以确定是否:

这个问题是不可行的。
有些界限可以收紧。
有些不平等是多余的，因此可以忽略或删除。
一些不平等现象可以加强。
有些整数变量是可以固定的。

的IntegerPreprocess选项让你选择是否intlinprog采取几个步骤，采取所有步骤，或几乎不采取任何步骤。如果你包含x0参数,intlinprog在预处理中使用该值。

混合整数程序预处理的主要目的是简化后续的分支定界计算。预处理包括快速预检查和消除一些无用的子问题候选项，而分支定界法本来会分析这些子问题。

关于整数预处理的详细信息，请参见Savelsbergh[9]．

减少代

切是附加的线性不等式约束intlinprog问题就更严重了。这些不等式试图限制LP松弛的可行区域，使其解更接近整数。金宝搏官方网站你可以控制切的方式intlinprog与the连用CutGeneration选择。

“基本”削减包括:

混合整数舍入切割
Gomory削减
集团削减
包括削减
流盖切割

此外，如果问题是纯整数(所有变量都是整数值)，那么intlinprog还使用以下切割:

强烈的Chvatal-Gomory切割
Zero-half削减

“中间”削减包括所有“基本”削减,加上:

简单的提升和工程削减
简单的旋转和减少切割
Reduce-and-split削减

“高级”削减包括所有“中间”删减和分割删减除外，加上:

强烈的Chvatal-Gomory切割
Zero-half削减

对于纯整数问题，“中间”使用最多的切割类型，因为它使用减少和分割切割，而“高级”没有。

另一个选择,CutMaxIterations，表示查询次数的上限intlinprog迭代以生成剪切。

关于切割生成算法(也称为切割平面方法)的详细信息，请参见Cornuéjols［5］以及，对于小团体的削减，Atamtürk, Nemhauser和Savelsbergh[3]．

寻找可行解的启发式金宝搏官方网站

为了得到目标函数的上界，分支定界法必须找到可行点。分支定界时LP弛豫的解可以是整数可行的，这可以为原MILP提供一个改进的上界。某些技术在分支定界之前或期间能更快地找到可行点。intlinprog在根节点和一些分支和定界迭代期间使用这些技术。这些技术是启发式的，这意味着它们是可以成功但也可以失败的算法。

设置intlinprog启发式使用“启发式”选择。选项是:

选项	描述
`“基本”`(默认)	求解器用不同的参数运行两次舍入启发式，用不同的参数运行两次潜水启发式，然后运行`“rss”`．当早期的启发式得到一个足够好的整数可行解时，求解器不会运行后来的启发式。
`“中间”`	求解器在不同的参数下运行两次舍入启发式，然后在不同的参数下运行两次潜水启发式。如果有一个整数可行的解，求解器就会运行`“rin”`紧随其后的是`“rss”`．如果`“rss”`找到一个新的解，解算器运行`“rin”`一次。当早期的启发式得到一个足够好的整数可行解时，求解器不会运行后来的启发式。
`“高级”`	求解器在不同的参数下运行两次舍入启发式，然后在不同的参数下运行两次潜水启发式。如果有一个整数可行的解，求解器就会运行`“rin”`紧随其后的是`“rss”`．如果`“rss”`找到一个新的解，解算器运行`“rin”`一次。当早期的启发式得到一个足够好的整数可行解时，求解器不会运行后来的启发式。
`“rin”`或者是同等的`“rins-diving”`	`intlinprog`搜索当前最佳整数可行解点(如果可用)的邻域，以找到一个新的更好的解。看看丹娜、罗斯伯格和勒·佩普[6]．当您选择`“rin”`，求解器在不同的参数下运行两次舍入启发式，在不同的参数下运行两次潜水启发式，然后运行`“rin”`．
`“rss”`或者是同等的`“rss-diving”`	`intlinprog`应用混合程序，结合了来自`“rin”`以及局部分支来寻找整数可行解。金宝搏官方网站当您选择`“rss”`，求解器在不同的参数下运行两次舍入启发式，在不同的参数下运行两次潜水启发式，然后运行`“rss”`．当早期的启发式得到一个足够好的整数可行解时，求解器不会运行后来的启发式。这些设置执行相同的启发式`“基本”`．
`“圆”`	`intlinprog`将LP解用于节点上的松弛问题，并以一种试图保持可行性的方式舍入整数分量。当您选择`“圆”`，求解器在根节点运行两次不同参数的舍入启发式，然后运行两次不同参数的潜水启发式。之后，求解器只在一些分支和定界节点上进行舍入启发式运算。
`“round-diving”`	求解器的工作方式类似于`“圆”`，但也在一些分支和定界节点上运行潜水启发式(除了舍入启发式)，而不仅仅是根节点。
`“潜水”`	`intlinprog`使用类似于分支和定界步骤的启发式方法，但只遵循树的一个分支，而不创建其他分支。这一单一的分支导致快速“俯冲”到树碎片，因此得名“潜水”。目前,`intlinprog`按以下顺序使用六种潜水启发式: 矢量长度潜水系数潜水部分潜水伪成本跳水直线搜索潜水引导潜水(适用于求解器已经找到至少一个整数可行点的情况) 潜水启发式通常选择一个应该是整数值的变量，其当前解为分数。然后，启发式引入一个约束，强制变量为整数值，并再次求解相关的松弛LP。选择变量绑定的方法是潜水启发式的主要区别。贝特看到[4]，第3.1节。
`“没有”`	`intlinprog`不寻找可行点。求解器简单地取它在分支定界搜索中遇到的任何可行点。

两者的主要区别“中间”而且“高级”是,“高级”在分支和定界迭代期间更频繁地运行启发式。

在每个启发式都得到一个可行解后，intlinprog调用输出函数和绘图函数。看到intlinprog输出函数和Plot函数语法．

如果你包含x0参数,intlinprog中使用该值“rin”引导潜水启发式直到找到一个更好的整数可行点。所以当你提供x0，您可以通过设置“启发式”选项“rins-diving”或者另一种使用“rin”．

分支与界限

分支定界方法构造一系列子问题，试图收敛到MILP的解。子问题给出了解的上界和下界序列f^Tx．第一个上界是任何可行解，第一个下界是松弛问题的解。有关上界的讨论，请参见寻找可行解的启发式金宝搏官方网站．

详见线性规划，线性规划松弛问题的任何解的目标函数值都比MILP的解的目标函数值低。还有，任何可行点x_{有限元分析}满足

f^Tx_{有限元分析}≥f^Tx，

因为f^Tx是所有可行点中的最小值。

在这种情况下，a节点是一个具有与原问题相同的目标函数、边界和线性约束的LP，但没有整数约束，并且对线性约束或边界有特定的变化。的根节点为原始问题，无整数约束，线性约束或边界不变，即根节点为初始松弛LP。

从起始边界开始，分支定界方法通过从根节点分支构造新的子问题。根据以下规则之一，采用启发式的方式进行分支步骤。每个规则都基于将一个变量限制为小于或等于整数J或大于或等于J+1来拆分问题的想法。这两个子问题出现时，进入x_LP，对应于intcon中指定的整数，它不是整数。在这里,x_LP是一个轻松问题的解决方案。取J为变量的下限(向下舍入)，J+1为上限(向上舍入)。由此产生的两个问题的解大于或等于金宝搏官方网站f^Tx_LP，因为他们有更多的限制。因此，这个过程可能会提高下限。

分支定界方法的性能取决于选择分裂哪个变量的规则(分支规则)。算法使用这些规则，您可以在BranchRule选择:

“maxpscost”-选择最大的分数变量pseudocost．
Pseudocost

变量的伪代价我是根据经验估计的下界何时发生变化我作为分支变量，结合我当前点的分量x．分数部分p分为上下两部分:

p_我^{- - - - - -}＝x（我) -⌊x（我)⌋
p_我⁺= 1 -p_我^{- - - - - -}．

让x_我^{- - - - - -}是线性规划的解的限制有x（我)≤⌊x（我)⌋，表示目标函数的变化

Δ_我^{- - - - - -}＝f^Tx_我^{- - - - - -}- - - - - -f^Tx．

同样的,Δ_我⁺问题限制时目标函数的变化有吗x（我)≥⌈x（我)⌉．

单位变量变化的目标增益x_我是

$d_{我}^{-} ＝ \frac{Δ_{我}^{-}}{p_{我}^{-}} 或 d_{我}^{+} ＝ \frac{Δ_{我}^{+}}{p_{我}^{+}} ．$

让年代_我^{- - - - - -}而且年代_我⁺的经验平均数d_我^{- - - - - -}而且d_我⁺在分支定界算法中。将经验值初始化为客观系数的绝对值f（我)在有任何观察之前。然后“maxpscost”规则是在节点上进行分支我对于一些正的权值，这是最大化的w⁺而且w^{- - - - - -}，数量

w^{- - - - - -}＊p_我^{- - - - - -}＊年代_我^{- - - - - -}+w⁺＊p_我⁺＊年代_我⁺．

粗略地说，这个规则选择了一个最可能增加下界的系数。
“strongpscost”-类似于“maxpscost”，而不是初始化为1对于每个变量，求解器只在伪代价有一个更可靠的估计之后才尝试在一个变量上分支。为了获得更可靠的估计，求解器执行以下操作(参见Achterberg、Koch和Martin)[1])．
- 根据当前基于伪成本的分数对所有潜在分支变量(那些当前为小数但应该为整数的变量)排序。
- 基于当前分支变量，从得分最高的变量(如果变量还没有用于分支计算)开始运行两个放松的线性程序。求解器使用这两个解来更新当前分支变量的伪代价。金宝搏官方网站求解器可以提前停止这个过程，以节省选择分支的时间。
- 继续选择列表中的变量，直到当前基于伪成本的最高分数不变k连续变量，其中k是内部选择的值，通常在5到10之间。
- 对基于伪成本的分数最高的变量进行分支。在早期的伪成本估计过程中，求解器可能已经基于该变量计算了松弛线性程序。
由于额外的线性规划解，每次迭代金宝搏官方网站“strongpscost”分支的时间比默认值要长“maxpscost”．然而，分支和定界迭代的数量通常会减少，因此“strongpscost”方法总体上可以节省时间。
“可靠性”-类似于“strongpscost”，但不是只对未初始化的伪代价分支运行宽松的线性程序，“可靠性”运行到的程序k2乘以每个变量，其中k2是一个小整数，例如4或8。因此,“可靠性”有更慢的分支，但可能更少的分支和定界迭代，相比“strongpscost”．
“mostfractional”-选择分数部分最接近的变量1／2．
“maxfun”-选择目标向量中对应绝对值最大的变量f．

在算法分支之后，有两个新的节点需要探索。算法使用以下规则之一在所有可用节点中选择要探索的节点:

“minobj”—选择目标函数值最小的节点。
“mininfeas”—选择整数不可行性和最小的节点。这意味着对于每一个整数不可行分量x（我)，将其中较小的相加p_我^{- - - - - -}而且p_我⁺,在那里

p_我^{- - - - - -}＝x（我) -⌊x（我)⌋
p_我⁺= 1 -p_我^{- - - - - -}．
“simplebestproj”—选择节点最佳投影．
最佳投影

让x_B表示目前为止找到的最佳整数可行点，x_R在根节点处降级LP松弛解，和x表示我们检查的节点。让在（x)表示该节点上的整数不可行性之和x(见“mininfeas”)．最佳投影规则是最小化

$f^{T} x + \frac{f^{T} x_{B} - f^{T} x_{R}}{我 n （ x_{R} ）} 我 n （ x ）．$

如果到目前为止还没有找到整数可行点，则设f^Tx_B= 0．

intlinprog通过考虑来自原始问题的信息，如目标函数的最大公约数(GCD)，跳过了对一些子问题的分析。

分支定界过程继续进行，系统地生成子问题进行分析，并丢弃那些不能改善目标上界或下界的子问题，直到满足以下停止条件之一:

算法超过MaxTime选择。
目标函数上下限的差值小于AbsoluteGapTolerance或RelativeGapTolerance公差。
被探测的节点数超过MaxNodes选择。
整数可行点的个数超过MaxFeasiblePoints选择。

关于分支定界过程的详细信息，请参见Nemhauser和Wolsey[8]和沃尔西[10]．

参考文献

[1]阿克特伯格，T.科赫和A.马丁。重新审视分支规则。运筹学通讯33,2005,pp. 42-54。可以在https://www-m9.ma.tum.de/downloads/felix-klein/20B/AchterbergKochMartin-BranchingRulesRevisited.pdf．

[2]安徒生和安徒生。线性规划中的解。数学规划71，页221-245,1995。

[3] Atamtürk, G. L. Nemhauser, M. W. P. Savelsbergh。求解整数规划问题中的冲突图。《欧洲运筹学杂志》，2000,pp. 40-55。

[4]伯特霍尔德，T。混合整数程序的原始启发式。Technischen Universität柏林，2006年9月。可以在https://www.zib.de/groetschel/students/Diplom-Berthold.pdf．

[5] Cornuéjols;混合整数线性规划的有效不等式。数学规划B, Vol. 112, pp. 3-44, 2008。

[6]丹娜，E.罗斯伯格，E.勒·教皇，C。探索弛豫诱导邻域以改进MIP解决方案。金宝搏官方网站数学规划，Vol. 102，第1期，pp. 71-90, 2005。

[7] Mészáros C.，和Suhl, U. H。线性规划和二次规划的高级预处理技术。《光谱》，25(4)，第575-595页，2003。

[8] Nemhauser, g.l.和Wolsey, l.a。整数与组合优化。Wiley-Interscience，纽约，1999年。

萨维尔斯伯格m.w.p。混合整数规划问题的预处理与探测技术。计算，Vol. 6, No. 4, pp. 445-454, 1994。

[10]洛杉矶沃尔西整数规划。Wiley-Interscience，纽约，1998年。