优化 | 精确算法之分支定界介绍和实现（附Python代码）

JoshWindsor · 发表于 2022-9-14 09:14

作者：
周鹏翔，清华大学，清华-伯克利深圳学院（博士在读）
刘兴禄，清华大学，清华-伯克利深圳学院（博士在读）
编辑：张瑞三，四川大学，硕士在读，邮箱：zrssum3@stu.scu.edu.cn 知乎ID：MunSum3
<hr/>分支定界算法

我们定义优化问题为 P=(X,f) ,其中， X 为搜索空间-可行域， f: X \rightarrow R 为目标函数。我们的目标是找到 x^{*} \in \arg \min {x \in X} f(x) 。为了求解 P ,分支定界算法迭代时构建了一棵包含子问题的搜索树 T ，即搜索空间的子集。此外，一个可行解 \hat x \in X (称为incumbent solution)被存储。在每一次迭代中，算法从未探索的子问题列表 L 中选择一个新的子问题 S \in X 进行探索;如果一个解 \hat x \in S ，我们有 f(\hat x^{&#39;})<f(\hat x) ，我们更新 incumbent solution。另一方面，如果能证明在S中没有一个解有比 \hat x 好(即 x∈S,f(x)≥f(\hat x) ），则子问题被剪枝。否则，子问题是通过将 S 划分成一个穷举的(但不一定是互斥的)子问题集 S{1},S_{2}，…，S_{r} ，然后将其插入到搜索树 T 中，一旦没有未探索的子问题存在，则返回现有的最优解。用于评估分支定界算法表现的因素主要有求解算法的运行时间以及被探索完毕的节点数量。

图1. 分支定界算法[1]

分支定界算法的策略

搜索策略（如何选择下一个被探索的节点）
分枝策略（影响子节点的数量和子问题如何被分解）
剪枝策略（决定节点是否被探索完毕）
初始解的选择（可使用启发式算法得到）
并行计算（需要关注不同处理器间的信息交换，包括bound/dominance/pruning rule）我们将分支定界算法分为两个阶段，搜索阶段和验证阶段。其中，搜索阶段旨在找到当前分支的最优节点（incumbent solution），涉及搜索策略和分支策略，如切平面作为剪枝策略可用于搜索阶段，用于鉴别可行解；而验证阶段旨在验证其他分支被探索完毕（如被剪枝，找到当前节点的最优解等），涉及分支策略和剪枝策略。

图2. 分支定界算法的策略[1]

搜索策略

下图描述的是不同搜索策略下的子问题探索顺序。虚线子问题是最优的，节点内部的数字是子问题的下界，节点外部的数字表示探索顺序。注意，需要计算子问题的下界，再将子问题插入到未探索的子问题列表。
(a) 深度优先搜索（Depth-first search）
优点： - 占用较小的内存（搜索策略只存储从 T 的根节点到当前子问题的路径;在这条路径上的每个子问题上存储上一个被探索的子问题的索引）  - 可重复使用父节点的信息，如optimal basis, LU factorization, 方法称为warm starting，hot starting。
缺点：  - trashing: 单一分支约束的存在会导致不可行性，但是在不可行性被检测之前，算法必须探索更多的子问题  - unbounded depth: 如果一些最优解靠近根节点，但在 T 中存在长路径使得求解该路径上的子问题一直得不到最优解
改进方法：

iterative deepening DFS: 设置探索的路径深度上限
interleaved depth-first search: 按顺序从每个不同的DFS路径中选择一个子问题进行探索
depth-first search with complete branching: 计算出所有子问题的下界（线性松弛的目标函数值），选择具有具有最低下界的子问题进行探索，但是会占用内存，因为当生成子问题必须得到子问题的child subproblems。

（b）广度优先探索（Breadth-first search）
优点：  - BrFS在探索任何更深层的子问题之前，先探索与根保持固定距离的所有子问题。BrFS策略的优点是总能找到最接近树根的最优解。
缺点：  - 由于最优解常位于更大的深度，BrFS通常不能利用bound剪枝
（c）最佳优先搜索(Best-first search)
该策略利用了最佳函数（measure of best)，计算一个值 μ(S) 对于每个未探索的子问题，选择 μ(S) 最小的分支作为下一个问题来探索。比如可以使用线性松弛求得的lower bound。但是用了过多的时间求解具有相同μ(S) 的子问题，可能长时间不能求得更优解。
（d）循环最佳优先搜索(Cyclic best-first search)
CBFS结合BFS和DFS，将未开发的子问题（BFS的堆结构存储）划分为若干个contour。当一个新的子问题被识别时，它将根据一组规则（例如，子问题在树中所处的深度等）被插入其中一个contour中。为了探索搜索空间，CBFS策略反复迭代所有非空contour，选择最佳子问题（根据最佳函数，measure of best  μ ) 进行探索。例如，如果contour是按深度分类，那么CBFS将在根节点探索最佳子问题，然后是深度1，依此类推；当到达search tree的底部时，它将从深度0开始重复这个过程。

