运筹学教学|Benders decomposition(一)技术介绍篇

相约女神节

biu~ biu~ biu~

我们的运筹学教学推文又出新文拉

还是熟悉的配方,熟悉的味道

今天向大家推出的是

Benders decomposition(一)技术介绍篇

1.背景介绍

Benders分解算法是由Jacques F. Benders在1962年首先提出,目的是用于解决混合整数规划问题(mixed integer programming problem,简称MIP问题),即连续变量与整数变量同时出现的极值问题[1]。但它的实际应用并不限于此,A.M. Geoffrion建立了广义的Benders分解法,它可以对具有Benders分解基本形式的非线性问题求解,对子问题的求解方法也不必一定是线性的。Benders 分解法是一个很常用的方法,用来计算像整数非线性规划问题和随机规划问题之类的难以解决的问题。

Jacques F. Benders设计了一个巧妙的途径,来求解具有复杂变量的数学规划问题。所谓的复杂变量是指,当将这些变量固定后,剩下的优化问题(通常称为子问题)变得相对容易。在Benders考虑的一类特殊问题中,先把复杂变量的值固定,从而将问题规约为一个一般的线性规划问题,当然,这个线性规划问题是以复杂变量为参数的。在Benders设计的算法里,利用割平面的方式将主问题(以子问题的解为参变量)的极值和使子问题(线性规划问题)有可行解的参变量值的集合很恰当地表达了出来。过程中,对偶理论用来推导刻画这些表达式特征的自然割平面族,而带有参变量的线性规划问题被用来生成割平面。

在1976年,Florian[2]将这个算法应用于铁路机车的调度问题。1976年,Richardso[3]把这个算法应用于航空路线规划,1974年 Geoffrion和Graves[4]成功地把这个算法应用于设计工业分配系统。从1978年开始,Fisher和 Jaikumar[5]就在研究讨论利用这个算法的优势来规划机动车的路线。以上这些应用说明Benders分解算法用来解决各种特定结构的混合整规划问题有很大的优势。

2.Benders分解算法具体说明

给定一个线性优化问题:

其中xy分别是pq维向量,Yy所在的可行域空间,AB是矩阵,b、c、f表示适当的一维向量。

假设y是复杂变量,当y值固定时,原问题可以转化为相对容易求解的问题,利用Benders方法可以将问题分解为两部分:

其中q(y)表示当y值固定时子问题的最优解。

可以发现,子问题(3)是线性优化问题,如果子问题无界,那么主问题(2)也必定无界,此时原问题(1)也无界,那么原问题没有最优解。我们假设子问题(3)有界,我们可以通过求解子问题(3)的对偶问题来计算q(y)。子问题的对偶问题可以写成:

从对偶问题(4)中可以发现对偶问题的可行域不依赖于y的值,而y的值仅影响目标函数。因此,当我们给定y的值时,例如

,如果对偶问题的可行域为空,那么原问题无界或可行域也为空(此时对所有的y原问题都为空)。假设式子(4)不为空,我们可以枚举对偶问题所有的极点(extreme points)

极射线(extreme rays)

,其中I和J分别表示极点和射线的个数。对于一个给定的y的值,

,可以通过检测:(a)对于所有的极射线式子

是否成立[6],(b)能否找到一个极点使对偶问题目标函数值

最大。如果(a)存在,则对偶问题无界且原问题无解,如果(b)成立,则对偶问题和原问题都有有限的最优解。

注:(a)的理论依据见参考文献[2],178页Theorem 4.14,具体理论如下:

对于一个最小化问题

,约束条件为

,假设可行域中至少存在一个极点。则最优解为-∞的条件为当且仅当存在某个极射线d使

。注意本文中用来举例的子问题的对偶问题是最大化问题,参考文献[2]中提及的是最小化问题。

基于上述理论,对偶问题可以重新写成:

从(5)可以发现只有q一个变量,但是存在很多个约束。我们用(5)代替(2)中的q(y),则原问题可以写成:

