Chapter 6 - branch and bound method

Overview of branch and bound method

The branch and bound method is the same as the backtracking method , It is also an exhaustive algorithm to search for feasible solutions in the solution space tree of the problem .

among “ m. ” refer to “ Branch and bound method ” The strategy for searching feasible solutions is breadth first search or cost first search with similar methods and ideas .

The concept and implementation of breadth first search have been introduced many times , No more details here ; The purpose of cost first search is to search with a certain defined priority , All nodes are processed from high priority to low priority .

( From low to high and from high to low are essentially the same , Take the example from high to low ).

If the status node is not strict according to the priority ( Can be equal to ) Descending order , In the solution space tree, according to the node height from high to low , The arrangement of nodes of the same height from left to right or from right to left , Then we can use breadth first search to achieve the purpose of cost first search ( The search order of breadth first search is the same as that of cost first search ).

But the state nodes in the state space tree are connected by decision , The decision has various changes to the attributes related to the state priority ( May increase , May reduce , Possible linearity , Possible nonlinearity ), The appearance of state nodes on the state space tree in the order of priority from high to low is often a jump , It is independent of the structure of the solution space tree .

If the policy can always keep the priority related attributes from the state node to the child node increasing or decreasing ( That is, the nodes on the tree conform to the nature of the heap from the perspective of attribute values ), We can use heap data structure to store unprocessed nodes in state space in cost first search , In the process of processing nodes, the method of expanding nodes to join containers according to optional policies is the same as breadth first search .

According to the nature of the heap data structure , Every time we take the top of the stack ( Team leader ) Node for processing , That is, the node with the highest priority among the remaining unprocessed nodes ( Child nodes not added to the container , There must be a node in the container whose priority is higher than that of the descendant node , Therefore, it is the node with the highest priority among the unprocessed nodes ), This continuous processing means that all state nodes are processed in the order of highest to lowest priority .

( Specific reasons and proof by means of counter evidence , Do not go into ).

“ Gauge ” It refers to the bounded function , It is the same as the bound function in the backtracking method , In breadth ( cost ) Priority search adds the extended nodes to ( first ) In the queue , Delete some unnecessary child nodes , This makes the selection more effective to speed up the search process .

I conclude that ： backtracking =( On the state space tree ) General depth first search + Bounded functions , Branch and bound method =( On the state space tree ) General breadth ( cost ) Priority search + Bounded functions .

As two algorithms for searching feasible solutions in the state space book , We generally consider the width and depth of the state space tree to choose whether to use the backtracking method or the branch and bound method ： When the path from the root node to some leaf nodes is too long , Select branch and bound method to avoid searching in a long path ; If there are too many choices , That is, when the width of the tree is too large , The backtracking method is selected to avoid too many state nodes at the same height of the extended state space tree .

If both conditions exist at the same time , We can limit the maximum depth of single backtracking method to avoid backtracking method to search elements into too deep branches , Continue to expand the maximum depth of single backtracking method until a certain backtracking method finds a feasible solution , This strategy is called iteration deepening .

If the attributes of the state node meet the requirements of cost first search , That is, the priority of child nodes is higher than that of parent nodes , We can also use the branch and bound method to find the optimal solution in a specific sense .

If the attribute is worth ( priority ) Decreasing from top to bottom according to the hierarchy and the optimal solution “ optimal ” It refers to the priority descending from top to bottom according to the hierarchy , Then the first feasible solution found by using the cost first search as the template is our optimal solution , In the context of this problem, it is not necessary to compare with the current optimal solution to determine whether a more optimal solution can be obtained by the pruning function .

Determine the feasible solution ( Optimal solution ) Decisions made

That's in the picture ( Trees ) In the search question of , Find the path from the root node to the current node , There are two general strategies ：

The first is to save the path from the root node to the node for each node , When expanding, the path from the root node to the child node is obtained through the path from the root node to the parent node .

This method is easy to implement , But it often wastes space and time .

The second is to save its predecessor nodes in the state space for each node when expanding child nodes , The parent node , Then the path from the parent node to the root node is obtained by backtracking the parent node , The reverse order is the path from the root node to the node .

Time performance of branch and bound method

