preface

Recently, I realized that export is the way to go. There are several advantages:

  • It is easy to comb and think again and repair the blind area of knowledge structure
  • Turn internalization into externalization to build influence

I hope there will be updates every week. If there is any mistake or omission, please correct it.

The branch and bound algorithm

Branch and bound is one of the most commonly used algorithms for integer programming problems. This method can solve both pure integer programming and mixed integer programming problems.

The main idea of branch-and-bound method: taking the maximum problem as an example, it usually divides all feasible solution space into smaller and smaller subsets repeatedly, which is called branching. In addition, an optimal solution is calculated for the solution set within each subset and an attempt is made to update the upper bound of the target. When the feasible solution of integer constraint is satisfied, the lower bound of the target is updated, which is called delamination. After each branching, those subsets whose bounds exceed the target value of the known feasible solution set are not further branched, so that many subsets may not be considered. This is called pruning.

This algorithm relies very much on the efficient evaluation of upper and lower bounds. If there are no upper and lower bounds, the whole algorithm will degenerate to exhaustive search.

The algorithm depends on efficient estimation of the lower and upper bounds of regions/branches of the search space. If no bounds are available, the algorithm degenerates to an exhaustive search.

If the maximization problem is taken as an example, the algorithm process can be summarized as the following steps:

1. Initialization Firstly, a heuristic method is used to calculate the target value or negative infinity of a feasible solution assigned to B (in the maximization problem, the lower bound Lb is equivalent to B); Initializes A queue for the target optimization problem and queues the original problem (A). For example, to find the following target maximum value, we can initialize B to -inf.

$$ \begin{aligned} &(A) \max S=5 x_{1}+8 x_{2} \\ &\left\{\begin{array}{l} x_{1}+x_{2} \leq 6 \\ 5 x_{1}+9 x_{2} \leq X_ 45 \ \ x_ {1}, {2} \ geq 0 and to integers {array} \ \ end right.} {aligned \ end $$

2. The current optimal solution and upper and lower bounds are updated out of the queue. The integer constraints are not considered temporarily, and the simplex method is used to solve an optimal solution X and the target value B’ in linear space. The branch operation and pruning operation are completed continuously by updating the upper and lower bounds.

  • If x exists that is not an integer and B’

    UB is not a case because the branching solution space is smaller)
    ,>
  • If the values of x are all integers and B’>LB, the lower bound LB=B’, and record the optimal solution X so far, the node stops exploring downward;
  • If B ‘is not between [LB,UB], it can be considered that there is no better parameter combination under the current node, stop exploring downward, that is, pruned (after all, reduced constraints can not exceed the current LB, it seems that there is no hope;). (Note: the lower bound is controlled by integer solution, and the upper bound is controlled by linear solution)

For example, regardless of the integer constraint, A goes to B0 (the solution of A can be considered A subset of the solution of B0)

$$ \begin{aligned} &(B_{0}) \max S=5 x_{1}+8 x_{2} \\ &\left\{\begin{array}{l} x_{1}+x_{2} \leq 6 \\ 5 x_{1}+9 x_{2} \leq 45\\ x_{1}, x_{2} \geq 0 \end{array}\right. \end{aligned} $$

X1 =2.25, X2 =3.75 and S0=41.25 are obtained by simplex method

3. Branch nodes According to the variable results obtained by the simplex method, select a variable for disintegration: the integer before and after the variable corresponding to the optimal solution is taken as the disintegration.

E.g. B0 will be disassembled into B1 and B2, and B1 and B2 will be put into the queue; Since x2=3.75 of the optimal solution after relaxation in the previous step, the original constraint is changed to <=3 and >=4. (Note: when placed in the queue, both B1 and B2 have “integer constraints”)

$$ \begin{aligned} &\left(B_{1}\right) \max S=5 x_{1}+8 x_{2}\\ &\left\{\begin{array}{l} x_{1}+x_{2} \leq 6\\ {5 x_{1}+9 x_{2} \leq 45} \\ \begin{array}{l} x_{2} \leq 3 \\ x_{1}, X_ {2} \geq 0 and integer \end{array}\ end{array}\right.\\ end{aligned} $$

$$ \begin{aligned} &\left(B_{2}\right) \max S=5 x_{1}+8 x_{2}\\ &\left\{\begin{array}{l} x_{1}+x_{2} \leq 6\\ {5 x_{1}+9 x_{2} \leq 45} \\ \begin{array}{l} x_{2} \geq 4 \\ x_{1}, X_ {2} \geq 0 and integer \end{array}\ end{array}\right.\\ end{aligned} $$

The ways of queuing can be divided into breadth first search, depth first search and best first search.

  • Breadth – first search (BFS) : breadth-first search, is horizontal search, first search the tree node. And then layer by layer down. This search can be done using a FIFO Queue.
  • Depth-first search (DFS) : Depth-first search (DFS) is a vertical search that starts from one branch to the end and then jumps to the next. This search can be done with a LIFO Queue, which is a stack.
  • Best – First Search: Best first search, the best first search Algorithm is a Heuristic search Algorithm, which is based on the breadth first search Algorithm. The difference is that it relies on the valuation function to evaluate the nodes to be traversed, and chooses the nodes with low cost to traverse until finding the target point. This search can be done using a Priority Queue.

4. Terminate decision: When the queue is empty, the calculation ends.

Introduction to Wikipedia :(minimizing questions)

  1. Using a heuristic, find a solution xh to the optimization problem. Store its value, B = f(x_h). (If no heuristic is available, set B to infinity.) B will denote the best solution found so far, and will be used as an upper bound on candidate solutions.
  2. Initialize a queue to hold a partial solution with none of the variables of the problem assigned.
  3. Loop until the queue is empty: 3.2. If N represents a single candidate solution x and f(x) < B, Then X is the best solution so far. Record it and set B ← F (X). Branch on N to produce new nodes Ni. For each of these: 3.3.1. If bound(N_I) > B, do nothing; since the lower bound on this node is greater than the upper bound of the problem, It will never lead to the optimal solution, and can be discarded. 3.3.2.

reference

A few good articles: 1,2,3