# 干货 | 10分钟搞懂branch and bound算法的代码实现附带java代码

OUTLINE

Example-1

Example-2

00

Example-1

01

ExampleProblem.java内置了三个整数规划模型的实例。

public BnB_Guide(int demoProblem){ example = new ExampleProblem(demoProblem); LinearProgram lp = new LinearProgram(); lp = example.getProblem().getLP(); solver = SolverFactory.newDefault(); 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 verifyOptimalSolution(solution,lp); else this.solveChildProblems(lp, solution, maxElement); // create 2 child problems and solve them printSolution(); }

1. 首先变量lp保存了整数规划的松弛问题。

2. 在调用求解器求解松弛模型以后，判断是否所有决策变量都是整数了，如果是，已经找到最优解。

3. 如果不是，根据找出最大的非整数的决策变量，对该变量进行分支，solveChildProblems。

```    public void solveChildProblems(LinearProgram lp, double[] solution ,int maxElement){
searchDepth++;                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 double[lp.getDimension()]; // The variables' values of the new constraint                 for(int i=0;i<constr_val.length;i++){ // Populate the table            if(i == maxElement )                constr_val[i] = 1.0;            else                constr_val[i] = 0;        }           //Create 2 child problems: 1. x >= ceil(value), 2. x <= floor(value)        lp1.addConstraint(new LinearBiggerThanEqualsConstraint(constr_val, Math.ceil(solution[maxElement]), constr_name));        lp2.addConstraint(new LinearSmallerThanEqualsConstraint(constr_val, Math.floor(solution[maxElement]), constr_name));        solveProblem(lp1);        solveProblem(lp2);    }```

1. 首先新建两个线性的子问题。

2. 两个子问题分别添加需要分支的决策变量新约束：1. x >= ceil(value), 2. x <= floor(value)。

3. 一切准备就绪以后，调用solveProblem求解两个子问题。

`    private void solveProblem(LinearProgram lp) {                double[] sol = solver.solve(lp);                LPSolution lpsol = new LPSolution(sol, lp);        double objVal = lpsol.getObjectiveValue();                if(lp.isMinProblem()) {            if(objVal > MinimizeProblemOptimalSolution) {                System.out.println("cut >>> objVal = "+ objVal);                return;            }        }        else {            if(objVal < MaximizeProblemOptimalSolution) {                System.out.println("cut >>> objVal = "+ objVal);                return;            }                    }                System.out.println("non cut >>> objVal = "+ objVal);                int maxElement = this.getMax(sol);        if(maxElement == -1 && lp.isFeasable(sol)){ //We found a solution            solutionFound = true;            verifyOptimalSolution(sol,lp);        }        else if(lp.isFeasable(sol) && !solutionFound) //Search for a solution in the child problems            this.solveChildProblems(lp, sol, maxElement);            }`

1. 首先调用求解器求解传入的线性模型。

2. 然后实行定界剪支，如果子问题的objVal比当前最优解还要差，则剪掉。

3. 如果不剪，则判断是否所有决策变量都是整数以及解是否可行，如果是，找到新的解，更新当前最优解。

4. 如果不是，根据找出最大的非整数的决策变量，对该变量再次进行分支，进入solveChildProblems。

Example-2

02

input是模型的输入，输入的是一个整数规划的模型。由于输入和建模过程有点繁琐，这里就不多讲了。挑一些重点讲讲具体是分支定界算法是怎么运行的就行。

`public class BNBSearch {        Deque<searchNode> searchStack = new ArrayDeque<searchNode>();    double bestVal = Double.MAX_VALUE;    searchNode currentBest = new searchNode();    IPInstance solveRel = new IPInstance();     Deque<searchNode> visited = new ArrayDeque<searchNode>();        public BNBSearch(IPInstance solveRel) {        this.solveRel = solveRel;        searchNode rootNode = new searchNode();        this.searchStack.push(rootNode);    };`

BNBSearch 这个类是branch and bound算法的主要过程，成员变量如下：

• searchStack ：构造和遍历生成树用的，栈结构。
• bestVal：记录当前最优解的值，由于求的最小化问题，一开始设置为正无穷。
• currentBest ：记录当前最优解。
• solveRel ：整数规划模型。
• visited ：记录此前走过的分支，避免重复。

```public class searchNode {      HashMap<Integer, Integer> partialAssigned = new HashMap<Integer, Integer>();            public searchNode() {          super();      }      public searchNode(searchNode makeCopy) {          for (int test: makeCopy.partialAssigned.keySet()) {                this.partialAssigned.put(test, makeCopy.partialAssigned.get(test));            }          }
}```

`    public int solveIP() throws IloException {        while (!this.searchStack.isEmpty()) {            searchNode branchNode = this.searchStack.pop();            boolean isVisited = false;            for (searchNode tempNode: this.visited) {                if (branchNode.partialAssigned.equals(tempNode.partialAssigned)){                    isVisited = true;                    break;                }            }                        if (!isVisited) {                visited.add(new searchNode(branchNode));                double bound = solveRel.solve(branchNode);                if (bound > bestVal || bound == 0) {                    //System.out.println(searchStack.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) {                            searchNode left = new searchNode(branchNode);                            searchNode right = new searchNode(branchNode);                            left.partialAssigned.put(varToSplit, 0);                            right.partialAssigned.put(varToSplit, 1);                            this.searchStack.push(left);                            this.searchStack.push(right);                        }                                            }                }            }        }        return (int) bestVal;    }`

```  public double solve(searchNode node) throws IloException {            try {          cplex = new IloCplex();          cplex.setOut(null);                    IloNumVarType [] switcher = new IloNumVarType[2];          switcher[0] = IloNumVarType.Int;          switcher[1] = IloNumVarType.Float;          int flag = 1;                    IloNumVar[] testUsed = cplex.numVarArray(numTests, 0, 1, switcher[flag]);                    IloNumExpr objectiveFunction = cplex.numExpr();             objectiveFunction = cplex.scalProd(testUsed, costOfTest);                    cplex.addMinimize(objectiveFunction);
for (int j = 0; j < numDiseases*numDiseases; j++) {              if (j % numDiseases == j /numDiseases) {                  continue;              }                            IloNumExpr diffConstraint = cplex.numExpr();                            for (int i =  0; i < numTests; i++) {                  if (A[i][j/numDiseases] == A[i][j%numDiseases]) {                      continue;                  }                  diffConstraint = cplex.sum(diffConstraint, testUsed[i]);               }                            cplex.addGe(diffConstraint, 1);              diffConstraint = cplex.numExpr();
}                    for (int test: node.partialAssigned.keySet()) {              cplex.addEq(testUsed[test], node.partialAssigned.get(test));          }                              //System.out.println(cplex.getModel());                    if(cplex.solve()) {                double objectiveValue = (cplex.getObjValue());                                 for (int i = 0; i < numTests; i ++) {                    if (cplex.getValue(testUsed[i]) == 0) {                        node.partialAssigned.put(i, 0);                    }                    else if (cplex.getValue(testUsed[i]) == 1) {                        node.partialAssigned.put(i, 1);                    }                }                //System.out.println("LOL"+node.partialAssigned.size());                               return objectiveValue;          }
}      catch(IloException e) {          System.out.println("Error " + e);      }      return 0;  }```

`          for (int test: node.partialAssigned.keySet()) {              cplex.addEq(testUsed[test], node.partialAssigned.get(test));          }`

if (bound > bestVal || bound == 0)：剪支。

if (bound < bestVal && bound!=0)：判断是否所有决策变量都为整数，如果是，找到一个可行解，更新当前最优解。如果不是，找一个小数的决策变量入栈，等待后续分支。

03

Example-1：

Example-2：

END

1

0 条评论