@广东工业大学 English

梁颖宗

个人信息Personal Information

教授

硕士生导师

教师拼音名称：Liang Yingzong

入职时间：2018-12-27

所在单位：材料与能源学院

联系方式：yliang@gdut.edu.cn

在职信息：在职

主要任职：Professor

其他任职：Professor

毕业院校：The Hong Kong University of Technology

学科：工程热物理

同专业硕导

教师博客

当前位置： 中文主页 >> 教师博客

分支切平面法

点击次数：

介绍

分支和剪切方法是在 90 年代发现的，作为解决/优化混合整数线性规划的一种方法（Karamanov，Miroslav）[1]。这个概念由两种已知的优化方法组成——分支定界和切割平面。利用这两个工具，分支和剪切可以通过放宽问题以产生上限来找到最佳解决方案。放宽问题可以使复杂的问题简化，以便更容易解决。此外，上限表示目标可行时可以采取的最高值。当目标等于上限时找到最佳解决方案（Luedtke，Jim）[2]。这种方法对于优化的未来至关重要，因为它结合了两种常用工具，以便利用每个组件来找到最佳解决方案。展望未来，可以组合不同方法的关键组成部分，以便以更简单和直接的方式找到最优性。

方法与算法

方法

缩写详细信息
缩写词 扩张
LP 线性规划
民宿 分支定界

最不可行的分支：

最不可行分支是一种非常流行的方法，它选择小数部分最接近的变量{\displaystyle 0:5}， IE，{\displaystyle si=0:5-|xA_{i}-xA_{i}-0:5|}[3] . 大多数不可行的分支选择一个变量，其中可以识别变量应舍入到哪一侧的趋势最小。然而，该方法的性能并不比随机选择变量的规则优越。

强分支：

对于每个分数变量，强分支通过计算该变量分支的 LP 松弛结果来测试对偶界限增加。选择导致最大增量的变量作为当前节点的分支变量。尽管其明显简单，但就 B&B 树中可用节点的数量而言，强分支是迄今为止最强大的分支技术，但这种有效性只能以计算成本来实现。[4]

伪成本：

纯伪成本分支

近似松弛值的另一种方法是利用伪成本方法。变量的伪成本是对因变量值向上或向下舍入而导致的目标函数每单位变化的估计。对于每个变量，我们选择具有最大估计 LP 目标增益的变量[5]。  

算法

分支与剪切是分支与界限算法的变体。分支割法结合了戈梅利割法，允许给定问题的搜索空间。标准单纯形算法将用于解决每个整数线性规划问题（LP）。


{\displaystyle min:c^{t}x}

{\displaystyle stAx<b}

{\displaystyle x\geq 0}

{\displaystyle x_{i}=int,i=1,2,3...,n}

以上是一个混合整数线性规划问题。x 和 c 是 n 向量的一部分。这些变量可以设置为 0 或 1 允许二进制变量。上述问题可以表示为{\displaystyle LP_{n}}

以下是利用分支和切割算法以及 Gomery 切割和分区的算法：

步骤0：

上限 = ∞下限 = -∞

步骤1.初始化：

将第一个节点设置为{\displaystyle LP_{0}} 同时将活动节点设置为{\displaystyle L}。该集可以通过访问{\displaystyle LP_{n}}

步骤 2. 终止：

步骤 3. 迭代列表 L：

尽管{\displaystyle L}不为空（i是L列表的索引），则：

步骤 3.1。转换为松弛：

解决3.2。

解决轻松问题

步骤 3.3。

如果 Z 不可行：
   返回步骤 3。否则：
   继续解 Z。

步骤 4. 切割平面：

如果找到切割平面：
   则添加到线性松弛问题（作为约束）并返回步骤 3.2否则：
   继续。

步骤 5. 修剪和探索：

(a)如果≥Z:，则转至步骤3。

如果 Z^l <= Z AND X_i 是整数可行：
   Z = Z^i
   从 Set(L) 中删除所有 Z^i

步骤 6. 分区

让{\displaystyle D_{j=1}^{lj=k}}是约束集的一个分区{\displaystyle D} 问题的 {\displaystyle LP_{l}}。添加问题{\displaystyle D_{j=1}^{lj=k}}到 L，其中  {\displaystyle LP_{j}^{l}}是{\displaystyle LP_{l}} 可行区域限制为{\displaystyle D_{j}^{l}} 和{\displaystyle Z_{lj}} 对于 j=1，...k 设置为以下值{\displaystyle Z^{l}} 对于父问题l。转到步骤 3。[6]

数值例子

首先列出MILP：

{\displaystyle min\ z=-4x_{1}-7x_{2}}

{\displaystyle 6x_{1}+x_{2}\leq 13}

{\displaystyle -x_{1}+4x_{2}\leq 5}

{\displaystyle x_{1},x_{2}\geq 0}

原始LP的解决方案

{\displaystyle z=-19.56,x_{1}=1.88,x_{2}=1.72}


在 x 1 上分支以生成子问题

{\displaystyle min\ z=-4x_{1}-7x_{2}}

{\displaystyle 6x_{1}+x_{2}\leq 13}

{\displaystyle -x_{1}+4x_{2}\leq 5}

{\displaystyle x_{1}\geq 2}

{\displaystyle x_{1},x_{2}\geq 0}

拳头分支子问题的解法

{\displaystyle z=-15,x_{1}=2,x_{2}=1}

{\displaystyle min\ z=-4x_{1}-7x_{2}}

{\displaystyle 6x_{1}+x_{2}\leq 13}

