混合整数线性规划算法- 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不执行后期。

降低问题的规模线性规划预处理。
解决使用一个初始放松(noninteger)问题线性规划。
执行混合整数规划预处理收紧的LP放松整数问题。
试一试减少代进一步加强LP放松的整数的问题。
试图找到integer-feasible解决方案使用金宝搏官方网站启发式。
使用一个分支界限法算法来系统地搜索最优解。该算法解决了LP的松弛与可能的值的整数变量的限制范围。它试图生成一系列更新边界最优目标函数值。

线性规划预处理

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

$\begin{matrix} 一个 \cdot x \leq b \\ 一个 e 问 \cdot x = b e 问。 \end{matrix}$

这些线性约束限制的解决方案x。

通常,可以减少问题的变量(组件的数量x),减少线性约束。在执行这些削减可以花时间解决者,他们通常更低的整体解决方案,和可以解决大问题。数值算法可以使方案更加稳定。此外,这些算法有时会发现一个不可行的问题。

预处理步骤旨在消除冗余的变量和约束,提高模型的扩展和约束矩阵的稀疏,加强变量的取值范围,检测模型的原始和双不可行性。

,安德森,安德森[2]和Meszaros苏尔[8]。

线性规划

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

f^Tx_LP≤f^Tx,

因为x_LP减少相同的功能,但更少的限制。

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

混合整数规划预处理

在整数程序预处理,intlinprog分析了线性不等式* x≤b随着完整性约束来确定:

问题是不可行的。
一些边界可以收紧。
一些不平等是多余的,所以可以忽略或删除。
一些不平等可以加强。
一些整数变量可以固定。

的IntegerPreprocess选项允许您选择intlinprog需要几个步骤,需要所有人,或几乎没有。如果你有一个x0参数,intlinprog在预处理使用该值。

混合整数规划预处理的主要目的是简化随后的和计算。预处理包括快速preexamining并消除一些徒劳的子问题候选人和否则分析。

整数预处理的详细信息,请参阅Savelsbergh[10]。

减少代

削减额外的线性不等式约束intlinprog增加了问题。这些不平等试图限制LP的可行域的松弛,这样他们的解决方案更接近整数。金宝搏官方网站你控制削减的类型intlinprog使用与CutGeneration选择。

“基本”削减包括:

整数的削减
Gomory削减
集团削减
包括削减
流覆盖削减

此外,如果问题是纯粹的整数(所有变量都是整数值)intlinprog还使用以下削减:

强Chvatal-Gomory削减
Zero-half削减

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

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

“高级”削减包括所有“中间”除了削减reduce-and-split削减,加上:

强Chvatal-Gomory削减
Zero-half削减

对于纯整数问题,“中间”使用最切的类型,因为它使用reduce-and-split削减“高级”没有。

另一个选择,CutMaxIterations,指定一个上限的次数intlinprog迭代生成减少。

细节将代算法(也称为剖切面方法),看到Cornuejols[5]削减小团体,Atamturk Nemhauser, Savelsbergh[3]。

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

得到目标函数上界,和程序必须找到可行点。解决一个LP期间放松和可以整数可行,这可以提供一种改进的原始MILP上界。某些技术找到可行的分速度和之前或期间。intlinprog使用这些技术在根节点和一些和迭代。这些技术是启发式的,也就是说,它们的算法可以成功,但也会失败。

启发式可以开始启发式,帮助解决者找到最初的或新的integer-feasible解决方案。或启发式可以改进启发式integer-feasible点开始,试图找到一个更好的integer-feasible点,意味着一个较低的目标函数值。的intlinprog改进启发式“rin”,“rss”,2-opt 1-opt和指导潜水。

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

