问题定义
对于一个存在耦合约束或复杂变量的较难优化问题:
mincTx+fTys.tAx+By=bx∈Xx≥0y∈Y
假设y是整数或BINARY
等复杂变量,当y值固定时,原问题可以转化为相对容易求解的问题,故该问题可以拆分为==主问题==和==子问题==两部分:
minfTy+q(y)y∈Y(Master)
mincTxs.tAx=b−Byx∈Xx≥0(Sub)
由于Sub
子问题的可行域受Master
主问题中设定的y取值影响,不好定量判断是否为空集,故将子问题写成对偶问题形式
maxuT(b−By)s.tATu≤cu无约束(Sub-Dual)
若Sub-Dual
问题可行域为空(注意这里的可行域与y无关,下述内容对Master
主问题中∀y∈Y成立),即子问题的对偶问题不可行,则子问题无界或不可行,此时对∀y∈Y,整个问题都不可解,我们不考虑这种情况,只考虑Sub-Dual
子问题可行域不为空的情况,设此时该子问题的极点和极射线集合如下: 极点和极射线
{upi∣∀i∈I}:极点集合{urj∣∀j∈J}:极射线集合
极点和极射线对问题的性质影响如下:
- 若存在某条极射线使得
(urj)T(b−By)>0
则Sub-Dual
无界
2. 若存在某个极点使对偶目标函数值最大
(upi)T(b−By)=max{(upi)T(b−By)∣∀i∈I}
则Sub
子问题有有限的最优解
综上,Sub-Dual
可以写成:
minqs.t(urj)T(b−By)≤0(upi)T(b−By)≤qq无约束(Sub-Dual)
Sub-Dual
改写完毕后,可将其代回到Master
主问题中
s.tminfTy+q(urj)T(b−By)≤0(upi)T(b−By)≤qy∈Yq无约束(master)
(urj)T(b−By)≤0(1)
(upi)T(b−By)≤q(2)
此时,表面看上去问题转化成了一个仅有y的优化问题,但实际上,列出全部的极点和极射线基本是不可能的。因此,我们下面介绍Benders
分解法的具体步骤
Benders算法步骤
- 不添加任何约束簇(1)和约束簇(2)中的约束,求解
Master
问题,得到原问题的LB:此时Master
问题中目标函数和约束中都不考虑x
的影响,约束比原问题少很多,目标函数中除y之外的q也无约束,因此其必然是原问题的一个下界
- 第1步得出的y传到
Sub
中(实际操作中为了方便可以不将子问题转化为Sub-Dual
的对偶形式),求解Sub
子问题:
- 如果
Sub
子问题可行,那么此时这组(x, y)为可行解,此时子问题的目标函数值与主问题的目标函数值之和必然为原问题的上界。因此,从子问题中得到极点(对偶问题最优解π),更新原问题的上界UB,并添加最优约束cut
(2)
- 如果
Sub
子问题不可行,则得到极射线,添加可行约束cut
(1)(这里要注意,如果子问题不转化为其对偶形式,基于Gurobi
直接获取Constr.FarkasDual
属性作为极射线的话,需要对该属性取负值才是真正的极射线向量值)
- 接着求解
Master
问题,得到y值返回给子问题,直到UB和LB之间的gap满足收敛条件为止