Integer Programming
Lynn A. Fish, Ph.D.
Spring 2000

Integer Programming: extension of LP that solves problems requiring integer solutions

Goal Programming: extension of LP that permits more than one objective to be stated

Nonlinear Programming: case where objectives or constraints are nonlinear

Integer Programming: solution values must be whole numbers in integer programming
Rounding off is one way to reach integer solution values, but it often does not yield the best solution.
An integer programming solution can never be better than the solution to the same LP problem. The integer problem is usually worse in terms of higher cost or lower profit.

Types of Integer Programming Problems
Pure Integer Programming Problems: All decision variables must have integer solutions.
Max 6 X1 + 8 X2
St: 4 X1 + 6 X2 < 36
10 X1 + 7 X2 < 70
X1 and X2 > 0 and integer

Mixed-Integer Programming: some, but not all, of the decision variables are required to have integer values.
Max 6 X1 + 8 X2
St: 4 X1 + 6 X2 < 36
10 X1 + 7 X2 < 70
X1 and X2 > 0 and X1 integer

Zero-One Integer Programming: All decision variables must have integer solution values of 0 or 1.
Example: Max 65 X1 + 70 X2 + 40 X3 + 50 X4
St: 10 X1 + 12 X2 + 6 X3 + 8 X4 < 30
3 X1 + X2 + 2 X3 < 5
All variables 0 or 1





Methods to Solve
Complete Enumeration:
Steps:
List all possible alternatives.
Determine which alternatives are feasible.
Find the value of the objective function for each feasible alternative.
Select the feasible alternative with the best value of the objective function.


Example:
Solve the following problem using the enumeration method:
Max 65 X1 + 70 X2 + 40 X3 + 50 X4
St: 10 X1 + 12 X2 + 6 X3 + 8 X4 < 30
3 X1 + X2 + 2 X3 < 5
All variables 0 or 1

There are four decision variables, thus possibilities = 16.

List all possible alternatives as in the table below, check for feasibility, determine objective function value and choose optimal:

DS WIN Solution: NOTE Additional Constraints for Xi 0 or 1 must be added.

Branch and Bound (for Maximization Problems)
a) Method
Solve the problem as if it were a standard LP problem. Ignore any integer requirements.
If all variables have integer values, this is the optimal integer solution. (For a mixed-integer problem, if all variables with integer requirements are integer, the solution is optimal.) If any variables with integer requirements are noninteger, this is not the optimal solution. Using the values of the variables for this solution, compute the value of the objective function. This is the upper bound: No feasible solution can yield a better value.
Examine the non-integer valued variables with integer requirements. Identify the one with the largest fractional part. In case of a tie, choose one arbitrarily. Branch on that variable: Round it both up and down to integer values. For the lower integer value, formulate a new constraint requiring that this variable cannot exceed this lower value. For the upper integer value, formulate a new constraint requiring that this variable must equal or exceed this upper value.
Solve two new problems, one consisting of the original problem and the lower integer constraint and the other consisting of the original problem and the upper integer constraint. (For subsequent nodes, include the constraints for all branches leading to the node being considered.) For each node (problem), one of three possibilities will materialize:
All required variables will be integer. This may be the optimal solution. Compute the upper bound for this solution. Stop branching on this portion of the tree. This upper bound is now a standard of comparison for other nodes: Stop branching from any node if its upper bound does not exceed this node's value. For nodes with higher upper bounds, return to step 3.
The solution will be infeasible. Again, stop branching on this portion of the tree, but consider other portions: Return to step 3.
If some integer-required variables are still non-integer, compute the upper bound for this node. If any all-integer nodes exist, compare the upper bound of this node to the highest upper bound of the all-integer nodes. If it exceeds that value, return to step 3. Otherwise, stop branching from this node and consider other nodes using step 3.
The optimal integer solution is found when the value of the objective function at a node with all integer values is not exceeded by the upper bound of any other node, whether they represent all integers or not.

Example: 0 or 1 Integer Problem continued. Note all branches in this type of problem are expressed as equalities rather than inequalities.

Node 1. Solve for LP without 0 or 1 constraint. This solves for the upper bound on the problem.
The solution at this point is: X1 = .77, X2 = .69, X3 = 1, and X4 = 1, Z = 188.46.
Since X1 has the larger fractional value, branch on X1.

