【整数规划算法】分支定界法及其Python代码实现

【整数规划算法】分⽀定界法及其Python 代码实现

1 最优性条件与分⽽治之两⼤思路的结合

求解⼀般的最优化问题的基本策略是先建⽴该问题的最优性条件，然后根据最优性条件利⽤迭代算法寻满⾜该条件的可⾏解。这种基本策略已经在线性规划，⼆次规划，⾮线性规划问题中得到了很多使⽤。⽽在整数规划问题中，我们⽆法采⽤微积分这样的⼯具来构建最优性条件，因此并没有像连续优化问题那样有⽐较好的最优性条件(例如 KKT条件)，这也正是造成整数规划问题求解困难的主要原因。基于这个思路，我们尝试从最基本的最优性原理出发来构造整数规划问题的近似最优性条件。

考虑如下的整数规划问题IP：

其中为上述整数规划问题的最优解。

假设我们依据某个算法可以得到如下关于该整数规划问题上界的序列：

同时我们还可以得到关于该整数规划问题下界的序列：

若对于某个使得如下表达式成⽴：，则可得：

定理1.1 ：若，则表明，进⼀步可得整数规划问题P的最优解为。

由此可得可⾏解离最优解的距离不超过。从上⾯的推导可以知道，如果我们有2个算法分别能够求出原整数规划问题的上界和下界，然后逐步逼近上下界，当上下界之间的距离⾜够接近的时候，我们就可以得到⼀个近似最优解。

从上⾯的分析我们可以看出我们需要分别寻整数规划问题IP的上界和下界，寻上界⾃然我们⾸先会相当对原整数规划问题做松弛，如下所⽰：

考虑整数规划问题P的线性松弛问题LP：

寻下界，我们⼀般会选择对原整数规划问题进⾏分解：

设原整数规划问题的可⾏域可以被分解为如下若⼲个集合的并

我们在每个⼩集合上有，

对于进⼀步可得

将上⾯两条结合起来松弛问题可以帮助我们得到上界，分解问题可以帮助对整数规划问题进⾏拆分，同时也可以帮助我们得到下界。把这两个思想结合在⼀起就构成了我们今天的主⾓：分⽀定界法。

v =∗max c x : x ∈S ⊆Z {T n }

v ∗≥v ˉ1≥v ˉ2≥v ˉ3...≥v ∗

≤v 1≤v 2≤≤v ∗

k −v ˉk ≤v k ϵ−v ˉk ϵ≤v ≤∗v ˉk

ϵ=0−v ˉk =v k 0v ˉk v ˉk ϵu =∗max c x : x ∈S ⊆R {T n }

S =S ∪1S ⋯∪2S M

S i z =k max c x : x ∈S ⊆Z {T k n }

k =1,...,M v =∗z ≥k max k z k

2 分⽀定界法如何实现节省计算量

以如下三个决策变量的整数规划问题为例：

上述问题总的可⾏域为我们将集合分为两部分和，依次类推

等，如下图所⽰可以构成⼀个树结构：

固然我们可以去遍历整个树上的每个节点就可以完成对整数规划问题的求解，但是这样的⽅法实际上是不可⾏的，因为其计算时间会随着问题规模急剧增⼤，这⼀点在前⾯我们已经讲过了。所以我们需要通过定出问题的上下界来⽐较“智能”的给出哪些节点肯定不是最优解，那么就不⽤搜索这些节点了以便于节省时间。

⾸先我们需要如下两个定理使得我们的分⽀定界法变得⽐较“智能”

定理2.1：（1）若LP不可⾏，则IP也不可⾏。（2）设是LP的最优解，同时有，则也是IP的最优解。

证明：(1)采⽤反证法直接可以证明。(2) 由于既是IP问题的下界，⼜是IP问题的上界，所以其必为IP问题的最优解。

定理2.2：设原整数规划问题的可⾏域可以被分解

我们在每个⼩集合上有，

对于，设为的⼀个上界，为的⼀个下界。由此可得，是原整数规划问题最优解的上界，是原整数规划问题的下界。max x +1x +2x 3

s .t . x ,x ,x ∈1230,1{}

S =0,1{}3S S =0x ∈S :x =0{1}S =1x ∈S :x =1{1}S ,S ,...

0001x ∗x ∈∗Z n x ∗x ∗S =S ∪1S ⋯∪2S M

S i z =k max c x : x ∈S ⊆Z {T k n }

k =1,...,M z ˉk z k z k z k =

苗颖z ˉk max z ˉk v ∗=z k max z k

情况1：Pruned by optimality

如上图所⽰，图中节点旁边的两个数字分别表⽰该节点处的上界和下界。根据定理2.2可以对进⾏更新，即，同时也可以对进⾏更新，即。我们观察到节点处的上界和下界都是20，根据定理1.1可知此时已经求解到了问题的最优解了，那么就⽆需对的⼦节点进⼀步搜索了。

情况2：Pruned by bound

如上图所⽰，同样的根据定理2.2可以对进⾏更新，即，同时也可以对进⾏更新，即。我们观察节点可知的上界是20，⽽，也就是说最优解⼀定是⼤于等于21的，⽽节点的⼦问题最⼤只能取到20，由此可知最优解⼀定不在处，那么就⽆需对的⼦节点进⼀步搜索了。