选项	描述
`“基本”`(默认)	与不同的参数解算器运行舍入启发式两次,分两次潜水启发式与不同的参数,然后运行`“rss”`。解算器不运行后启发式当早些时候启发式导致一个足够好的integer-feasible解决方案。
`“中间”`	用不同的参数解算器运行舍入启发式两次,然后用不同的参数运行两次潜水启发式。如果有一个integer-feasible解决方案,然后求解程序运行`“rin”`紧随其后的是`“rss”`。如果`“rss”`发现了一个新的解决方案,解决运行`“rin”`一次。解算器不运行后启发式当早些时候启发式导致一个足够好的integer-feasible解决方案。
`“高级”`	用不同的参数解算器运行舍入启发式两次,然后用不同的参数运行两次潜水启发式。如果有一个integer-feasible解决方案,然后求解程序运行`“rin”`紧随其后的是`“rss”`。如果`“rss”`发现了一个新的解决方案,解决运行`“rin”`一次。解算器不运行后启发式当早些时候启发式导致一个足够好的integer-feasible解决方案。
`“rin”`或同等`“rins-diving”`	`intlinprog`搜索当前的社区,最好integer-feasible解点(如果有的话)来找到一个新的和更好的解决方案。看到丹娜,Rothberg,勒佩普[6]。当您选择`“rin”`,解决运行舍入启发式两次不同的参数,运行两次潜水启发式与不同的参数,然后运行`“rin”`。
`“rss”`或同等`“rss-diving”`	`intlinprog`适用于混合过程结合的想法`“rin”`和当地分支搜索integer-feasible解决方案。金宝搏官方网站当您选择`“rss”`,解决运行舍入启发式两次不同的参数,运行两次潜水启发式与不同的参数,然后运行`“rss”`。解算器不运行后启发式当早些时候启发式导致一个足够好的integer-feasible解决方案。这些设置执行相同的启发式`“基本”`。
`“圆”`	`intlinprog`采用LP解决放松问题节点,和轮整数组件的方式试图维护的可行性。当您选择`“圆”`解算器,在根节点,舍入启发式两次不同的运行参数,然后用不同的参数运行两次潜水启发式。此后,解算器运行时只在一些四舍五入启发式和节点。
`“round-diving”`	解算器以类似的方式工作`“圆”`,而且运行潜水启发式(除了舍入启发式)和节点,不仅仅是根节点。
`“潜水”`	`intlinprog`使用启发式和步骤类似,但遵循树的一个分支,没有创建其他分支。这一分支导致快速“潜水”树片段,因此命名为“潜水。“目前,`intlinprog`使用六个潜水启发式在这个顺序: 向量长度潜水系数潜水部分潜水伪成本潜水线搜索潜水引导潜水(适用于解决已经发现至少有一个integer-feasible点) 潜水启发式通常选择一个变量应该是整数值,为当前的解决方案是分数。然后启发式介绍部队整数值的变量的绑定,并解决相关的放松LP。选择变量绑定的方法之间的主要区别是潜水启发式。贝特看到[4],3.1节。
`“没有”`	`intlinprog`不寻找一个可行点。解算器简单地将遇到的任何可行的点和搜索。

的主要区别“中间”和“高级”是,“高级”运行启发式和迭代期间更频繁。

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

子轮——这种启发式方法运行时LP算法解决了一个放松。启发式将遍历每个部分整数变量试图转移到相邻的整数而不影响可行性对其他约束。详情,请参阅Hendel[7]。
1-opt——这种启发式方法运行一算法发现一个新的integer-feasible解决方案。启发式穿过每一个整数变量试图转移到相邻的整数不影响可行性对其他约束,同时降低目标函数值。
2-opt——这种启发式方法运行一算法发现一个新的integer-feasible解决方案。2-opt发现所有成对的整数变量影响相同的约束,这意味着他们有非零项的同一行一个或Aeq约束矩阵。对于每一对,2-opt integer-feasible解决方案和变量的值对向上或向下移动使用所有四种可能的举措(down-up向上,上下,当当你),寻找一个可行的邻国解决方案,有一个更好的目标函数值。算法测试每一对整数变量通过计算最大大小相同(级)的每个变量的变化对满足约束条件和目标函数值也有所改善。

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

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

定义的“锁”的观点是只有有限的上界和下界的所有变量的问题。每个变量的“锁”点是它的上限或下限,选择如下。为每一个变量j,计算相应的积极的条目的数量线性约束矩阵(:,j)和数量减去相应的消极的条目。如果结果是正的,使用该变量的下限,磅(j)。否则,使用该变量的上界,乌兰巴托(j)。“锁”点试图满足线性不等式约束的最大数量为每个变量,但不一定是可行的。

每次启发式完成一个可行的解决方案后,intlinprog输出函数和情节函数调用。看到intlinprog输出函数和情节函数的语法。

如果你有一个x0参数,intlinprog使用价值的“rin”和指导潜水启发式,直到找到一个更好的integer-feasible点。所以当你提供x0通过设置,您可以获得良好的结果“启发式”选项“rins-diving”或另一个设置使用“rin”。

分支界限法

和方法构造一系列子问题,尝试的MILP收敛到一个解决方案。子问题给一个序列上、下界的解决方案f^Tx。第一个上界是任何可行的解决方案,第一个下界是放松的问题解决方案。上界的讨论,请参阅启发式寻找可行的解决方案金宝搏官方网站。

在解释线性规划,任何解决线性规划松弛问题的目标函数值低于MILP解决方案。同时,任何可行点x_{有限元分析}满足

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

因为f^Tx至少在所有可行点。

在这种背景下,节点LP相同的目标函数,边界,和线性约束作为最初的问题,但没有整数约束,和特定的线性约束条件或边界的变化。的根节点最初的问题是没有整数约束,没有改变线性约束或限制,意思是根节点初始放松LP。

