运筹学教学|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分解算法具体说明

给定一个线性优化问题：

其中x和y分别是p和q维向量，Y是y所在的可行域空间，A、B是矩阵，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。在每次迭代过程中都可以生产某一类型的约束，由于I和J是有限的，故可以保证在有限次迭代过程后得到最优解。

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）