情况3：No pruning possible

如上图所⽰，同样的根据定理2.2可以对进⾏更新，，同时也可以对进⾏更新，即，观察和我们发现不能通过情况1和情况2来跳过节点，也就是说此时我们还得进⼀步去搜索和。情况 4： Pruned by infeasibility

infeasibility 的情况最简单，就是解到某个节点发现该节点的问题是⼀个不可⾏问题，那么必然这个节点之下的⼦问题也都是不可⾏的，那么该节点就不⽤在搜索下去了。

⾄此，我们总结⼀下在树搜索过程中会有四种情况发⽣：

情况1：Pruned by optimality，这种情况是⾮常幸运的⼀下⼦就解到的⼦问题的最优解。

情况2：Pruned by bound，这种情况可以通过最优解的上下界来排除掉⼀部分不可能是最优解的节点。

z ˉ=z ˉ=赵本山实话实说

k max z ˉk max 20,25={}25z =z =k max z k max 15,20={}20S 1S 1S 1z ˉ=

z ˉ=k max z ˉk max 20,26={}26z =z =k max z k max 18,21={}21S 1S 1=z 21S 1S 1S 1z ˉ=z ˉ=k max z ˉk max 24,37={}37z =z =k max z k max 13,−∞={}13S 1S 2S 1S 2

情况3：No pruning possible，这种情况实际上就是最差的情况。

情况4：Pruned by infeasibility ，这种情况因为不可⾏的原因同样可以删除掉⼀部分节点不⽤搜索。了解了分⽀定界法的四种情况，接下来我们给出分⽀定界法的算法总流程。

3 分⽀定界法流程

分⽀定界算法的流程如下所⽰：

水力压裂

zˉz

从图中可以看到初始化阶段我们需要给定输出的全局的上界和下界，如果能有⼀些启发式的⽅法获得稍微好点的上下界作为初始解导⼊那是最好的不过的了。如果没有的话可以先设置为正负⽆穷⼤。

接着进⼊到主循环中，我们通过求解整数规划的连续松弛问题（线性规划）来得到该⼦问题的上界。在主循环中，剩余的操作其实就是依据我们上⼀节所讲的四种情况来分别进⾏，即 Pruned by optimality，Pruned by bound，No pruning possible, Pruned by

infeasibility，对于情况1,2,4我们需要提前跳出循环完成剪枝的过程。如果情况1,2,4都不满⾜的话，就会⼀直运⾏到最后⼀步 return two subproblems 因为没有剪枝，所以需要把两个⼦节点都添加进来。

4 分⽀定界法求解0-1线性整数规划问题代码实现

依据上述算法流程，我们在Python中实现了⼀个基本的分⽀定界算法。注意的是我们的代码针对是0-1线性整数规划问题，并且⽬标函数是极⼤化的情况。同时整数规划模型的建⽴要依赖Gurobi，所以想要运⾏代码需要安装Gurobi 以便于代码结果展⽰。

接下来我们对代码的主⼲部分做⼀个简要介绍，⾸先我们通过Gurobi⽣成我们要求解的整数规划问题的模型作为我们分⽀定界法的输⼊。这部分是Gurobi的指令（不熟悉的Gurobi的同学需要先了解⼀下

Gurobi），如下所⽰

准备完输⼊之后，如下代码实际上就对应我们上⼀节所述的分⽀定界算法的主⼲流程。可以看到 Pruned by optimality，Pruned by bound, Pruned by infeasibility 三种情况会跳出本次循环，⽽如果三种情况都不满⾜则就是情况3：No pruning possible，这时候会在本次循环的最后⽣成两个⼦问题（child_node1,child_node2）model = gp .Model ("mip1")x = model .addVar (vtype =GRB .BINARY , name ="x")y = model .addVar (vtype =GRB .BINARY , name ="y")z = model .addVar (vtype =GRB .BINARY , name ="z")model .setObjective (x + y + 2 * z , GRB .MAXIMIZE )model .addConstr (x + 2 * y + 3 * z <= 4, "c0")model .addConstr (x + y >= 1, "c1")model .addConstr (x + z == 2, "c2")model .update ()model .write ("model_integer.lp")

11upper_bound , lower_bound = float ('inf'), 0model_relax = model .relax ()root_node = Node (model = model_relax , upper_bound = upper_bound , lower_bound = lower_bound , candidate_vars = [i for i in range (model .NumVars candidate_node = [root_node ]current_optimum = None while candidate_node : node , candidate_node = choice_node (candidate_node ) if node .upper_bound <= lower_bound : print ("prune by bound") continue model_status = node .optimize (heuristic_solve ) if model_status == 'infeasible': print ("prune by infeasiblity") continue node .update_upper_bound () if node .upper_bound <= lower_bound : print ("prune by bound") continue if node .is_integer (): node .update_lower_bound () if node .lower_bound > lower_bound : lower_bound = node .lower_bound current_optim

um = node .solution continue if node .is_child_problem (): child_node1, child_node2 = node .get_child_problem () candidate_node .append (child_node1) candidate_node .append (child_node2)1

商业部通知4

Pae6

82008扣篮大赛