由于极射线和极点数量庞大,如果要生成所有的约束显然不现实。Benders算法求解的是松弛主问题(Relaxed master problem),即松弛主问题中的约束是原问题中约束(6b)和(6c)的一个子集。最开始,初始松弛主问题中无约束,在Benders算法求解过程中不断向松弛主问题中加入约束(6b)和(6c)中的某一个,即加入有效的切平面(cut)。通过求解松弛主问题,我们可以得到一个候选最优解(y*,q*),然后将y*代入对偶子问题(4)中求解计算q(y*)值,如果子问题的最优解q(y*)=q*,则算法停止。如果对偶问题无解,则在松弛主问题中可以加入(6b)类型的约束,然后求解新的松弛主问题。(6b)类型的约束称之为Benders feasibility cuts。如果对偶子问题的最优解q(y*)>q*,则在松弛主问题中可以引入(6c)类型的约束,然后求解新的松弛主问题。(6c)类型的约束称之为Benders optimality cuts。在每次迭代过程中都可以生产某一类型的约束,由于IJ是有限的,故可以保证在有限次迭代过程后得到最优解。

Benders算法实现过程:

初始化:

y:=有效的整数解

LB:=-∞

UB:=∞

参考文献:

[1].https://en.wikipedia.org/wiki/Benders_decomposition

[2].Florian M, Bushell G, Ferland J, et al. The Engine Scheduling Problem In A Railway Network[J]. Infor Information Systems & Operational Research, 1972, 14(2):39-43.

[3].Richardson R. An Optimization Approach to RoutingAircraft[J]. Transportation Science, 1976, 10(1):52-71.

[4].Geoffrion A M, Graves G W. MulticommodityDistribution System Design by Benders Decomposition[J]. Management Science,1980, 26(8):855-856.

[5].Fisher M L, Jaikumar R. A generalized assignmentheuristic for vehicle routing[J]. Network, 1979, 11(2):109-124.

[6].Bertsimas D, Tsitsiklis J. Introduction to LinearOptimization[M]// Introduction to linear optimization /. Athena Scientific,1997:57-9.

—end—

编辑:黄楠(huangnanhust@163.com, 华中科技大学管理学院博士一年级)

指导老师:秦时明月(professor.qin@qq.com)

原文发布于微信公众号 - 数据魔术师(gh_39567a079597)

原文发表时间:2018-03-08

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏腾讯音视频实验室

带宽节省利器——帧率上采样

目前大多数人都关注点都在超分辨率技术上,为何不Pick一下帧率上采样呢?

7.8K40
来自专栏机器学习算法与Python学习

Machine Learning -- Bayesian network

链接地址:http://www.dataguru.cn/thread-508373-1-1.html 0 引言 事实上,介绍贝叶斯定理、贝叶斯方法、贝叶斯推断的...

53060
来自专栏IT派

读懂概率图模型:你需要从基本概念和参数估计开始

概率图模型是人工智能领域内一大主要研究方向。近日,Statsbot 团队邀请数据科学家 Prasoon Goyal 在其博客上分两部分发表了一篇有关概率图模型的...

43240
来自专栏贾志刚-OpenCV学堂

图形图像算法中必须要了解的设计模式(1)

随着信息的多元化,信息的概念不仅仅指的是文字,它还包含图片、声音、视频等其它丰富的信息。文字信息越来越多地被图片、声音、视频信息所替代,而视频又是由一针一针的图...

15930
来自专栏新智元

【深度学习会被可微分编程取代?】展望30年后的神经网络和函数编程

作者:colah 译者:文强,刘小芹 【新智元导读】在Yann LeCun“深度学习已死”的惊人发言下,可微分编程的概念引发了广泛关注。机器学习著名博主cola...

42240
来自专栏深度学习自然语言处理

简单实例讲解为何深度学习有效

在之前的一些年里,深度学习已经占领了模式识别领域,之后又横扫了计算机数视觉,之后自然语言处理也慢慢的朝着这个方向开始了它的发展。

9320
来自专栏算法channel

入门解读 seq2seq 和注意力模型

29140
来自专栏量化投资与机器学习

【Python机器学习】信息熵和在决策树中的运用(附源码)

之前在【Python机器学习】系列五决策树非线性回归与分类(深度详细附源码)一期中, 我们提到了用熵来度量信息的不确定性和信息增益。今天我们来详细解读一下什么是...

39270
来自专栏数据科学与人工智能

【陆勤阅读】深度学习、自然语言处理和表征方法

简介 过去几年,深度神经网络在模式识别中占绝对主流。它们在许多计算机视觉任务中完爆之前的顶尖算法。在语音识别上也有这个趋势了。 虽然结果好,我们也必须思考……它...

319100
来自专栏机器学习AI算法工程

用R语言做钻石价格预测

作者:夏尔康 https://ask.hellobi.com/blog/xiaerkang/4424 1.1问题描述和目标 因为钻石的价格定价取决于重量...

48950

扫码关注云+社区

领取腾讯云代金券