混合整数线性规划算法- 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可以在任何阶段解决这个问题。如果它能在一个阶段内解决问题，intlinprog不执行后面的阶段。

减少问题大小使用线性程序预处理．
使用线性规划．
履行混合整数规划预处理收敛了混合整数问题的LP松弛。
尝试削减生成进一步加强了混合整数问题的LP松弛。
试着用金宝搏官方网站启发式．
使用一个分支和绑定系统搜索最优解的算法。该算法解决了整数变量可能取值范围有限的LP松弛问题。它试图生成一个更新的最优目标函数值的界限序列。

线性程序预处理

根据这一点混合整数线性规划定义，有矩阵一个和Aeq和相应的向量b和说真的编码一组线性不等式和线性等分

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

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

通常，可以减少问题中变量的数量(组件的数量)x)，并减少线性约束的数量。虽然执行这些缩减会占用求解器的时间，但它们通常会降低解决问题的总体时间，并使更大的问题变得可解决。该算法可以使解在数值上更稳定。此外，这些算法有时可以检测到不可行的问题。

预处理步骤旨在消除冗余变量和约束，提高约束矩阵的模型和稀疏性的缩放，加强变量的界限，并检测模型的原始和双重不可行性。

详情请参见Andersen和Andersen[２]Mészáros和苏尔［8］．

线性规划

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

f^Tx_LP.≤f^Tx，

因为x_LP.最小化相同的功能，但限制更少。

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

混合整数规划预处理

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

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

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

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

整数预处理请参见Savelsbergh［10］．

削减生成

切割是额外的线性不等式约束intlinprog增加了问题。这些不等式试图限制LP放松的可行区域，以便它们的解决方案更接近整数。金宝搏官方网站您控制剪切类型intlinprog用途CutGeneration选择。

“基本”削减包括:

混合整数圆形切割
戈梅里削减
Clique Cuts.
包括削减
流覆盖削减

此外，如果问题是纯整数(所有变量都是整数值)，则intlinprog也使用以下削减:

强Chvatal-Gomory削减
零半切

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

简单lift-and-project削减
简单pivot-and-reduce削减
Reduce-and-split削减

'先进的'削减包括所有“中间”除削减和分割削减外的削减，加上:

强Chvatal-Gomory削减
零半切

对于纯整数问题，“中间”使用最剪切类型，因为它使用缩小和分裂剪切，而'先进的'没有。

另外一个选项，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解用于松弛问题的一个节点，并以一种试图保持可行性的方式将整数分量舍入。当你选择`“圆”`，求解器在根节点上运行两次具有不同参数的舍入启发式，然后运行两次具有不同参数的潜水启发式。此后，求解器只在一些分支绑定节点上运行舍入启发式算法。
`'圆潜水'`	求解器的工作方式类似于`“圆”`，还在一些分支绑定节点上运行潜水启发式(除了舍入启发式)，而不仅仅是根节点。
`'潜水'`	`intlinprog`使用类似于分支绑定步骤的启发式方法，但只沿着树的一个分支向下，而不创建其他分支。这个分支导致快速“向下”树片段，因此命名为“潜水”。目前,`intlinprog`按以下顺序使用六个潜水启发式: 向量长度潜水系数潜水部分潜水伪成本潜水线路搜索潜水引导潜水(当求解器已经找到至少一个整数可行点时) 潜水启发式算法通常选择一个应该是整数值的变量，当前的解决方案是分数。然后启发式引入一个边界，强制变量为整数值，并再次求解相关的松弛LP。选择约束变量的方法是潜水启发式的主要区别。贝特看到［4］, 3.1节。
`'没有任何'`	`intlinprog`不搜索可行的点。求职者只是在其分支和绑定的搜索中遇到任何可行的点。

主要区别“中间”和'先进的'是,'先进的'在分支绑定迭代期间更频繁地运行启发式算法。

除上一个表外，在启发式选项是“基本”，“中间”,或'先进的'．

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

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

所有的零
上限
下限（如果非零）
“锁定”点

“锁定”点只对所有变量的上界和下界有限的问题定义。每个变量的“锁定”点是它的上界或下界，如下所示。为每一个变量j，计算线性约束矩阵中的相应正条目的数量A（：，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．
伪心

一个变量的伪成本我是根据经验估计的变化下限在什么时候我已被选择为分支变量，与我当前点的分量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］)．
- 通过其当前基于Pseudocost的分数命令所有潜在的分支变量（目前分数但是应该是整数的那些）。
- 基于当前分支变量运行两个松散的线性程序，从得分最高的变量开始(如果这个变量还没有被用于分支计算)。求解器使用这两个解来更新当前分支变量的伪代价。金宝搏官方网站求解器可以提前停止这个过程，以节省选择分支的时间。
- 继续在列表中选择变量，直到当前最高的基于伪成本的分数不变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]和Wolsey.［11］．

参考文献

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

[2]安德森，E. D.和Andersen，K。D.线性规划中的求解。数学编程71，PP。221-245,1995。

[3]Atamtürk，A.，G.L.L.Nemhauser，M. W.P.Velsbergh。整数规划问题中的冲突图。欧洲运筹学杂志，2000年，第40-55页。

贝特[4],T。混合整数程序的原始试探法。TechnischenUniversität柏林，2006年9月。提供https://www.zib.de/groetschel/students/Diplom-Berthold.pdf．

[5] Cornuejols G。混合整数线性规划的有效不等式。数学规划B，第112卷，第3-44页，2008。

[6]唐娜，E.，Rothberg，E.，Le Pape，C.探索放松诱导社区，改善MIP解决方案。金宝搏官方网站数学规划，第102卷，第1期，71-90页，2005。

[7] Hendel G。混合整数规划的新圆形和传播启发式。2011年Technische Universität Berlin学士论文。PDF可以在https://opus4.kobv.de/opus4-zib/files/1332/bachelor_thesis_main.pdf．

[8] Mészáros C。用于线性和二次编程的先进预处理技术。或光谱，25(4)，pp. 575-595, 2003。

G. L. Nemhauser和洛杉矶沃尔西整数与组合优化。Wiley-Interscience，纽约，1999。

萨维尔斯伯格(m.w.p.)混合整数规划问题的预处理和探测技术。ORSA J. Computing, Vol. 6, No. 4, pp. 445 - 454,1994。

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