In binary problems, each variable can only take on the value of 0 or 1. This may represent the selection or rejection of an option, the turning on or off of switches, a yes/no answer, or many other situations. We will study a specialized branch and bound algorithm for solving BIPs, known as Balas Additive Algorithm. It requires that the problem be put into a standard form:
This may seem like a restrictive set of conditions, but many problems are easy to convert to this form. For example, negative objective function coefficients are handled by a change of variables in which xj is replaced by (1 -xj’). It is also easy to reorder the variables. Constraint right hand sides can be negative, so ≤ constraints are easily converted to ≥ form by multiplying through by -1. The biggest restriction is that Balas Additive Algorithm does not handle equality constraints.
The keys to how Balas Algorithm works lies in its special structure
- The objective function sense is minimization, and all of the coefficients are nonnegative, so we would prefer to set all of the variables to zero to give the smallest value of Z.
- If we cannot s et all of the variables to 0 without violating one or more constraints, then we prefer to set the variable that has the smallest index to 1. This is because the variables are ordered so that those earlier in the list increase Z by the smallest amount.
These features also affect the rest of the branch and bound procedures. Branching is simple: each variable can only take on one of two values: 0 or 1. Bounding is the interesting part. Balas algorithm does not perform any kind of look -ahead to try to complete the solution or a simplified version of it. Instead the bounding function just looks at the cost of the next cheapest solution that might provide a feasible solution.
It is easy to determine whether the solution proposed by the bounding function is feasible: just assume that all of the variables past xN (when xN = 1) or past xN+1 (when xN = 0) take on the value of zero and check all of the constraints. If all of the constraints are satisfied at the solution proposed by the bounding function, then the node is fathomed, since it is not possible to get a lower value of the objective function at any node that descends from this one (the bounding function has made sure of that). All that remains is to compare the solution value at the node to the value of the incumbent, and to replace the incumbent if the current node has a lower value.
Infeasibility pruning is also worthwhile in this algorithm since it is easy to determine when a bud node can never develop into a feasible solution, no matter how the remaining variables are set. This is done by examining each constraint one by one. For each constraint, calculate the largest possible left hand side value, given the decisions made so far, as follows: (left hand side value for variables set so far) + (maximum left hand side value for variables not yet set). The second term is obtained by assuming that a variable will be set to 0 if its coefficient is negative and 1 if its coefficient is positive. If the largest possible left hand side value is still less than the right hand side constant, then the constraint can never be satisfied, no matter how the remaining variables are set, so this node can be eliminated as “impossible”. For example, consider the constraint
–4x1 – 5x2 + 2x3 + 2x4 – 3x5 ≥ 1. Suppose that both x1 and x2 have already been set to 1, while the remaining variables have not yet been set. The largest possible left hand side results if x3 and x4 are set to 1 while x5 is set to 0, giving a left hand side value of ( –9) + (4) = –5, which is not ≥ 1, hence the partial solution (1,1,?,?,?) cannot ever yield a feasible solution, so the node is fathomed as “impossible”.
Balas Additive Algorithm uses depth -first node selection. It is of course possible to replace this by another node selection strategy, such as best – first, but if you do so then you are no longer following Balas’ algorithm, strictly speaking. If your problem formulation states that you are using the Balas algorithm, then you must use depth-first node selection.
Example
Note that the variables are already ordered as required by Balas’ algorithm. There are 26 = 64 possible solutions if they are all enumerated, but we expect that Balas’ algorithm will generate far fewer full and partial solutions. The branch and bound tree develops as shown in the following diagrams. Figure below shows the root node, which has an objective function value of 0 and is infeasible by constraints 1 and 3, hence it must be expanded. From here on, each node is labeled with the bounding function value, and an indication of status for the current solution that the node represents (note that this is not the same as the bounding function solution for zero nodes). Inf indicates that the node is currently infeasible and Imp indicates that the node has been found to be impossible to satisfy; each of these notations is followed by an indication of which constraints are causing infeasibility or impossibility.
There are still live bud nodes on the developing branch and bound tree, so we choose the next node to expand, via the depth-first rule. Here we have just the two nodes to choose from, and since this is a minimization problem, we choose the node having the smallest value of the bounding function, and expand it using the next variable in the list, x2. This is shown in second branching figure. Note that node (1,1,?,?,?,?) is impossible by constraint 2. Once x1 and x2 are set to 1, no matter how the remaining variables are set, the left hand side will never be greater than –2.
Now we select the next node for expansion. Since we are using depth-first node selection, we are left only a single bud node to choose: (1,0,?,?,?,?), with a bounding function value of 9. Best-first node selection would have chosen node (0,?,?,?,?,?) because it has a lower bounding function value of 5.
The expansion of node (1,0,?,?,?,?) is shown in third branching figure. Node (1,0,0,?,?,?) is fathomed and found to be feasible when using the bounding function solution (1,0,0,1,0, 0), with an objective function value of 12. This is our first incumbent solution. Node (1,0,1,?,?,?) is found to be impossible by constraint 1.