Node 2. An all 0 or 1 solution. This is a candidate for the optimum at this point. However, the branch X1 = 1 must first be explored.
The solution at this point is: X1 = 0, X2 = 1, X3 = 1, and X4 = 1, Z = 160.

Node 3. The solution is not completely 0 or 1. However, the upper bound of $188.33 is higher than at Node 2, so a continued search from Node 3 is indicated. Variables X2 and X3 have the same fractional values, so variable X2 was arbitrarily selected to branch on.
The solution at this point is: X1 = 1, X2 = .67, X3 = .67, and X4 = 1, Z = 188.33.

Node 4. All variables are 0 or 1, so no further branching will be done from this node. Moreover, because its objective function value of $155 is less than the value at Node 2, this is not a candidate for the optimum. Consequently Node 2 still exists as the standard against which to judge other solutions.
The solution at this point is: X1 = 1, X2 = 0, X3 = 1, and X4 = 1, Z = 155.

Node 5. Still not completely 0-1, but because the upper bound of $186.25 exceeds the value at Node 2, additional branching is called for. Because variable X4 has the larger fractional part, it is branched on.
The solution at this point is: X1 = 1, X2 = 1, X3 = .50, and X4 = .63, Z = 186.25.

Node 6. Although not completely 0-1, its upper bound is less than the value at Node 2, so no further branching from Node 6 would be justified.
The solution at this point is: X1 = 1, X2 = 1, X3 = .50, and X4 = 1, Z = 155.

Node 7. This is the optimal solution because all variables are 0 or 1 and its value of $185 exceeds the only other possible optimum, that of Node 2 which was infeasible.
The solution at this point is: X1 = 1, X2 = 1, X3 = 0, and X4 = 1, Z = 185.


Note that for the most part these interations correspond to the DSWIN interation results.

Example (All integer problem):
Consider this all-integer problem:
Max 6 X1 + 8 X2
St: 4 X1 + 6 X2 < 36
10 X1 + 7 X2 < 70
X1 and X2 > 0 and integer

Solve for LP relaxation solution (i.e, without X1 and X2 as integers).
Node 1. The solution at this point is: X1 = 5.25, X2 = 2.50, and Z = 51.50.
Since both decision variables are not integer, we are not optimal. Recommend choosing variable with largest fractional value, therefore, X2 to branch on first.

Explore X2 < 2 and X2 > 3. Thus the two problems at this point are:

Node 2: The solution at this point is: X1 = 5.6, X2 = 2, and Z = 49.60.
Node 3: The solution at this point is: X1 = 4.5, X2 = 3, and Z = 51.00.

Because neither of these solutions have both X1 and X2 integer, additional branching will be necessary. The Z values for each sub-problem now become the upper bounds for their respective nodes: No subsequent branching from that node can produce a value of the objective function that exceeds this upper bound. The lower bound at each node could be determined. Thus, both nodes offer further branching possibilities.. However, since Node 3 Z is greater than Node 2 Z, it seems reasonable to explore branches from Node 3 first.

Since the only non-integer is X1 = 4.5, we can branch on X1 < 4 and X1 > 5. Thus the two problems at this point are:

Node 4: The solution at this point is: X1 = 4, X2 = 3.33, and Z = 50.67.
Node 5: The solution at this point is infeasible.

Since Node 5 is infeasible, no further branching from this node can occur. Both Nodes 2 and 4 are candidates for further branching. Because Node 4 has the higher upper bound, it appears to offer more promise than branching from Node 2 at this time. Therefore, continue with Node 4.

The non-integer variable at Node 4 is X2, so branch on it. The two new branches are X2 < 3 and X2 > 4. Thus the new sub-problem becomes:

Therefore at these nodes, X2 must equal 3. The solutions at this point are:
Node 6: The solution at this point is: X1 = 4, X2 = 3, and Z = 48.
Node 7: The solution at this point is: X1 = 3, X2 = 4, and Z = 50.

At this point, both decision variables are integer, which means no additional branching can occur from either node as: No lower node can produce a value of the objective function that will exceed the value at this point, and these solution are both integer. Comparing the solutions at these nodes, Node 7 is preferred over Node 6. The only other possibility is branching from Node 2, which cannot be optimal as it is no all-integer. If we compare Z at Node 2 and Node 7, we find that Node 7 Z > Node 2 Z, thus branching from Node 2 can not yield a solution better than Node 7. Hence, Node 7 is optimal.

