分⽀定界法python实现_⼲货10分钟搞懂branchandbound（分
⽀定界）算法的。。。
Outline
前⾔
Example-1
Example-2
运⾏说明
00 前⾔
universal robots前⾯⼀篇⽂章我们讲了branch and bound算法的相关概念。可能⼤家对精确算法实现的印象⼤概只有⼀个，调⽤求解器进⾏求解，当然这只是⼀部分。其实精确算法也好，启发式算法也好，都是独⽴的算法，可以不依赖求解器进⾏代码实现的，只要过程符合算法框架即可。
只不过平常看到的⼤部分是精确算法在各种整数规划模型上的应⽤，为此难免脱离不了cplex等求解器。
这⾥简单提⼀下。今天给⼤家带来的依然是branch and bound算法在整数规划中的应⽤的代码实现，所以还是会⽤到部分求解器的。
注：本⽂代码下载请关注公众号【程序猿声】，后台回复【bbcode】，不包括【】即可下载！
01 Example-1
⾸先来看第⼀个代码实例，该代码求解的是整数优化的模型，关于branch and bound求解整数规划的具体原理就不再概述了，和上⼀篇⽂章差不多但是有所区别。代码⽂件层次如下：
其中branch and bound算法主要部分在BnB_Guide.java这个⽂件。ExampleProblem.java内置了三个整数规划模型的实例。调⽤的是scpsolver这个求解器的wrapper，实际调⽤的还是lpsolver这个求解器⽤以求解线性松弛模型。下⾯着重讲讲BnB_Guide.java这个⽂件。
public BnB_Guide(int demoProblem){
example = new ExampleProblem(demoProblem);
LinearProgram lp = new LinearProgram();
lp = Problem().getLP();
solver = wDefault();
double[] solution = solver.solve(lp); // Solution of the initial relaxation problem
int maxElement = getMax(solution); // Index of the maximum non-integer decision variable's value
if(maxElement == -1 ) // We only got integers as values, hence we have an optimal solution
2012高考时间verifyOptimalSolution(solution,lp);
el
this.solveChildProblems(lp, solution, maxElement); // create 2 child problems and solve them
printSolution();
}
该过程是算法主调⽤过程：
⾸先变量lp保存了整数规划的松弛问题。
yed
在调⽤求解器求解松弛模型以后，判断是否所有决策变量都是整数了，如果是，已经找到最优解。
唯美的英文句子如果不是，根据找出最⼤的⾮整数的决策变量，对该变量进⾏分⽀，solveChildProblems。
接着是分⽀⼦问题的求解过程solveChildProblems如下：
public void solveChildProblems(LinearProgram lp, double[] solution ,int maxElement){
archDepth++;
LinearProgram lp1 = new LinearProgram(lp);
LinearProgram lp2 = new LinearProgram(lp);
String constr_name = "c" + (lp.getConstraints().size() + 1); // Name of the new constraint
double[] constr_val = new Dimension()]; // The variables' values of the new constraint
for(int i=0;i
学英语报if(i == maxElement )
constr_val[i] = 1.0;
el
constr_val[i] = 0;
}
//Create 2 child problems: 1. x >= ceil(value), 2. x <= floor(value)
lp1.addConstraint(new LinearBiggerThanEqualsConstraint(constr_val, il(solution[maxElement]), constr_name));
lp2.addConstraint(new LinearSmallerThanEqualsConstraint(constr_val, Math.floor(solution[maxElement]), constr_name)); solveProblem(lp1);
solveProblem(lp2);
}
具体的分⽀过程如下：
⾸先新建两个线性的⼦问题。
两个⼦问题分别添加需要分⽀的决策变量新约束：1. x >= ceil(value), 2. x <= floor(value)。
⼀切准备就绪以后，调⽤solveProblem求解两个⼦问题。
⽽solveProblem的实现代码如下：
private void solveProblem(LinearProgram lp) {
double[] sol = solver.solve(lp);
LPSolution lpsol = new LPSolution(sol, lp);
double objVal = ObjectiveValue();
if(lp.isMinProblem()) {
if(objVal > MinimizeProblemOptimalSolution) {
System.out.println("cut >>> objVal = "+ objVal);
return;
}
}
el {
if(objVal < MaximizeProblemOptimalSolution) {
System.out.println("cut >>> objVal = "+ objVal);
return;
}
}
System.out.println("non cut >>> objVal = "+ objVal);
int maxElement = Max(sol);
if(maxElement == -1 && lp.isFeasable(sol)){ //We found a solution
solutionFound = true;
verifyOptimalSolution(sol,lp);
}
el if(lp.isFeasable(sol) && !solutionFound) //Search for a solution in the child problems
this.solveChildProblems(lp, sol, maxElement);
}
该过程如下：
⾸先调⽤求解器求解传⼊的线性模型。
然后实⾏定界剪⽀，如果⼦问题的objVal⽐当前最优解还要差，则剪掉。
如果不剪，则判断是否所有决策变量都是整数以及解是否可⾏，如果是，找到新的解，更新当前最优解。
如果不是，根据找出最⼤的⾮整数的决策变量，对该变量再次进⾏分⽀，进⼊solveChildProblems。
从上⾯的逻辑过程可以看出，solveChildProblems和solveProblem两个之间相互调⽤，其实这是⼀种递归。该实现⽅式进⾏的就是BFS ⼴度优先搜索的⽅式遍历搜索树。
02 Example-2
再来看看第⼆个实例：
input是模型的输⼊，输⼊的是⼀个整数规划的模型。由于输⼊和建模过程有点繁琐，这⾥就不多讲了。挑⼀些重点讲讲具体是分⽀定界算法是怎么运⾏的就⾏。
⾸先该代码⽤了stack的作为数据结构，遍历搜索树的⽅式是DFS即深度优先搜索，我们来看BNBSearch.java这个⽂件：
public class BNBSearch {
Deque archStack = new ArrayDeque();
double bestVal = Double.MAX_VALUE;
archNode currentBest = new archNode();
IPInstance solveRel = new IPInstance();
Deque visited = new ArrayDeque();
public BNBSearch(IPInstance solveRel) {
this.solveRel = solveRel;
archNode rootNode = new archNode();
this.archStack.push(rootNode);
};
BNBSearch 这个类是branch and bound算法的主要过程，成员变量如下：
archStack ：构造和遍历⽣成树⽤的，栈结构。
bestVal：记录当前最优解的值，由于求的最⼩化问题，⼀开始设置为正⽆穷。
currentBest ：记录当前最优解。
solveRel ：整数规划模型。
damvisited ：记录此前⾛过的分⽀，避免重复。
然后在这⾥展开讲⼀下archNode就是构成搜索树的节点是怎么定义的：
public class archNode {
HashMap partialAssigned = new HashMap();
快递费 英文public archNode() {
super();
}
public archNode(archNode makeCopy) {
for (int test: makeCopy.partialAssigned.keySet()) {
this.partialAssigned.put(test, (test));
}
}
}
其实⾮常简单，partialAssigned 保存的是部分解的结构，就是⼀个HashMap，key保存的是决策变量，⽽value对应的是决策变量分⽀的取值(0-1)。举上节课讲过的例⼦：
⽐如：
节点1的partialAssigned == { {x3, 1} }。电子英文
节点2的partialAssigned == { {x3, 0} }。
节点3的partialAssigned == { {x3, 1}, {x2, 1} }。
节点4的partialAssigned == { {x3, 1}, {x2, 0} }。
节点7的partialAssigned == { {x3, 0}, {x1, 1}, {x2, 1}}。
……
想必各位已经明⽩得不能再明⽩了。
然后就可以开始BB过程了：
public int solveIP() throws IloException {
while (!this.archStack.isEmpty()) {
archNode branchNode = this.archStack.pop();
boolean isVisited = fal;
for (archNode tempNode: this.visited) {
if (branchNode.partialAssigned.equals(tempNode.partialAssigned)){ isVisited = true;
break;
}
韩语在线翻译发音
}
if (!isVisited) {
visited.add(new archNode(branchNode));
double bound = solveRel.solve(branchNode);
if (bound > bestVal || bound == 0) {
//System.out.println(archStack.size());
}
if (bound < bestVal && bound!=0) {
if (branchNode.partialAssigned.size() == solveRel.numTests) {
//分⽀到达低端，找到⼀个满⾜整数约束的可⾏解，设置为当前最优解。//System.out.println("YAY");
this.bestVal = bound;
this.currentBest = branchNode;
}
}
if (bound < bestVal && bound!=0) {
//如果还没到达低端，找⼀个变量进⾏分⽀。
if (branchNode.partialAssigned.size() != solveRel.numTests) {
int varToSplit = getSplitVariable(branchNode);
if (varToSplit != -1) {
archNode left = new archNode(branchNode);
archNode right = new archNode(branchNode);
代替英语left.partialAssigned.put(varToSplit, 0);
right.partialAssigned.put(varToSplit, 1);
this.archStack.push(left);