Branch and bound method and backtracking method are essentially exhaustive methods ( Breadth first search and depth first search ), In the worst case, it has the same complexity as the exhaustive method ( Even worse , Because it is necessary to calculate the limit value and judge the limit function ), The actual solution efficiency is basically determined by the limit function .

---

solve 0/1 knapsack problem

That is, I have introduced it many times 0/1 knapsack problem .

Nodes whose weight is less than the specified weight form a solution space tree through decision , because 0/1 The decision of knapsack problem ensures that the value attribute of the child node must be greater than or equal to the value attribute of the parent node , The value attribute of the node is used to determine the priority of the node , We can use the priority queue branch and bound method , That is, the branch and bound method with cost first search as the template is used to solve 0/1 The optimal solution of knapsack problem .

Cost pre search solution 0/1 knapsack problem , That is to search the solution space tree with the value attribute of the state node as the standard of priority height .

The left child pruning strategy in the bound function is consistent with the left child pruning strategy in the backtracking method ; Mentioned in the previous chapter 0/1 The right child pruning of the knapsack is equivalent to fixing the subsequent strategy of the right child node to the left , Add all items that have not been selected to the backpack to get an upper bound of value .

In fact, the estimation of the upper bound of the value is rough , Because we often can't add all the remaining items to the current backpack . This upper bound estimation method is equivalent to a fixed policy jumping to the leftmost state node of the right subtree , No real search , In fact, this extension results in “ The leftmost status node ” May not meet the conditions of the problem specification , That is, it is not a feasible solution that meets the requirements ( Does not actually exist in the solution space tree ), The upper bound is overestimated .

So if we are actually searching , Search for the leftmost state node of the right subtree that meets the problem conditions ？ That is, the original method on the courseware ：

This method of estimating the upper bound of value will lead to counter examples when the items with small weight and high value appear in the decision-making at the lower level of the solution space tree . The solution is simple , It is to avoid the objects with small weight and high value appearing in the lower layer of the solution space tree , In other words, avoid the items with small weight and high value appearing after the items with large weight and low value in the item sequence , That is, a preprocessing of the item sequence ： Before the branch and bound method , First according to “ value / weight ” To sort the item sequence from large to small .

The corresponding queue branch and bound method is solved as follows ( Just one framework , When cost first search can be used, cost first search is generally used )：

// Status node type in the queue 
struct NodeType{
    	
	int no;// Node number 
	int i;// The level of the current node in the search space 
	int w;// Find the total weight of the current node 
	int v;// Find the total value of the current node 
	int x[MAXN];// Search for the decision made by the current state node  
	double ub;// Bounded functions bound Upper bound of estimated value 
};
// Calculate the status node e The upper bound of value 
// Need to value the item / The weight values are sorted 
void bound(NodeType &e){
    
	// Fix subsequent decisions to the left , Search the leftmost state node of the right subtree that meets the problem conditions 
	int i=e.i+1;
	int sumw=e.w;
	double sumv=e.v;
	while ((sumw+w[i]<=W)&&i<=n){
    	
		sumw+=w[i];	sumv+=v[i];	i++;
	}
	// If all the remaining items cannot be loaded into the backpack , For items that cannot be fully loaded into the backpack , The upper bound of value is estimated by means of block limit  
	if (i<=n) e.ub=sumv+(W-sumw)*v[i]/w[i];
	// If all the remaining items can be loaded into the backpack  
	else e.ub=sumv;
}
// Add the node into the container and judge the feasible solution through the node hierarchy , The optimal solution is obtained by comparison  
void EnQueue(NodeType e,queue<NodeType> &qu){
    
	// The feasible solution is judged by the hierarchy of nodes 
	if (e.i==n){
    
		if (e.v>maxv){
    
			// Save information about the optimal solution  
			maxv=e.v;
			for (int j=1;j<=n;j++) bestx[j]=e.x[j];
		}
	}
	else qu.push(e);// Non leaf nodes into the team 
}
// Queue branch and bound method to find 0/1 The optimal solution of knapsack 
void bfs(){
    
	int j;
	NodeType e,e1,e2;				
	queue<NodeType> qu;// Define a queue 
	// The root node is set to the initial value 
	e.i=0; e.w=0; e.v=0; e.no=total++; 
	for (j=1;j<=n;j++) e.x[j]=0;
	bound(e);// Calculate the value upper bound of the root node 
	qu.push(e);// Root node into the team 
	while (!qu.empty()){
    
		// Make different decisions on the team head node to expand  
		e=qu.front(); qu.pop();	
		// The left child prunes  
		if (e.w+w[e.i+1]<=W){
    
			// Create left child node 
			e1.no=total++; 
			e1.i=e.i+1;	e1.w=e.w+w[e1.i]; e1.v=e.v+v[e1.i];
			// Copy decisions  
			for (j=1;j<=n;j++) e1.x[j]=e.x[j];
			e1.x[e1.i]=1;// Add a new decision  
			bound(e1);// Find the upper bound of the value of the left child node 
			EnQueue(e1,qu);// The left child joins the team 
		}
		// Create a right child node 
		e2.no=total++;				
		e2.i=e.i+1; e2.w=e.w; e2.v=e.v;
		// Copy decisions 
		for (j=1;j<=n;j++) e2.x[j]=e.x[j];
		e2.x[e2.i]=0;// Add a new decision  
		// Calculate the value upper bound of the right child node and prune the right child  
		bound(e2);					
		if (e2.ub>maxv){
    
			EnQueue(e2,qu);// The right child joins the team 
		}
	}
}

