Binary and Mixed-Integer Programming
Active In SP
Joined: Feb 2011
15-02-2011, 02:37 PM
Binary and Mixed-Integer Programming
The general branch and bound approach described in the previous chapter can be customized forspecial situations. This chapter addresses two special situations:
when all of the variables are binary (known as “Binary Integer Programming” or BIP),when some or all of the variables are integer-valued and the objective function and all of the constraints are linear (known as “Mixed Integer Programming”, MIP, or “MixedInteger Linear Programming”, MILP).
Binary Integer Programming
In binary problems, each variable can only take on the value of 0 or 1. This may represent theselection or rejection of an option, the turning on or off of switches, a yes/no answer, or manyother 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 tandard form:The m constraints are all inequalities of the form
∑ aij x
≥ bi for i 1,2,...m
All of the xj where j=1,2,…n are binary variables (can only have a value of 0 or 1).All objective function coefficients are non-negative.The variables are ordered according to their objective function coefficients so that
0 ≤ c1 ≤ c2 ≤…≤ cn.This may seem like a restrictive set of conditions, but many problems are easy to convert to thisform. 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 handsides 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 set all of the variables to 0 without violating one or more constraints, thenwe 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. Balasalgorithm 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 solutionthat might provide a feasible solution. There are two cases, as described nextIf the current variable is set to 1, i.e. xN = 1, then the algorithm assumes that this might provide athe cheapest thing that can happen. Note that xN (“x now”) is not the same as xn (the last x in thelist).If the current variable is set to 0, i.e. xN = 0, then things are a little different. Recall that we needto calculate a bounding function value only for nodes that are currently infeasible. In this case,one of the≥ constraints is not yet satisfied, i.e. the left hand side is less than the right handconstant. But if we set the current variable to zero, the left hand side value of the violatedconstraint(s) will not change. Therefore we must set at least one more variable to 1, and thealgorithm assumes that this cheapest setting might provide a feasible solution, so it proceeds.It is easy to determine whether the solution proposed by the bounding function is feasible: justassume that all of the variables past xN (when xN = 1) or past xN+1 (when xN = 0) take on the valueof zero and check all of the constraints. If all of the constraints are satisfied at the solutionproposed by the bounding function, then the node is fathomed, since it is not possible to get alower value of the objective function at any node that descends from this one (the boundingfunction has made sure of that). All that remains is to compare the solution value at the node tothe value of the incumbent, and to replace the incumbent if the current node has a lower value.Infeasibility fathoming is also worthwhile in this algorithm since it is easy to determine when abud node can never develop into a feasible solution, no matter how the remaining variables areset. This is done by examining each constraint one by one. For each constraint, calculate thelargest possible left hand side value, given the decisions made so far, as follows: (left hand sidevalue for variables set so far) + (maximum left hand side value for variables not yet set). Thesecond term is obtained by assuming that a variable will be set to 0 if its coefficient is negativeand 1 if its coefficient is positive. If the largest possible left hand side value is still less than theright hand side constant, then the constraint can never be satisfied, no matter how the remainingvariables are set, so this node can be eliminated as “impossible”. For example, consider theconstraint -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 ifx3 and x4 are set to 1 while x5 is set to 0, giving a left hand side value of (-9) + (4) = -5, which isnot≥ 1, hence the partial solution (1,1,?,?,?) cannot ever yield a feasible solution, so the node isfathomed as “impossible”.Balas Additive Algorithm uses depth-first node selection. It is of course possible to replace thisby another node selection strategy, such as best-first, but if you do so then you are no longerfollowing Balas’ algorithm, strictly speaking. If your problem formulation states that you areusing the Balas algorithm, then you must use depth-first node selection.
download full report