Optimal Solution: both of the following conditions must be satisfied
1) A node consists of all integer values, or in the case of a mixed integer problem, the variables that are required to be integer are all integers.
2) No other node at a branch end, whether all-integer or not, has a higher upper bound.

Other comments on Branch & Bound:
Notice that the value of the objective function at the nodes get smaller moving down the tree. Although in some problems a lower node may have a value equal to a higher node's value, the value at a node in a maximization problem can never exceed the value of the node it emanates from. This holds true because each sub-problem is more restrictive than the preceding one.
After the first node, each node has at least one variable that is integer.
We explore the tree portion that had the higher upper bound (i.e., value of Z) at any point in the problem.



DSWIN Solution:

3) Graphical Methodology:

If there are only 2 variables, the solution can be solved for using the graphical method.
First, plot the constraints as usual and solve. Then explore adding additional integer constraints and the additional constraints they form.

Example:

Max 6 X1 + 8 X2
St: 4 X1 + 6 X2 < 36
10 X1 + 7 X2 < 70
X1 and X2 > 0 and integer

NODE 1

Then add additional constraints, here we choose X2 < 2.0 and X2 > 3.0 separately.
Adding X2< 2.0 (NODE 2):

Additional X2 > 3 (NODE 3):

Looking at the solutions to both of the above problems, we note that in both cases X1 is not integer. Thus, similar to the branching results, we constrain X1. Thus add X1 < 4 and X1 > 5.
Additional X1 < 4 (Node 4):

Additional X1> 5: (NODE 5) There is no feasible solution.



Thus we need to consider X2 = 3, X1 < 4 and 3 < X2 < 4 and X1< 4:
Additional Constraint X2 = 3 (NODE 6):

Additional Constraint X2 > 4 (Node 7):

As we found before in the Branch and Bound Solution, this is the optimal solution. Hence, graphically we can only consider the values where X1 and X2 equal integer values given the feasible region.






Mixed-Integer Problem Example:

Max 6 X1 + 8 X2
St: 4 X1 + 6 X2 < 36
10 X1 + 7 X2 < 70
X1 and X2 > 0 and X1 integer

Solve using Branch and Bound. The methodology is very similar except the final solution will be where one of the integer values intersects the boundary of the feasible solution space.

As before, the LP relaxed solutions is: X1 = 5.25, X2 = 2.50, and Z = 51.50.

Then branching on X1 < 5 and X1 > 6, we find:

X1 < 5 (Node 2):
Max 6 X1 + 8 X2
St: 4 X1 + 6 X2 < 36
10 X1 + 7 X2 < 70
X1 < 5
X1 and X2 > 0 and X1 integer
DSWIN Solution:

Therefore, at both Nodes 2 and 3, X1 has an integer value. The value of Z for each node represents an upper bound on the value of the objective function for any further searching on those branches. Consequently, as Node 2 has the higher value of Z, it represents the optimal solution. Hence, X1 = 5, X2 = 2.67, and Z = 51.33.

DSWIN Mixed Integer Solution:

Branch and Bound Minimization:
The methodology is essentially the same except: The main difference is that the objective function value at each node is being minimized, therefore, the objective function value at the various nodes going down through the tree will get larger (or remain the same) rather than get smaller.

Example: Solve
Min 15 X1 + 10 X2 + 12 X3
St: 4 X1 + 6 X2 + 5 X3 > 60
3 X1 + X2 + X3 > 18
X1, X2, X3 > 0 and integer








DSWIN Solution:

Formulating Integer Programming Problems:
Either-Or Alternatives:
If either X1 or X2 is needed: X1 + X2 = 1
If there is a possibility that neither X1 or X2 is needed, X1 + X2 < 1

K Out of N alternatives:
For exactly 2 out of 5: X1 + X2 + X3 + X4 + X5 = 2
For at least 2 out of 5: X1 + X2 + X3 + X4 + X5 > 2
For no more than 2 out of 5: X1 + X2 + X3 + X4 + X5 < 2
For at least 2 but no more than 4:
X1 + X2 + X3 + X4 + X5 > 2
X1 + X2 + X3 + X4 + X5 < 4
If then Alternatives:
If X2 MAY necessitate X1, X1 > X2
In order to satisfy the requirement that the RHS consist solely of numerical quantity, we re-write this to: X1 - X2 > 0
If X2 REQUIRES X1, X1 - X2 = 0.