The difference between the implementation of the priority queue branch and bound method and the queue branch and bound method is ：

1. The container is a priority queue .
2. You need to overload the relation function in the definition of the structure to ensure that the priority queue can be applied (0/1 The knapsack problem is sorted according to the value of the currently loaded knapsack ).

The solution process of the priority queue branch and bound method will not be repeated .

Whether queue branch and bound method or priority queue branch and bound method is used to solve 0/1 knapsack problem , In the worst case, the entire solution space tree must be searched , So the worst time and space complexity is O(2ⁿ), among n Number of items .

---

Solve the task assignment problem

That is, the task allocation problem mentioned earlier .

The solution space tree corresponding to task assignment is the permutation tree , From the root node i The second decision is expressed to the i Personal assignments . We consider the cost sum attribute of the currently assigned tasks , The sum of the costs of the child nodes obtained from the decision must be greater than the sum of the costs of the parent nodes , So we can use the priority queue branch and bound method to deal with this problem .

Cost pre search to solve the task assignment problem , In the solution space tree, the cost attribute of the state node is taken as the standard of priority height
Line cost first search .

The sum of costs increases from top to bottom , What we want is a feasible solution ( the n Leaf nodes of sub decision ) The node with the smallest sum of costs in , Therefore, the first feasible solution searched by the priority queue branch and bound method is the optimal solution with the minimum sum of costs we need , There is no need to compare with the current optimal solution to judge whether a better solution can be obtained .

