混合整数线性规划算法- MATLAB和Simulink - MathWorks印度金宝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可以在任何阶段解决问题。如果它在一个阶段解决了问题，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[8]．

线性规划

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

f^Tx_LP≤f^Tx，

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

这个初始松弛的LP(根节点LP)和分支定界算法中所有产生的LP松弛都是使用线性规划求解技术求解的。

混合整数程序预处理

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

这个问题是不可行的。
有些界限可以收紧。
有些不等式是多余的，所以可以忽略或删除。
一些不平等可以被加强。
一些整型变量是可以固定的。

的IntegerPreprocess选项让您选择是否intlinprog走几步，走全部，或者几乎不走一步。如果你包括x0参数,intlinprog在预处理中使用该值。

混合整数程序预处理的主要目的是简化后续的分支定界计算。预处理包括快速预检查和消除一些无用的子问题候选，否则将由分支和边界法进行分析。

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

减少代

切分是附加的线性不等式约束intlinprog这更加剧了问题。这些不等式试图限制LP松弛的可行区域，使其解更接近整数。金宝搏官方网站你可以控制切割的类型intlinprog与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改进启发式是“rin”，“rss”、1-opt、2-opt和引导潜水。

设置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`按以下顺序使用6个潜水启发式: 矢量长度潜水系数潜水部分潜水伪成本跳水直线搜索潜水引导潜水(当求解器已经找到至少一个整数可行点时应用) 潜水启发式通常选择一个应该是整值的变量，其当前解是分数。然后，启发式引入一个约束，强制变量为整值，并再次求解相关的松弛LP。选择变量的方法是潜水启发式的主要区别。贝特看到[4]，第3.1节。
`“没有”`	`intlinprog`不去寻找一个可行点。求解器简单地取它在分支定界搜索中遇到的任何可行点。

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

除了前面的表，下面的启发式运行时启发式选择是“基本”，“中间”,或“高级”．

ZI轮——每当一个算法求解一个宽松的LP时，这个启发式就会运行。启发式方法遍历每个分数型整数变量，试图在不影响其他约束条件的情况下将其转换为邻近的整数。详情请参见亨德尔[7]．
1-opt -每当算法找到一个新的整数可行解时，这个启发式就会运行。启发式方法遍历每个整数变量，试图在不影响其他约束的可行性的情况下将其移动到邻近的整数，同时降低目标函数值。
2-opt -每当算法找到一个新的整数可行解时，这个启发式就会运行。2-opt查找影响相同约束的所有整数变量对，这意味着它们在的同一行中有非零项一个或Aeq约束矩阵。对于每一对，2-opt取一个整数可行解，并使用所有四种可能的移动(向上、向上、向下、向下和向下)向上或向下移动变量对的值，寻找具有更好目标函数值的可行相邻解。该算法通过计算满足约束条件的整数变量对中每个变量的最大移位量(相同幅度)来测试每个整数变量对，并改进目标函数值。

在启发式阶段的开始，intlinprog运行微不足道的启发式,除非启发式是“没有”或者你提供一个初始整数可行点x0论点。琐碎启发式检查以下几点的可行性:

所有的零
上界
下界(如果非零)
“锁”点

“锁定”点仅用于所有变量的上界和下界都有限的问题。每个变量的“锁定”点是其上界或下界，如下所示。对于每个变量j，计算线性约束矩阵中对应的正项个数(:, j)然后减去相应的负元素数。如果结果为正，则使用该变量的下界，磅(j)．否则，使用该变量的上界，乌兰巴托(j)．“锁定”点试图满足每个变量最大数量的线性不等式约束，但不一定可行。

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

如果你包括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[9]和沃尔西[11]．

参考文献

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

[2]安徒生E. D.和安徒生K. D.线性规划中的预解。《数学规划》71,pp. 221-245, 1995。

[3] Atamtürk, A.， 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, G。混合整数线性规划的有效不等式。数学规划B卷，第3-44页，2008。

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

亨德尔，G。混合整数规划的新舍入和传播启发式。学士学位论文Universität柏林，2011年。PDF可于https://opus4.kobv.de/opus4-zib/files/1332/bachelor_thesis_main.pdf．

[8] Mészáros C.和Suhl, U. H.;线性和二次规划的先进预处理技术。光谱学，25(4)，pp. 575-595, 2003。

[9] Nemhauser, G. L.和Wolsey, L. A。整数与组合优化。Wiley-Interscience，纽约，1999年。

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

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