{\displaystyle -x_{1}+4x_{2}\leq 5}

{\displaystyle x_{1}\leq 1}

{\displaystyle x_{1},x_{2}\geq 0}

第二分支子问题的解

{\displaystyle z=-14.5,x_{1}=1,x_{2}=1.5}

添加剪切

{\displaystyle min\ z=-4x_{1}-7x_{2}}

{\displaystyle 6x_{1}+x_{2}\leq 13}

{\displaystyle -x_{1}+4x_{2}\leq 5}

{\displaystyle 2x_{1}+x_{2}\leq 3}

{\displaystyle x_{1}\leq 1}

{\displaystyle x_{1},x_{2}\geq 0}

切割LP的解决方案

{\displaystyle z=-13.222,x_{1}=.778,x_{2}=1.444}

应用

下面更详细地描述了几个分支和剪切应用程序以及它们的使用方法。这些应用程序可作为使用分支和切割来有效优化各种问题的方法。

组合优化

组合优化是分支和剪切的一个很好的应用程序。这种优化方式是利用有限的已知集合和集合的信息来优化解决方案的方法。该应用程序的最初目的是为了最大化流量以及运输行业（Maltby 和 Ross）。这种组合优化也应用于一些经常使用的新领域。组合优化现在是研究人工智能和机器学习算法以优化解决方案的重要组成部分。组合优化倾向于利用和关注的有限集包括图、部分有序集以及定义线性独立性（称为拟阵）的结构。[7]

本德分解

Bender 的分解是另一种在随机规划中广泛使用的分支和剪切应用程序。本德分解是指将初始问题分为两个不同的子集。通过将问题分成两个单独的问题，您可以比原始实例 (Benders) 更容易地解决每一组问题。因此，可以针对第一变量集来解决所创建的子集中的第一个问题。考虑到第一个问题的解决方案，然后解决第二个子问题。这样做可以解决子问题以确定第一个问题是否不可行（Benders）。可以添加本德削减来限制问题，直到找到可行的解决方案。[6]

大规模对称旅行商问题

大规模对称旅行商问题是一个常见问题，人们总是在考虑优化最短路线，同时访问每个城市一次并最终返回原来的城市。在更大的范围内，这种类型的问题必须分解为子集或节点（SIAM）。通过限制这种类型的问题（例如组合优化方法），旅行商问题可以被视为部分有序集。通过在有限的城市中大规模执行此操作，您可以优化所采取的最短路径，并确保每个城市仅被访问一次。[8]

子模函数

子模函数是另一种在人工智能和机器学习中使用的函数。其原因是，随着函数输入的增加，值或输出会减少。由于输入不断增长，因此在上述情况下可以实现出色的优化功能。这使得机器学习和人工智能能够基于这些算法（Tschiatschek、Iyer 和 Bilmes）继续发展[9]。通过向系统强制执行新的输入，系统将了解越来越多的信息，以确保优化要制定的解决方案。[10]

结论

分支和剪切是一种用于优化整数线性规划的优化算法。它结合了其他两种优化算法 - 分支定界和切割平面，以便利用每种方法的结果来创建最佳解决方案。特定方法中使用了三种不同的方法——最不可行的分支、强分支和伪代码。此外，Branch and Cut可以应用于多种场景——子模函数、大规模对称旅行商问题、bender分解和组合优化，增加了方法的影响。

参考

  1. ^ 卡拉马诺夫, 米罗斯拉夫. “分支和剪切：实证研究。” 卡内基梅隆大学，2006 年 9 月，https://www.cmu.edu/tepper/programs/phd/program/assets/dissertations/2006-operations-research-karamanov-dissertation.pdf。

  2. ^ 卢德克, 吉姆. “解决混合整数优化问题的分支切割算法。” 数学家及其应用研究所，2016 年 8 月 10 日，https://www.ima.umn.edu/materials/2015-2016/ND8.1-12.16/25397/Luedtke-mip-bnc-forms.pdf。

  3. ^ 重新审视分支规则 Tobias Achterberga；*、Thorsten Kocha、Alexander Martinb https://www-m9.ma.tum.de/downloads/felix-klein/20B/AchterbergKochMartin-BranchingRulesRevisited.pdf

  4. ↑ 混合整数双层线性优化问题的分支割算法及其实现https://coral.ise.lehigh.edu/~ted/files/papers/MIBLP16.pdf

  5. ^ 混合整数编程的进展http://scip.zib.de/download/slides/SCIP-branching.ppt

  6. ↑跳转至：6.0 6.1 Benders, JF（1962 年 9 月），“解决混合变量编程问题的分区过程”，Numericsche Mathematik 4(3)：238–252。

  7. ^ 亨利·马尔特比和伊莱·罗斯。“组合优化。” 辉煌数学与科学维基，https://brilliant.org/wiki/combinatorial-optimization/。

  8. ^ 工业与应用数学学会。“暹罗牧师” SIAM 评论，2006 年 7 月 18 日，https://epubs.siam.org/doi/10.1137/1033004

  9. ^ S. Tschiatschek、R. Iyer、H. Wei 和 J. Bilmes，用于图像集合摘要的子模函数的学习混合，NIPS-2014。

  10. ^ A. Krause 和 C. Guestrin，《超越凸性：机器学习中的子模块性》，ICML-2008 教程

广东工业大学网络信息与现代教育技术中心电话：020-39323866   版权所有@ 2020-2021保留所有权利  
粤ICP备05008833号
手机版 访问量：次

开通时间： ..

最后更新时间： ..