背景介绍
Benders decomposition由Jacques F. Benders提出，常用于解决混合整数规划模型。在经典Benders decomposition中，问题被分解为整数规划主问题和线性规划子问题，过程在求解主问题和求解每个子问题之间反复进行，直到找到最优解。
但对于一些组合优化问题，例如在设施选址问题和各类生产调度问题中，通常包含复杂的逻辑结构并且涉及一系列离散决策，其子问题没有实用的线性模型，传统的Benders分解不再适用。幸运的是，Benders分解的一种扩展——Logic-based Benders decomposition给我们提供了解决任意子问题的方法，本文将对此做具体介绍。
在很久之前公众号曾经出过介绍Benders decomposition的推文，有需要的请点击下方链接查看。
Benders decomposition由Jacques F. Benders提出，常用于解决混合整数规划模型。在经典Benders decomposition中，问题被分解为整数规划主问题和线性规划子问题，过程在求解主问题和求解每个子问题之间反复进行，直到找到最优解。
但对于一些组合优化问题，例如在设施选址问题和各类生产调度问题中，通常包含复杂的逻辑结构并且涉及一系列离散决策，其子问题没有实用的线性模型，传统的Benders分解不再适用。幸运的是，Benders分解的一种扩展——Logic-based Benders decomposition给我们提供了解决任意子问题的方法，本文将对此做具体介绍。
在很久之前公众号曾经出过介绍Benders decomposition的推文，有需要的请点击下方链接查看。
Benders分解回顾
在开始之前，我们先对Benders decomposition做一个简单回顾，这里我们直接使用[1]中的介绍。
令原问题为
将问题拆分为master problem和线性规划subproblem
master problem
其中q(y)代表子问题目标函数的最优值
subproblem
对于任意y，问题(3)都是线性规划模型。
如果(3)无界，可得到原问题也无界；若有界，我们可以通过计算其对偶问题来得到q(y)
dual problem
在对偶问题中，为对偶变量。
变量y只影响对偶问题目标函数值而不影响可行域。因此由对偶理论，如果对偶问题不可行时，要么问题(3)对于某些y无界——也就是说原问题无界，要么问题(3)对于所有y都不可行——即原问题不可行。
如果问题(3)可行，我们可以枚举出可行域内的所有极值点和极射线
由此我们引出对偶问题的另一个形式reformulation of dual problem
其中q为q(y)，(5b)和(5c)分别是有关问题可行性和最优性的cuts。
有关Benders feasibility cuts和Benders optimality cuts的证明，请参考Benders本人发表的[2]中的Lemma 4.1和Lemma 4.2，需要注意的是，文中的原问题是最大化问题；Benders feasibility cuts的证明也可以参考《introduction to linear optimization》的Theorem 4.14。
最后得到的主问题为：
伪代码为：![]()
在开始之前，我们先对Benders decomposition做一个简单回顾，这里我们直接使用[1]中的介绍。
令原问题为
将问题拆分为master problem和线性规划subproblem
master problem
其中q(y)代表子问题目标函数的最优值
subproblem
对于任意y，问题(3)都是线性规划模型。
如果(3)无界，可得到原问题也无界；若有界，我们可以通过计算其对偶问题来得到q(y)
dual problem
在对偶问题中，为对偶变量。
变量y只影响对偶问题目标函数值而不影响可行域。因此由对偶理论，如果对偶问题不可行时，要么问题(3)对于某些y无界——也就是说原问题无界，要么问题(3)对于所有y都不可行——即原问题不可行。
如果问题(3)可行，我们可以枚举出可行域内的所有极值点和极射线
由此我们引出对偶问题的另一个形式reformulation of dual problem
其中q为q(y)，(5b)和(5c)分别是有关问题可行性和最优性的cuts。
有关Benders feasibility cuts和Benders optimality cuts的证明，请参考Benders本人发表的[2]中的Lemma 4.1和Lemma 4.2，需要注意的是，文中的原问题是最大化问题；Benders feasibility cuts的证明也可以参考《introduction to linear optimization》的Theorem 4.14。
最后得到的主问题为：
伪代码为：
Logic-based Benders decomposition
Logic-based Benders decomposition[3]（基于逻辑的Benders分解）是对经典Benders decomposition的扩展，适用于任意形式的子问题，并且尤其适用于包含复杂的逻辑关系的混合整数规划问题，下面进行具体介绍。
Logic-based Benders decomposition[3]（基于逻辑的Benders分解）是对经典Benders decomposition的扩展，适用于任意形式的子问题，并且尤其适用于包含复杂的逻辑关系的混合整数规划问题，下面进行具体介绍。
引入：经典Benders分解的基本观点及优势
classic Benders decomposition的求解策略基本可以分为以下几步：
将原问题的变量拆分为两个部分，设为x和y。 先求解master problem以固定y值，然后将y带入子问题。如果子问题结果表明y不被接受，则运用子问题的对偶排除类似的y（即加入Benders cuts）。 最终只剩下可接受的值，如果一切顺利，算法在只枚举出 y 的几个可能值后就结束了。
相较于一般方法，Benders decomposition的优势为：
解决问题之前，预先拆分变量以优化解的结构。y固定之后，所产生的子问题求解起来会大大简化。 子问题具有线性，因此可以通过一种简单而系统的方法，即通过求解线性规划对偶，来获得Benders cut。
结合以上两点优势，如果要推广Benders decomposition以求解线性规划之外的子问题，关键在于推广对偶的概念。对偶须定义为任何类型的子问题，并为主问题提供合适的约束。
classic Benders decomposition的求解策略基本可以分为以下几步：
将原问题的变量拆分为两个部分，设为x和y。 先求解master problem以固定y值，然后将y带入子问题。如果子问题结果表明y不被接受，则运用子问题的对偶排除类似的y（即加入Benders cuts）。 最终只剩下可接受的值，如果一切顺利，算法在只枚举出 y 的几个可能值后就结束了。
相较于一般方法，Benders decomposition的优势为：
解决问题之前，预先拆分变量以优化解的结构。y固定之后，所产生的子问题求解起来会大大简化。 子问题具有线性，因此可以通过一种简单而系统的方法，即通过求解线性规划对偶，来获得Benders cut。
结合以上两点优势，如果要推广Benders decomposition以求解线性规划之外的子问题，关键在于推广对偶的概念。对偶须定义为任何类型的子问题，并为主问题提供合适的约束。
inference duality 推理对偶
基于以上观点，J.N. Hooker等人[3]提出了inference dual的概念，从约束集中推理出可能的最强约束。
对于一般优化问题(1)
其中S为可行集feasible set；D为x所属的值域，例如0-1或实数域。
假设P和Q是两个命题，他们的真或假取决于x（即真或假是x的函数），记为P在D的背景下蕴含Q。即对于任意x属于D，若P为真，Q一定为真。
则优化问题(1)的inference dual(2)为
dual寻求最大的β使得约束集蕴含(imply) .换句话说，对偶问题的目的是寻找目标函数值的一个尽可能紧的界。这也是上文Benders optimality cut的目的。
假设问题(1)不可行时最优值为正无穷，无界时最优值为负无穷。可知inference dual具有强对偶性——原问题和推理对偶具有相同的最优值。
基于以上观点，J.N. Hooker等人[3]提出了inference dual的概念，从约束集中推理出可能的最强约束。
对于一般优化问题(1)
其中S为可行集feasible set；D为x所属的值域，例如0-1或实数域。
假设P和Q是两个命题，他们的真或假取决于x（即真或假是x的函数），记为P在D的背景下蕴含Q。即对于任意x属于D，若P为真，Q一定为真。
则优化问题(1)的inference dual(2)为
dual寻求最大的β使得约束集蕴含(imply) .换句话说，对偶问题的目的是寻找目标函数值的一个尽可能紧的界。这也是上文Benders optimality cut的目的。
假设问题(1)不可行时最优值为正无穷，无界时最优值为负无穷。可知inference dual具有强对偶性——原问题和推理对偶具有相同的最优值。
线性规划与inference dual
对于如下LP问题
其inference dual为
如果要推理对偶的约束成立，就要寻找实数向量,使得，也就是说，存在u使得不等式 优超(dominate) 不等式 。则可以得到inference dual的另一种形式为：
这也是线性规划问题的典型对偶形式，由此可以证明线性规划inference dual的完备性。
对于如下LP问题
其inference dual为
如果要推理对偶的约束成立，就要寻找实数向量,使得，也就是说，存在u使得不等式 优超(dominate) 不等式 。则可以得到inference dual的另一种形式为：
这也是线性规划问题的典型对偶形式，由此可以证明线性规划inference dual的完备性。
抽象形式的Logic-based Benders decomposition
令抽象形式的Benders分解原问题为
其中和为x和y的值域，S仍为可行域。
固定y的值为，得到子问题
假设子问题最优值在不可行时为正无穷，无界时为负无穷。则问题满足强对偶性。
子问题的inference dual为：
则inference dual的目的为：固定y的值为，在由约束条件推得的最优成本上找到最优下界。为了详细解释这一过程，我将在之后的实例讲解中进行展示。
该方法的核心是通过某种方式推导出一个函数，该函数对任意固定的y值给出原问题最优值的有效下界。inference dual得到的主问题为
该问题约束中的不等式即为生成的Benders cut。（注意：Benders cuts并非是对目标函数最优值的直接约束，而是反馈在某种决策变量取值情况下的目标函数的边界信息，这种的约束加入能逐步缩减松弛主问题的解空间）
基于上述问题，可以给出通用Benders decomposition算法的步骤为
![]()
上述算法一般不需要终止，即使子问题总是被求解到最优性（相关例子请查看[3] Theorem 1，在此不赘述）。但如果y的值域为有限集，则算法必须要终止：因为过程中要求不断增加，但只有有限多个子问题可以被定义，经过有限步才能达到最优。
令抽象形式的Benders分解原问题为
其中和为x和y的值域，S仍为可行域。
固定y的值为，得到子问题
假设子问题最优值在不可行时为正无穷，无界时为负无穷。则问题满足强对偶性。
子问题的inference dual为：
则inference dual的目的为：固定y的值为，在由约束条件推得的最优成本上找到最优下界。为了详细解释这一过程，我将在之后的实例讲解中进行展示。
该方法的核心是通过某种方式推导出一个函数，该函数对任意固定的y值给出原问题最优值的有效下界。inference dual得到的主问题为
该问题约束中的不等式即为生成的Benders cut。（注意：Benders cuts并非是对目标函数最优值的直接约束，而是反馈在某种决策变量取值情况下的目标函数的边界信息，这种的约束加入能逐步缩减松弛主问题的解空间）
基于上述问题，可以给出通用Benders decomposition算法的步骤为
上述算法一般不需要终止，即使子问题总是被求解到最优性（相关例子请查看[3] Theorem 1，在此不赘述）。但如果y的值域为有限集，则算法必须要终止：因为过程中要求不断增加，但只有有限多个子问题可以被定义，经过有限步才能达到最优。
运用inference dual处理0-1规划问题
给定0-1规划模型
固定y的值，得到子问题的inference dual为
给定y的原问题可以用分支定界求解，得到一个最优值；再继续求解其dual problem以获得Benders cut，dual的解必须满足以为前提，证明。求解的一个直接方法是将上述分支定界树解释为最优性的证明。
首先我们引入逻辑学的一个概念：clase（子句）是由一个或多个文字（literals）通过逻辑析取（disjunction）连接而成的。析取是逻辑运算的一种，表示“或”的关系，用符号 “∨” 表示。在子句中，如果有一个或多个文字为真，则整个子句为真。文字是原子命题（atomic proposition）或其否定形式。例如，x1 ∨¬x2 ∨¬x3是一个断言x1为真或x2为假或x3为假的子句。
在叶节点t，令为所有的集合，其中的分支将设置为1，对对应的分支将设置为0。则如下的子句一直会被固定变量所违背。（只要有一个变量取0或1，就有一段literal为false）
令为叶节点t处的所违背的不等式。只要满足最优性证明，一直蕴含一个在该节点处被证伪的子句。这个不等式就可以用来生成Benders cut。（这个我们下面会讲解）
叶节点t处，问题的松弛可以写为
其中不等式包含对x的上界约束、对固定的的约束和固定的的约束。和为对应的对偶变量。
上述的松弛问题的求解结果有三种，接下来我们逐一分析。
此处我们先引入一个lemma：令，0-1变量不等式蕴含子句，当且仅当
这个很好理解，满足这个不等式条件时，一定有变量被固定，所以子句被证伪。
三种情况分别为：
给定0-1规划模型
固定y的值，得到子问题的inference dual为
给定y的原问题可以用分支定界求解，得到一个最优值；再继续求解其dual problem以获得Benders cut，dual的解必须满足以为前提，证明。求解的一个直接方法是将上述分支定界树解释为最优性的证明。
首先我们引入逻辑学的一个概念：clase（子句）是由一个或多个文字（literals）通过逻辑析取（disjunction）连接而成的。析取是逻辑运算的一种，表示“或”的关系，用符号 “∨” 表示。在子句中，如果有一个或多个文字为真，则整个子句为真。文字是原子命题（atomic proposition）或其否定形式。例如，x1 ∨¬x2 ∨¬x3是一个断言x1为真或x2为假或x3为假的子句。
在叶节点t，令为所有的集合，其中的分支将设置为1，对对应的分支将设置为0。则如下的子句一直会被固定变量所违背。（只要有一个变量取0或1，就有一段literal为false）
令为叶节点t处的所违背的不等式。只要满足最优性证明，一直蕴含一个在该节点处被证伪的子句。这个不等式就可以用来生成Benders cut。（这个我们下面会讲解）
叶节点t处，问题的松弛可以写为
其中不等式包含对x的上界约束、对固定的的约束和固定的的约束。和为对应的对偶变量。
上述的松弛问题的求解结果有三种，接下来我们逐一分析。
此处我们先引入一个lemma：令，0-1变量不等式蕴含子句，当且仅当
这个很好理解，满足这个不等式条件时，一定有变量被固定，所以子句被证伪。
三种情况分别为：
1.松弛问题不可行
在这种情况下，目标函数为正无穷。则对偶变量满足
依据这两个不等式和，可以推得下面的不等式不可行。分支定界过程中一直有x被固定，所以该不等式一直满足上述的lemma。由lemma可以得到蕴含当且仅当
其中为A的第j列。令该不等式为
在这种情况下，目标函数为正无穷。则对偶变量满足
依据这两个不等式和，可以推得下面的不等式不可行。分支定界过程中一直有x被固定，所以该不等式一直满足上述的lemma。由lemma可以得到蕴含当且仅当
其中为A的第j列。令该不等式为2.松弛问题可行，解均为整数
设最优值为，则对偶变量满足条件
上述不等式组可行，将其合并为一个不等式并取反可以得到不可行的不等式为
同理，得到为
设最优值为，则对偶变量满足条件
上述不等式组可行，将其合并为一个不等式并取反可以得到不可行的不等式为
同理，得到为3.松弛可行，但有非整数解
此步骤解的最优值一般大于等于分支定界得到的最终解。分析过程与2同理，得到为
生成Benders cut
对偶解在每个叶节点上都会得到1或2中的一个不等式。 子问题的最优值为分支定界过程中在节点t得到的最小值。 对任意y，分支定界树证明了在选择这个y的情况下，是原问题最优值的有效下界。
为了更精确的分析，我们把子问题解耦成更小的问题时，形式如下
向量不包含相同的变量。通过求解每个子问题
得到对应的最优值。最终得到的最优值为设是求解分支定界树在t节点处得到的不等式，则Benders cut为
其中是得到的搜索树中叶节点的集合。Ji也是xi中变量的索引集。 ， 计算了cx的最小可能值，为y不满足的情况提供一个默认下界。
![]()
子问题解耦的0 - 1规划的Benders算法 [3]中提供了一个具体详细的例子，此处不进行解释，感兴趣的请自行查看。
此步骤解的最优值一般大于等于分支定界得到的最终解。分析过程与2同理，得到为
生成Benders cut
对偶解在每个叶节点上都会得到1或2中的一个不等式。 子问题的最优值为分支定界过程中在节点t得到的最小值。 对任意y，分支定界树证明了在选择这个y的情况下，是原问题最优值的有效下界。
为了更精确的分析，我们把子问题解耦成更小的问题时，形式如下
向量不包含相同的变量。通过求解每个子问题
得到对应的最优值。最终得到的最优值为设是求解分支定界树在t节点处得到的不等式，则Benders cut为
其中是得到的搜索树中叶节点的集合。Ji也是xi中变量的索引集。 ， 计算了cx的最小可能值，为y不满足的情况提供一个默认下界。
[3]中提供了一个具体详细的例子，此处不进行解释，感兴趣的请自行查看。
LBBD结合Constraint Programming
[3]中，作者提到Logic-based Benders Decomposition最有前景的应用是作为优化和约束规划(constraint programming)相结合的框架。
因此，在下一篇分享LBBD实例的推文中，笔者将为大家详细介绍一种用Logic-based Benders decomposition解决capacity- and distance-constrained plant location problem (CDCPLP，带容量和运输距离限制的工厂选址问题)的方法[4]，其中对子问题的建模采用constraint programming。同时，笔者会实现对应的Java代码供大家学习参考。
[3]中，作者提到Logic-based Benders Decomposition最有前景的应用是作为优化和约束规划(constraint programming)相结合的框架。
因此，在下一篇分享LBBD实例的推文中，笔者将为大家详细介绍一种用Logic-based Benders decomposition解决capacity- and distance-constrained plant location problem (CDCPLP，带容量和运输距离限制的工厂选址问题)的方法[4]，其中对子问题的建模采用constraint programming。同时，笔者会实现对应的Java代码供大家学习参考。
参考文献
[1]Decomposition and Z Caner Ta¸skın. “Benders Decomposition ∗.” (2015).
[2]Benders, J.F. Partitioning procedures for solving mixed-variables programming problems. Numer. Math. 4, 238–252 (1962). https://doi.org/10.1007/BF01386316
[3]Hooker, J. and Greger Ottosson. “Logic-based Benders decomposition.” Mathematical Programming 96 (2003): 33-60.
[4]Mohammad M. Fazel-Zarandi, J. Christopher Beck, (2011) Using Logic-Based Benders Decomposition to Solve the Capacity- and Distance-Constrained Plant Location Problem. INFORMS Journal on Computing 24(3):387-398.
[1]Decomposition and Z Caner Ta¸skın. “Benders Decomposition ∗.” (2015).
[2]Benders, J.F. Partitioning procedures for solving mixed-variables programming problems. Numer. Math. 4, 238–252 (1962). https://doi.org/10.1007/BF01386316
[3]Hooker, J. and Greger Ottosson. “Logic-based Benders decomposition.” Mathematical Programming 96 (2003): 33-60.
[4]Mohammad M. Fazel-Zarandi, J. Christopher Beck, (2011) Using Logic-Based Benders Decomposition to Solve the Capacity- and Distance-Constrained Plant Location Problem. INFORMS Journal on Computing 24(3):387-398.