图3. 分支定界算法的搜索策略[1]

分枝策略

(a) binary branching

二元分支策略专注于将一个子问题细分为两个相互排斥的小子问题

(b) wide branching
从多个二元变量的组合中选取一个元素，得到新的子问题，我们常常会使用Special ordered sets, SOS1(一组有序集合，顶多有1个非0值)，SOS2（一组有序集合，顶多有2个非0值）等，进行branch。
优点在于能减小search tree的规模，但是不一定能生成互斥的分支，同一个子问题有可能被探索多次（不同探索路径），而且一个子问题下再一次branch产生的分支过多，我们常常会限制子问题产生的分支的数量，该方法又被称为 delayed branching。

图4. Binary branching 和 wide branching对比[1]

(c) 基于整数的分支策略

most franctional(most infeasible):它选择分式部分最接近0.5的变量作为分支变量。least franctional的分支策略选择分式部分最远离0.5的变量作为分支变量，基本不被使用。
Pseudocost branching: 基于过去求解的search tree上的子问题的经验，预测候选分支变量对目标函数值影响的大小，选择对目标函数影响最大的候选分支变量。
Strong branching：求解候选分支变量的子问题的LP松弛目标值，然后选择引起目标变化最大的变量进行分支。
Hybrid branching：刚开始求解时，求解子问题的经验很少，我们使用strong branching，在求解的子问题的经验积累到一定程度时，我们选择Pseudocost branching进行分支。刚开始使用strong branching时，注意考虑未被探索过的变量作为分支变量，否则在Pseudocost branching可能会缺失某些候选分支变量的对目标函数影响的经验值。
如果候选分支变量导致的发生变化的变量数最多（或者说对该候选分支变量进行分支会导致很多约束不能被满足），则选择该候选变量进行分支。

剪枝策略

dominance rule: 如果存在 S_{1} 中的解，使得其比 S_{2} 中的任何一个解都要好，则 S_{1} 优于 S_{2} ，则将 S_{2} 对应的子问题进行剪枝。广度优先可能存在很长时间都找不到dominating 子问题。
添加切平面的约束进行剪枝，比如Gomory cuts/bender cuts等。(bender decomposition)
列生成: 将切割平面添加到对偶优化问题中，以改进计算出的下界; （branch and price）

初始解的选择

使用启发式算法选择初始可行解。
案例分析

\\\max_{x_{0},x_{1}}100*x_{0}+150*x_{1}
subject to:
\\ \begin{array}{rc} 2*x_{0}+x_{1} \leq &10 \\ 3*x_{0}+6*x_{1} \leq &40 \end{array}

暂不考虑分支策略: 对分支变量向下取整，作为RHS
搜索策略：使用深度优先搜索
剪枝逻辑：

根据最优性剪枝，子问题得到整数解，子问题的线性松弛的解是该子问题的最优解
根据bound剪枝，线性松弛的子问题所求的目标函数值小于所有叶子结点的下界
根据是否可行剪枝，如果子问题不可行，则剪枝