从边界开始,和分支方法构造新子问题的根节点。分支一步是采取启发式的,根据几个规则之一。每个规则是基于分裂问题的想法通过限制一个变量小于或等于整数J,或大于或等于J + 1。这两个子问题时出现的一个条目x_LP,对应于一个整数中指定intcon,不是一个整数。在这里,x_LP是一种放松的问题的解决方案。以J为变量的地板(四舍五入),和J + 1的上限(围捕了)。由此产生的两个问题解决方案,是大于或等于金宝搏官方网站f^Tx_LP,因为他们有更多的限制。因此,这个过程可能提高下界。

和方法的性能取决于规则选择变量分裂(分支规则)。该算法使用这些规则,你可以设置的BranchRule选择:

“maxpscost”——选择最大的部分变量pseudocost。
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”的,而是pseudocost被初始化为1为每一个变量,变量的解算器试图分支只有在pseudocost更可靠的估计。获得更可靠的估计,解决以下(见Achterberg,科赫,马丁[1])。
- 订单所有潜在的分支变量(那些目前分数但应该是整数)的当前pseudocost-based分数。
- 运行两个放松的线性程序基于当前分支变量,从得分最高的变量(如果变量尚未用于分支计算)。解算器使用这两个解决方案来更新当前分支pseudoc金宝搏官方网站osts变量。解算器可以停止这个过程就节省时间在选择分支。
- 继续选择变量列表中,直到当前最高pseudocost-based分数不会改变k连续变量,k内部是一个选择的价值,通常5 - 10。
- 在变量pseudocost-based得分最高的分支。解算器可能已经放松的线性计算程序基于这个变量在早些时候pseudocost估计过程。
因为额外的线性规划解决方案,每一次迭代金宝搏官方网站“strongpscost”比默认分支需要更长的时间“maxpscost”。然而,通常和迭代的数量减少,因此“strongpscost”整体方法可以节省时间。
“可靠性”——类似于“strongpscost”,而是跑步放松线性程序只对未初始化pseudocost分支,“可靠性”运行程序k2*为每个变量,在那里k2是一个小整数,如4或8。因此,“可靠性”甚至慢分支,但潜在的减少和迭代,相比“strongpscost”。
“mostfractional”——选择小数部分最接近的变量1/2。
“maxfun”——选择相应的绝对值最大的变量在目标向量f。

算法分支后,有两个新的节点来探索。该算法选择哪个节点探索可用在所有使用这些规则之一:

“minobj”——选择最低的节点目标函数值。
“mininfeas”——选择节点的最小整数之和不可行性。这意味着每integer-infeasible组件x(我在节点,添加的小p_我^{- - - - - -}和p_我⁺,在那里

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

让x_B表示最好的integer-feasible点发现到目前为止,x_R降级LP轻松解决方案在根节点,和x表示节点我们检查。让在(x)表示整数的和不可行性的节点x(见“mininfeas”)。最好的投影规则是最小化

$f^{T} x + \frac{f^{T} x_{B} - f^{T} x_{R}}{我 n (x_{R})} 我 n (x) 。$

发现到目前为止,如果没有integer-feasible点集f^Tx_B= 0。

intlinprog跳过某些子问题的分析,考虑信息从原始目标函数等问题的最大公约数(GCD)。

和过程仍在继续,系统生成子问题来分析和丢弃那些不会改善目标的上限或下限,直到其中一个停止条件满足:

该算法超过MaxTime选择。
较低的区别和目标函数上界小于AbsoluteGapTolerance或RelativeGapTolerance公差。
探索节点的数量超过了MaxNodes选择。
的数量超过了整数可行点MaxFeasiblePoints选择。

和程序的详细信息,请参阅Nemhauser和沃尔西[9]和沃尔西[11]。

引用

[1]Achterberg, T。,T。Koch and A. Martin.分支规则重新审视。行动研究快报33岁,2005年,页42-54。可以在https://www-m9.ma.tum.de/downloads/felix-klein/20B/AchterbergKochMartin-BranchingRulesRevisited.pdf。

[2]安徒生,e D。,一个ndersen, K. D.Presolving线性规划。数学规划71年,第245 - 221页,1995年。

[3]Atamturk,。,G. L. Nemhauser, M. W. P. Savelsbergh.冲突图解决整数规划问题。121年欧洲运筹学杂志,2000,pp。40-55。

贝特[4],T。原始的启发式混合整数规划。Technischen柏林大学,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,第90 - 71页,2005年。

[7]Hendel G。新舍入和传播启发式混合整数规划。在柏林科技大学学士论文,2011年。PDF可以在https://opus4.kobv.de/opus4-zib/files/1332/bachelor_thesis_main.pdf。

[8]Meszaros C。,Suhl, U. H.线性和二次规划的先进的预处理技术。或频谱,25(4),575 - 595年,2003页。

[9]Nemhauser, g·l·沃尔西,l。整数和组合优化。Wiley-Interscience,纽约,1999年。

[10]Savelsbergh, m . w . P。预处理和探测技术的混合整数规划问题。ORSA j .计算,6卷,第4号,第454 - 445页,1994年。

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