benders分解是将问题分为限制主问题和子问题，然后主问题向子问题传入变量，接着根据子问题求解的信息向主问题返回割（最优割和可行割），这些割以约束的形式被添加到主问题中。其中，子问题因为求解得到的解是可行的，是上界Ub，主问题因为添加的约束不够，可行域缩小，是下界。不断重复上述过程，直到Ub=Lb，即限制主问题中已经添加了所有应该添加的完备的约束信息，当前限制主问题与原始问题等价，求解结束，输出最优解。
割其实描述的子问题告诉限制主问题的信息，告诉限制主问题先前提供的解好不好，以及指导下一步该怎么做。
上述是benders分解算法的思路。根据主问题MP和子问题SP特点的不同，可以分为经典的benders算法和广义的benders算法（区别是前者是线性对偶，后者是推理对偶），后者又可以分为整数benders算法和逻辑benders算法。因此benders算法可以分为三类，经典的benders算法、整数benders算法、和逻辑benders算法。
经典benders算法可以参见：
(1) benders分解算法 逻辑思路整理
(2) benders decompositon学习笔记记录
逻辑benders算法可以参见：逻辑benders分解。
本节详细介绍整数benders分解。
1.整数benders分解问题结构：
当限制主问题LMP是0-1规划问题，而子问题SP是整数规划问题时，可以采用整数benders分解算法求解。
正因为有上述特性，因此可以利用上述特性来构造割的信息进而进行求解。
2.整数benders算法介绍：
类比经典的benders分解算法，即子问题包含在原始问题（原问题）中，因此子问题的求解信息与原问题是同步的。
（1）子问题假如不可行，那么原问题也不可行；
（2）子问题可行，那么原问题也可行；
（3）子问题无界，那么原问题也无界。
因为子问题不可行，原问题不可行，没有优化的意义，因此我们不需要考虑这种情况。需要考虑的是后两种。（这是经典benders分解中的内容）
我们需要考虑的是子问题可行以及子问题无界的情形，即返回最优割和可行割的情形。
那么现在的问题变为了对偶问题如何与子问题建立联系？经典benders中的对偶理论中的内容不再适用。通过推理的方式来构造对应的割。
（1）可行割
首先考虑可行割，即求解子问题得到的解是无界的，那么我们需要排除掉这个情形，即下一次不能再给子问题输入这样的解了。
可以构造可行割如下：
∑
j
:
y
^
=
0
y
j
+
∑
j
:
y
^
=
1
(
1
−
y
j
)
≥
1
\sum_{j:\hat{y}=0 }y_{j}+\sum_{j:\hat{y}=1 }(1-y_{j}) \ge 1
j:y^=0∑yj+j:y^=1∑(1−yj)≥1
分析如下：
我们需要排除目前的这个解，即这个解不满足该约束。将该解代入约束，发现约束左边为0+0=0，右边为1,0≥1是不满足的。因此可以把该解排除。
可行割利用的就是主问题是0-1规划的性质，解只能取0/1，因此可以构造上式。
（2）最优割
以下是最优割，即子问题输出的解是原问题的上界，我们需要构造出不等式来指导下一步前进的方向。
可以构造最优割如下：
q
≥
ϕ
(
y
ˉ
)
−
[
ϕ
(
y
ˉ
)
−
L
]
[
∑
j
:
y
ˉ
=
0
y
j
+
∑
j
:
y
ˉ
=
1
(
1
−
y
j
)
]
q \ge \phi (\bar{y} )-\left [ \phi (\bar{y} ) - L \right ] [\sum_{j:\bar{y}=0 }y_{j}+\sum_{j:\bar{y}=1 }(1-y_{j})]
q≥ϕ(yˉ)−[ϕ(yˉ)−L][j:yˉ=0∑yj+j:yˉ=1∑(1−yj)]
分析如下：
其中，第一部分 ϕ ( y ˉ ) \phi (\bar{y} ) ϕ(yˉ)表示松弛子问题的解，与经典benders分解子问题的解是一样的。后面两部分是整数benders和经典benders的区别。
我们注意到子问题是整数规划，为了求得它的值，我们可以构造松弛子问题LSP，求解LSP对偶问题可以为SP问题提供一些信息。
L
L
L是松弛子问题LSP（输入所有的
ϕ
(
y
ˉ
)
\phi (\bar{y} )
ϕ(yˉ)中）的最小值（有效下界），
[
ϕ
(
y
ˉ
)
−
L
]
\left [ \phi (\bar{y} ) - L \right ]
[ϕ(yˉ)−L]表示松弛子问题LSP与有效下界之间的差距，表明的是前进的方向。而第三项
[
∑
j
:
y
ˉ
=
0
y
j
+
∑
j
:
y
ˉ
=
1
(
1
−
y
j
)
]
[\sum_{j:\bar{y}=0 }y_{j}+\sum_{j:\bar{y}=1 }(1-y_{j})]
[∑j:yˉ=0yj+∑j:yˉ=1(1−yj)]表示
y
y
y的变化量，二者一综合提供了方向和步长。若使用推理的形式写出，描述如下：
上述是经典benders分解，下述是整数benders分解的推理过程。可以看到
λ
T
\lambda^{T}
λT其实就是我们构造的
[
ϕ
(
y
ˉ
)
−
L
]
\left [ \phi (\bar{y} ) - L \right ]
[ϕ(yˉ)−L]。
(
y
−
y
ˉ
k
)
(y-\bar{y}_{k})
(y−yˉk)其实就是我们构造的第三项
[
∑
j
:
y
ˉ
=
0
y
j
+
∑
j
:
y
ˉ
=
1
(
1
−
y
j
)
]
[\sum_{j:\bar{y}=0 }y_{j}+\sum_{j:\bar{y}=1 }(1-y_{j})]
[∑j:yˉ=0yj+∑j:yˉ=1(1−yj)]。
至此，构造出对应的最优割和整数割，求解完毕。
但该法有个问题，即每次添加的可行割只去除了一个解，效率是非常低的。我们需要根据问题的结构设计出有效的可行割，这也是逻辑benders分解的内容。也是论文发表的方向。
参考资料：
069-线性规划（十四）：整数Benders分解