代码逻辑描述

1.求解线性松弛的原问题，判断是否可行

a.根据是否可行剪枝，子问题不可行
b. 如果可行，原问题得到整数解，线性松弛后的原问题的解是该问题的最优解，终止算法。
c. 如果可行，线性松弛后的原问题没有得到整数解，则线性松弛后的原问题的目标函数值作为当前根节点的上界，选择原问题的可行解对应的目标函数值作为当前根节点的下界。根据分支策略进行分支得到子问题，并添加至未被探索的问题集中。

2.当未被探索的问题集不为空，且上下界的gap大于阈值，则根据搜索策略选择子问题进行探索

a.子问题不可行，剪枝
b.子问题可行，子问题得到整数解，子问题的线性松弛的解是该子问题的最优解，剪枝;线性松弛的子问题得到整数解，且线性松弛的子问题所求的目标函数值大于所有叶子结点的上界,算法终止
c.子问题可行，子问题没有得到整数解当子问题的上界不超过原问题当前所求得的下界，剪枝。否则将线性松弛后的子问题的目标函数值作为当前根节点的上界，选择子问题的可行解对应的目标函数值作为当前节点的下界。根据分支策略进行分支得到子问题，并添加至未被探索的问题集中。

3.算法的终止条件当未被探索的问题集不为空；如果上界等于下界，或者上界-下界的gap很小，则算法终止。
Python代码

注：代码框架参考小编们还未出版的书《运筹优化常用模型、算法及案例实战——Python+Java实现》

《运筹优化常用模型、算法及案例实战——Python+Java实现》源代码

&#34;&#34;&#34;
@author: Pengxiang Zhou
&#34;&#34;&#34;
from gurobipy import *
import copy
import numpy as np
import matplotlib.pyplot as plt
import pandas as pd

