Binary and MixedInteger Programming
seminar class Active In SP Posts: 5,361 Joined: Feb 2011 
15022011, 02:37 PM
Binary and MixedInteger 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 integervalued 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 j ≥ 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 nonnegative.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 (1xj’). It is also easy to reorder the variables. Constraint right handsides can be negative, so≤ constraints are easily converted to≥ form by multiplying through by1. 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 lookahead 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 depthfirst node selection. It is of course possible to replace thisby another node selection strategy, such as bestfirst, 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 depthfirst node selection. download full report sce.carleton.ca/faculty/chinneck/po/Chapter13.pdf 