( But let's learn how to design pruning functions )

Can we prune it ？ Although this issue was not covered in the previous chapter ( Because we think that the task allocation problem should not be handled in the framework of subset tree, but in the framework of permutation tree ), But we can still get a simple pruning method ：

For a state node , Compare its cost value with the current minimum cost , If the generation value is greater than the current minimum cost , Then there is no need to search the subtree .

This pruning method attempts to estimate the lower bound of the value of searching down from the node ( Hereinafter referred to as the lower bound of value ), But it is the same as the right child pruning strategy that has not been optimized , The estimation of the lower bound is too rough .

An optimized estimation strategy is ： Whether or not there will be conflicts between subsequent choices , Assign the lowest cost tasks to each of the following people except those already assigned in the current state , To estimate the lower bound of the cost .

Does this estimate guarantee the lower bound of the cost ？ Obviously , Because for any allocation scheme, the cost of the task actually selected by each person is greater than or equal to the task cost assigned to him by the above estimation strategy , Therefore, the sum of the costs allocated by the above strategies must be less than or equal to the actual minimum cost .

This is also a common design method of pruning function ： Each local optimal design method that violates the overall rule ( Note that it is not against the overall optimum ).

( If you avoid conflicting subsequent choices when estimating , Then it is a local optimal solution obtained by a greedy strategy , May not be able to get the overall optimal , Let alone used to estimate the lower bound )

The corresponding priority queue branch and bound method is as follows ( Pruning function with comparison with the current optimal solution )：

// Status node type 
struct NodeType{
      
	int no;// Node number 
	int i;// The level of the current node in the search space , Personnel number 
	int x[MAXN];//x[i] For the first time i Layer to personnel i Assigned task number 
	bool worker[MAXN];//worker[i]=true It means task i Has been allocated 
	int cost;// The cost of assigned tasks 
	int lb;// Lower bound of cost 
	// heavy load < Relational functions 
	// adopt cost Compare, not the lower bound of cost  
	bool operator<(const NodeType &s) const{
    
		return cost>s.cost;
	} 
};
// Calculate the cost lower bound of the state node  
void bound(NodeType &e){
      
	int minsum=0;
	// Whether or not there will be conflicts between subsequent choices 
	// Assign the lowest cost tasks to each of the following people except those already assigned in the current state  
	for (int i1=e.i+1;i1<=n;i1++ ){
      
		int minc=INF;
		for (int j1=1;j1<=n;j1++) 
			if (e.worker[j1]==false&&c[i1][j1]<minc) minc=c[i1][j1];
        minsum+=minc;
   }
   // Estimate the minimum cost of the current state node downward search  
   e.lb=e.cost+minsum;
}
// The priority queue branch and bound method is used to solve the task allocation problem  
void bfs(){
       
	int j;
    NodeType e,e1;
    priority_queue<NodeType> qu;
    memset(e.worker,0,sizeof(e.worker));	
	// Initialize root  
    e.i=0; e.cost=0; bound(e); e.no=total++;
    memset(e.x,0,sizeof(e.x)); 
	qu.push(e);// The root node enters the queue 
    while (!qu.empty()){
      
		e=qu.top(); qu.pop();		
		// First, the process of reaching n The feasible solution of sub decision , That is, the lowest cost feasible solution we want 
		//( Because it is searched from low to high according to the cost ) 
		if (e.i==n){
     
			for (j=1;j<=n;j++) bestx[j]=e.x[j];
		}
		e1.i=e.i+1;// Expand the tasks assigned to the next person 
		for (j=1;j<=n;j++){
      
			if (e.worker[j]) continue;// Consider tasks that have not been assigned  
			// Copy the assigned tasks  
			for (int i2=1;i2<=n;i2++) e1.worker[i2]=e.worker[i2];
			// Copy who is assigned what tasks  
			for (int i1=1;i1<=n;i1++) e1.x[i1]=e.x[i1];
			e1.x[e1.i]=j;// Give it to i Personal distribution No j A mission 
			e1.worker[j]=true;// It means task j Has been allocated 
			e1.cost=e.cost+c[e1.i][j];
			e1.no=total++;
			bound(e1);// Lower bound of estimated cost , Pruning  
			if (e1.lb<=mincost)	qu.push(e1);
       }
    }
}

Solve the flow shop scheduling problem

That is, the flow shop scheduling problem in the previous chapter .

According to the analysis in the previous chapter , The solution space tree of flow shop scheduling problem is also called permutation tree , From the root node i The second decision is expressed to the i Round assignment of jobs to be processed . We consider the state node M1 and M2 The sum of the time to process the currently assigned task , The sum of the time lengths of the child nodes obtained from the decision must be greater than the sum of the time lengths of the parent nodes , So we can use the priority queue branch and bound method to deal with this problem .

Cost pre search to solve flow shop scheduling problem , In the solution space tree, the time attribute of the state node is used as the standard of priority height to perform cost first search .

The sum of duration increases from top to bottom , What we want is a feasible solution ( the n Leaf nodes of sub decision ) The node with the smallest sum of the middle duration , That is to say, the optimal solution can still be determined directly , There is no need to prune by comparing with the current optimal solution .

( But we should also learn the design method of pruning function )

Same as the previous question , Can get the roughest pruning method ： Compare the execution time attribute of the state node with the time of the optimal solution .

Is there an optimized design ？

The direction of the fixed decision is only a feasible solution , The value obtained cannot be used as the estimate of the lower bound , Consider each local optimal design method that violates the overall rule .

But every task here, no matter where it is placed, is added to the pipeline , It needs the same processing time , That is, there is no choice for local optimization .

What does that mean ？ What we actually want to avoid for a decision is a bad allocation scheme that leads to M2 Need to wait M1 Work after work , That is, each decision only needs to be calculated M2 Time of processing operation (M2 Always have something to do , Not in idle state ).

Then the optimal lower bound valuation function , Is to ensure that all the tasks that have not yet been assigned ,M2 They are all done immediately , That is, the sum of the duration of the nodes in the current state plus the remaining jobs in M2 Lower bound of the time required to complete all jobs .

The corresponding algorithm is as follows ( Pruning function with comparison with the current optimal solution )：

// Status node type  
struct NodeType{
     
	int no;// Node number 
	int x[MAX];//x[i] It means the first one i The job number assigned to the assembly line by this decision 
	int y[MAX];//y[i]=1 Indicates that the number is i Your job has been assigned 
	int i;// Number of decisions made , That is, the level of the current node in the search space  
	int f1;// The job has been assigned on M1 Execution time of 
	int f2;// The job has been assigned on M2 Execution time of 
	// The conclusion of the previous chapter is as follows : 
	//f1=f1+a[j];
	//f2[i]=max(f1,f2[i-1])+b[j]
	int lb;// Lower bound of time length  
	// heavy load < Relational functions 
	bool operator<(const NodeType &s) const{
    
		return f2>s.f2;// adopt M2 Compare the time allocated after executing the current task  
};
// Calculate the cost lower bound of the state node 
void bound(NodeType &e){
    
	// The sum of the duration of nodes in the current state 
	// Add the remaining jobs in M2 Lower bound of the time required to complete all jobs  
	int sum=0;
	for (int i=1;i<=n;i++) if (e.y[i]==0) sum+=b[i];	
	e.lb=e.f1+sum;
}
// Solve the flow shop scheduling problem by solving the priority queue branch and bound method 
void bfs(){
      
	NodeType e,e1;
	priority_queue<NodeType> qu;	
	// Initialize the root node information  
	memset(e.x,0,sizeof(e.x));		
	memset(e.y,0,sizeof(e.y));		
	e.i=0; e.f1=0; e.f2=0; 
	e.no=total++;
	bound(e);// Calculate the lower bound of the root node 
	qu.push(e);// The root node enters the queue 
	while (!qu.empty()){
      
		e=qu.top(); qu.pop();	
		// First, the process of reaching n The feasible solution of sub decision , That is, the feasible solution with the lowest duration we want 
		//( Because it is searched from low to high according to the duration ) 
		if (e.i==n){
      
			for (int j1=1;j1<=n;j1++) bestx[j1]=e.x[j1];
        }
		e1.i=e.i+1;	// The extension assigns the next job 
		for (int j=1;j<=n;j++){
      
			if (e.y[j]==1) continue;// Consider unassigned jobs  
			// Copy which jobs were assigned before each step  
			for (int i1=1;i1<=n;i1++) e1.x[i1]=e.x[i1];
			// Copy the assigned job number  
			for (int i2=1;i2<=n;i2++) e1.y[i2]=e.y[i2];
			e1.x[e1.i]=j;// For the first time i Step assign job j
			e1.y[j]=1;// It means homework j Has been allocated 
			e1.f1=e.f1+a[j];//f1=f1+a[j]
			e1.f2=max(e.f2,e1.f1)+b[j];//f2[i+1]=max(f2[i],f1)+b[j]
			bound(e1);// Calculate the lower bound for pruning  
			if (e1.f2<=bestf){
      
				e1.no=total++;
				qu.push(e1);
			}
		}
	}
}

---

summary

Cost first search for values applicable to child nodes ( priority ) Than the value of the parent node ( priority ) Tall trees , The state nodes in the solution space tree can be prioritized from high to low ( From low to high ) Search for elements in the order of .

backtracking = General depth first search + Bounded functions .

Branch and bound method = General breadth ( cost ) Priority search + Bounded functions .

When the template of branch and bound method is cost first search , When searching from high to low priority , The first feasible solution we find is the one with the lowest priority , If the priority in the priority queue is exactly the opposite of the priority we need , That means we have got the optimal solution we need , At this time, there is no need to compare with the current optimal solution to judge whether the pruning function can get a better solution .