############## define initial linear relaxation problem of primal problem ##############
initial_LP = Model(&#39;initial LP&#39;)
x = {}
for i in range(2):
x = initial_LP.addVar(lb=0,ub=GRB.INFINITY, vtype=GRB.CONTINUOUS,name = &#39;x_&#39;+str(i))
initial_LP.setObjective(100*x[0]+150*x[1],GRB.MAXIMIZE)
initial_LP.addConstr(2*x[0]+x[1]<=10)
initial_LP.addConstr(3*x[0]+6*x[1]<=40)
initial_LP.optimize()
for var in initial_LP.getVars():
print(var.Varname,&#39;=&#39;,var.x)
initial_LP.status # 2: get the optimal value; 4: infeasible or unbounded; 5: unbounded

class Node:
def __init__(self):
      self.model = None
      self.x_sol = {} #solution of sub-problem
      self.x_int_sol = {} #round integer of solution
      self.local_LB = 0  #local bound of node, sub-problem
      self.local_UB = np.inf
      self.is_integer = False #is integr solution
      self.branch_var_list = []  #store branch variable

# deep copy the whole node
def deepcopy(node):
      new_node = Node()
      new_node.local_LB = 0
      new_node.local_UB = np.inf
      new_node.x_sol = copy.deepcopy(node.x_sol) #solution of sub-problem
      new_node.x_int_sol = copy.deepcopy(node.x_int_sol) #round integer of solution
      new_node.branch_var_list = [] # do not copy, or that always use the same branch_var_list in sub-problem
      # deepcopy, or that the subproblem add all the new constraints sub-problem->infeasible
      new_node.model = node.model.copy()  # gurobi can deepcopy model
      new_node.is_integer = node.is_integer

      return new_node

def branch_and_bound(initial_LP):
############## store UB，LB and solution ##############
trend_UB = []
trend_LB =[]
initial_LP.optimize()
global_LB = 0
global_UB = initial_LP.ObjVal
eps = 1e-3
incumbent_node = None
Gap = np.inf
############## branch and bound begins ##############
Queue = []
#create root node
node = Node()
node.local_LB = 0
# trend_LB.append(node.local_LB)
node.local_UB = global_UB #root node
# trend_UB.append(global_UB)
node.model = initial_LP.copy() # gurobi can deepcopy model
node.model.setParam(&#39;OutputFlag&#39;,0)
Queue.append(node)
#cycle
cnt = 0
while(len(Queue)>0 and global_UB - global_LB >eps):
      cnt += 1
      #Use depth-first search, last in, first out
      #pop: removes the last element element from a list and returns the value of that element
      current_node = Queue.pop()
      #solve the current node
      current_node.model.optimize()
      Solution_status = current_node.model.status

      #check the current solution(is_Integer, is_pruned)
      Is_Integer = True
      Is_pruned = False

      ############## check whether the sub-problem is feasible ##############
      if(Solution_status == 2): #2: get the optimal value
         ############## check whether the current solution is integer##############
         for var in current_node.model.getVars():
            current_node.x_sol[var.VarName] = var.x
            print(var.VarName,&#39;=&#39;,var.x)
            # round the fractional solution, round down
            current_node.x_int_sol[var.VarName] = (int)(var.x)
            if (abs( (int)(var.x)-var.x)>= eps):
                  Is_Integer = False # judge whether the solution is integer or not
                  current_node.branch_var_list.append(var.VarName)
         #Update LB and UB
         ############## is integer, incumbent ##############
         if(Is_Integer == True):
            current_node.local_LB = current_node.model.ObjVal
            current_node.local_UB = current_node.model.ObjVal
            current_node.is_integer = True
            if(current_node.local_LB > global_LB):
                  global_LB = current_node.local_LB
                  incumbent_node = Node.deepcopy(current_node)

         else:
         ############## is not integer, then branch ##############
            Is_Integer = False
            current_node.local_UB = current_node.model.ObjVal
            if current_node.local_UB < global_LB:
                  Is_pruned = True
                  current_node.is_integer = False
            else:
                  Is_pruned = False
                  current_node.is_integer = False
                  for var_name in current_node.x_int_sol.keys():
                     var = current_node.model.getVarByName(var_name)
                     current_node.local_LB += current_node.x_int_sol[var_name]*var.Obj
                     # round down the solution of parent node，calculate the objective value for LB
                     # Notice that round down the solution can still be feasible for our example
                  ############### update LB ##############
                  if (current_node.local_LB > global_LB):
                     global_LB = current_node.local_LB
                     incumbent_node = Node.deepcopy(current_node)

                  ############## branch ##############
                  branch_var_name = current_node.branch_var_list[0]
                  left_var_bound = (int)(current_node.x_sol[branch_var_name])
                  right_var_bound = (int)(current_node.x_sol[branch_var_name])+1

                  #current two child nodes
                  left_node = Node.deepcopy(current_node)
                  right_node = Node.deepcopy(current_node)

                  #add branching constraints
                  temp_var = left_node.model.getVarByName(branch_var_name)
                  left_node.model.addConstr(temp_var <= left_var_bound,name = &#39;branch_left_&#39;+str(cnt))
                  left_node.model.update() # lazy updation

                  temp_var = right_node.model.getVarByName(branch_var_name)
                  right_node.model.addConstr(temp_var >= right_var_bound,name = &#39;branch_right_&#39;+str(cnt))
                  left_node.model.update()

                  Queue.append(left_node)
                  Queue.append(right_node)

      ############## prune by infeasibility ##############
      elif(Solution_status !=2):
         Is_Integer = False
         Is_pruned = True

      ############## update Upper bound ##############
      temp_global_UB = 0
      for node in Queue:
         node.model.optimize()
         if(node.model.status == 2):
            if(node.model.ObjVal >=temp_global_UB):
                  temp_global_UB = node.model.ObjVal
      global_UB = temp_global_UB
      Gap = 100*(global_UB - global_LB)/global_LB
      print(&#39;Gap:&#39;,Gap,&#39; %&#39;)
      trend_UB.append(global_UB)
      trend_LB.append(global_LB)

print(&#39; ---------------------------------- &#39;)
print(&#39; Optimal solution found &#39;)
print(&#39; ---------------------------------- &#39;)
print(&#39;Solution:&#39;, incumbent_node.x_int_sol)
print(&#39;Obj:&#39;, global_LB)
plt.figure()
plt.plot( trend_LB , label=&#34;LB&#34;)
plt.plot( trend_UB, label=&#34;UB&#34;)
plt.xlabel(&#39;Iteration&#39;)
plt.ylabel(&#39;Bound Update&#39;)
plt.title(&#34;Bound Update During Branch and Bound Procedure&#34;)
plt.legend()
plt.show()
return incumbent_node, Gap
############## Call branch and bound function ##############
#Notice that we use the linear relaxation of primal model as input parameter
incumbent_node, Gap = branch_and_bound(initial_LP)分支定界的结果

求解结果

参考文献：

[1] Morrison D R, Jacobson S H, Sauppe J J, et al. Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning[J]. Discrete Optimization, 2016, 19: 79-102.
[2] 刘兴禄，熊望祺，臧永森，段宏达，曾文佳，陈伟坚. 2021. 运筹优化常用模型、算法及案例实战——Python+Java实现. 待出版.
<hr/>欢迎关注我们的微信公众号 运小筹
运小筹公众号致力于分享运筹优化(LP、MIP、NLP、随机规划、鲁棒优化)、凸优化、强化学习等研究领域的内容以及涉及到的算法的代码实现。编程语言和工具包括Java、Python、Matlab、CPLEX、Gurobi、SCIP 等。欢迎广大同行投稿！欢迎大家关注我们的公众号“运小筹”以及粉丝群！
可以私信编辑 MunSum3(知乎id) 拉入读者群
Notice 1

【运小筹】于去年建立了【OR领域英文期刊论文写作帮帮群】，旨在分享OR领域期刊论文的好的表达，用法，以及写作经验和心得。
之前一直是内部交流，现开放加群。
对此有浓厚兴趣，强烈意愿，并承诺愿意分享，一起学习进步的小伙伴，想进群的，可以加
微信：Ssum3_Klaus
小编通过之后可以拉大家入群一起学习
强调：帮帮群旨在相互分享、相互提升写作能力，分享意愿不高的同学建议添加我们读者群讨论问题。

读者群分享

Notice 2

目前我们运小筹微信公众号已经有接近10000关注了，为了纪念这个里程碑，我们决定奖励
1. 第10000位粉丝
2. 截止2022年6月5日23:59分，【阅读最多】【分享最多】【赞赏最多】【留言最多】四个项目中排名前五的粉丝
将直接获得之前的全部月刊

公众号

小编整理的资料1

小编整理的资料2

Notice 3

预告:等到1w粉后，将会开放读者核心群，入群对象为较为活跃的粉丝群体，活跃指标从：公众号推文分享次数、群内分享互助次数等方面考察。在核心群的成员可以享受到一些额外的福利，例如：一些小编整理的资料（如Notice2的月刊以及下图，这只是冰山一角）等
友情提示：为了避免进入核心群就不再分享、讨论，核心群或定期重新洗牌

小编整理的资料3

<hr/>往期推文合集

第90篇：优化 | 二部图最大匹配问题的精确算法详解(HK算法和匈牙利算法)：一份让您满意的【理论介绍+代码实现】学习笔记
第89篇：优化算法 | Benders Decomposition: 一份让你满意的【入门-编程实战-深入理解】的学习笔记
第88篇：优化 | 史上最【皮】数学题求解的新尝试：一种求解器的视角 (Python调用Gurobi实现)
第87篇：优化 | 寻找新的建模视角——从直观解释对偶问题入手：以Cutting Stock Problem的对偶问题为例
第86篇：ORers‘ Bling Chat【03】 | 【高光聊天记录集锦】：运小筹读者群里那些热烈的讨论
第85篇：非线性优化 | 非线性问题线性化以及求解的详细案例及Python+Gurobi求解
第84篇：ORers&#39; Bling Chat | 【高光聊天记录集锦-02】：运小筹读者群里那些热烈的讨论
第83篇：Machine-Learning–Based Column Selection for Column Generation
第82篇：最新！205页运小筹优化理论学习笔记发布(2021年9月--2022年3月)！
第81篇：【鲁棒优化】| 补充证明:为什么最优解一定满足取值等于绝对值(论文笔记：The Price of Robustness)
第80篇：【鲁棒优化】| 论文笔记：The Price of Robustness - 列不确定性模型部分的推导和一些思考
第79篇：ORers&#39; Bling Chat | 【高光聊天记录集锦-01】：运小筹读者群里那些热烈的讨论
第78篇：优化| 手把手教你学会杉数求解器(COPT)的安装、配置与测试
第77篇：【教学视频】优化 | 线性化(2)：连续变量 * 0-1变量的线性化
第76篇：【教学视频】优化 | 线性化：两个0-1变量相乘的线性化
第75篇：强化学习实战 | DQN和Double DQN保姆级教程：以Cart-Pole为例
第74篇：强化学习| 概念梳理：强化学习、马尔科夫决策过程与动态规划
第73篇：强化学习实战 | Q-learning求解最短路(SPP)问题
第72篇：鲁棒优化 | 以Coding入门鲁棒优化：以一个例子引入（二）
第71篇：鲁棒优化|基于ROME编程入门鲁棒优化：以一个例子引入(一)
第70篇：优化|含分式的非线性规划求解: 基于Outer Approximation的Branch-and-cut 算法及其Java实现
第69篇：科研工具 | 手把手教你玩转文献管理神器：Endnote
第68篇：相约深圳 | 2022 INFORMS 服务科学国际会议·征稿通知
第67篇：鲁棒优化｜利用rome求解鲁棒优化简单案例：以CVaR不确定性集为例
第66篇：机器学习 | 交通流特征工程小技巧和思考
第65篇：最新！145页运小筹优化理论学习笔记发布(2021年4月--9月)！
第64篇：优化 | 手把手教你用Python调用SCIP求解最优化模型
第63篇：优化 | 随机规划案例：The value of the stochastic solution
第62篇：工具 | draw.io: 科研流程示意图必备大杀器
第61篇：优化 | 开源求解器SCIP的安装与入门教程（Windows+Python）
第60篇：优化|Gurobi处理非线性目标函数和约束的详细案例
第59篇：让出租车更“懂”您的出行
第58篇：测试算例下载：《运筹优化常用模型、算法及案例实战：代码手册》
第57篇：鲁棒优化|分布式鲁棒优化转化为SOCP案例及代码实现(Python+RSOME)
第56篇：鲁棒优化 | 分布式鲁棒优化简单案例及实战(RSOME+Gurobi)
第55篇：【尾款+发货】|【代码手册】《运筹优化常用模型、算法及案例实战：Python+Java
第54篇：深度强化学习之：PPO训练红白机1942
第53篇：简单装配线平衡问题
第52篇：【视频讲解】CPLEX的OPL语言：可视化的优化模型求解解决方案
第51篇：算法 | 基于英雄联盟寻路背景的A星算法及python实现
第50篇：【转发】清华大学深圳国际研究生院2021年物流工程与管理项目优秀大学生夏令营报名通知
第49篇：优化 | 精确算法之分支定界介绍和实现（附Python代码）
第48篇：【顶刊论文速递】综述：服务科学视角下的金融科技
第47篇：【重新发布】|《运筹优化常用模型、算法及案例实战：Python+Java实现》【代码手册】开始预购啦！！！
第46篇：智慧交通可视化：手把手教你用Python做出行数据可视化-osmnx 包入门教程
第45篇：优化 | Pick and delivery problem的介绍与建模实现（二）
第44篇：推一个知乎学弱猹的公众号
第43篇：元启发式算法 | 遗传算法(GA)解决TSP问题(Python实现)
第42篇：优化|视频详解Python调用Gurobi的应用案例：TSP
第41篇：最新！213页运小筹优化理论系列笔记发布！
第40篇：运小筹第四期月刊发布！
第39篇：开源交通仿真平台SimMobility的安装教程
第38篇：浅谈 | P问题、NP问题、NPC问题、NP-Hard问题
第37篇：一份掏心掏肺的信息素养笔记分享
第36篇：强化学习｜Q-learning (王者荣耀视角)
第35篇：优化｜高级建模方法（Gurobi）：线性化表达小技巧
第34篇：深度强化学习介绍 | Deep Q Network——理论与代码实现
第33篇：优化 | 列生成算法及Java调用cplex实现
第32篇：优化 | Pick and delivery problem的简介与建模实现（一）
第31篇：最新！运小筹月刊-1月份发布！
第30篇：“Learn to Improve”（L2I）：ICLR文章分享 | 运用RL解决VRP问题
第29篇：线性规划求解小程序 | 基于Python 的Cplex 求解器图形化界面
第28篇：运筹学与管理科学TOP期刊揭秘 —TR系列
第27篇：Julia安装与配置Jupyter Notebook
第26篇：期刊征文| IEEE TRANSACTIONS应对COVID-19的特刊征文消息速递
第25篇：两阶段随机规划(Two-stage Stochastic Programming)：一个详细的例子
第24篇：最新！运小筹月刊-12月份发布！
第23篇：Python调用Gurobi：Assignment Problem简单案例
第22篇：初识随机规划：一个小小例子
第21篇：机器学习运用到VRP的若干小知识
第20篇：运筹学与管理科学TOP期刊揭秘 —Service Science
第19篇：手把手教你用Python实现Dijkstra算法（伪代码+Python实现）
第18篇：运筹学与管理科学大揭秘—TOP期刊主编及研究方向一览
第17篇：优化 | 手把手教你用Python实现动态规划Labeling算法求解SPPRC问题
第16篇：代码 | 运小筹GitHub项目上线啦，快来标星收藏吧！！
第15篇：最新！运小筹月刊首次发布！
第14篇：优化| 手把手教你用Python实现Dijkstra算法（附Python代码和可视化）
第13篇：优化|手把手教你用Python调用Gurobi求解最短路问题
第12篇：优化| 手把手教你用Java实现单纯形法
第11篇：优化| 手把手教你用Python调用Gurobi求解VRPTW
第10篇：优化 | 两阶段启发式算法求解带时间窗车辆路径问题（附Java代码）
第9篇：Java调用cplex求解运输问题
第8篇：优化 | 如何优雅地写出大规模线性规划的对偶
第7篇：优化 | TSP中两种不同消除子环路的方法及Callback实现（Python调用Gurobi求解）
第6篇：元启发式算法 | 禁忌搜索(Tabu Search)解决TSP问题(Python代码实现)
第5篇：论文代码复现 | 无人机与卡车联合配送(Python+Gurobi)
第4篇：优化|Shortest Path Problem及其对偶问题的一些探讨(附Python调用Gurobi实现)
第3篇：可视化|Python+OpenStreetMap的交通数据可视化(二)：OpenStreetMap+Python画城市交通路网图
第2篇：优化|最速下降法：详细案例+Python实现
第1篇：Python+networkX+OpenStreetMap实现交通数据可视化(一)：用OpenStreetMap下载地图数据

<hr/>作者：
周鹏翔，清华大学，清华-伯克利深圳学院（博士在读）
刘兴禄，清华大学，清华-伯克利深圳学院（博士在读）
编辑：张瑞三，四川大学，硕士在读，邮箱：zrssum3@stu.scu.edu.cn

		自动登录	找回密码
密码			立即注册

优化 | 精确算法之分支定界介绍和实现（附Python代码）

本帖子中包含更多资源