Enumerating 0-1 integer programs.

Enumerating 0-1 Integer Programs

We know that any problem which in NP can be stated as an 0-1 integer programming problem since 0-1 integer programming is NP-complete. In addition, we know how to easily map the satisfiability problem into the 0-1 integer programming problem. Therefor, we may turn any problem in NP into an integer program with the mapping:

This is often not too difficult to implement. All we do is state the problem in the language of predicate calculus and then either attempt to satisfy the clauses we developed or map it into 0-1 integer programming and then solve that problem.

This suggests an intriguing method of finding solutions to problems. All we need do is to compute the objective function for all combinations of zero and one for all variables and record the best feasible solution. Since each variable is restricted to values of zero or one (or, in the case of predicate calculus clauses, true and false), the number of solutions seems not as large as when we allow arbitrary integer values. This however is misleading since in mapping arbitrary integer programming problems into 0-1 integer programming problems there can be a significant variable explosion.

Let us examine this. If we think of 1 as true and 0 as false, then enumerating all candidates for a feasible integer programming solution is exactly the same as enumerating all subsets of the set of variables. In this manner we interpret a subset of the variables such as {x₂, x₄} as representing the solution where x₂ = x₄ = 1 and all other variables have values of zero. Thus any enumeration of subsets of a set of variables provides all possible candidates for feasible solutions. We even know exactly how many cases make up the enumeration. It is the same as the size of a truth table for an n variable formula, namely 2ⁿ.

A simple example of an enumeration of the subsets of four variables is pictured as a graph in figure 1. The subsets are ordered by set inclusion with the empty set at the top and the set of all variables: {x₁ , x₂ , x₃ , x₄} at the bottom.

Figure 1 - Combinations of four Variables

One of the first enumeration methods which comes to mind is a depth-first search of the graph in figure 1. To do this, we examine all combinations of variables where x₁ is set to true or one, then all combinations where x₂ is set to true or one, but x₁ is false or zero, and so forth. The tree in figure 2 is the corresponding depth-first search tree.

Figure 2 - Depth First Search Tree for four Variables

If we look at combinations of variables as the quadruples <x₁, x₂, x₃, x₄>, then depth-first search takes us through the sequence:

0000,
1000, 1100, 1110, 1111, 1101, 1010, 1011, 1001,
0100, 0110, 0111, 0101,
0010, 0011,
0001

Note that we first check the case where all variables are zero, then fix x₁ at one and do a depth-first search of its subtree. Next we fix x₁ at zero and x₂ at one and search that subtree. This continues until the entire tree has been visited. The recursive procedure presented in figure 3 does exactly this when called with i set to 1 using z(x₁, ... , x_n) as the objective function for the problem we are optimizing.

Figure 3 - Finding the Optimum by Depth-First Enumeration

Even though a depth-first search such as that described in figure 3 is essentially the technique we shall use to find optimum solutions, we should examine the other obvious graph search technique, namely breadth-first search. In this method, we visit the nodes of the search tree of figure 2 in the following order:

0000,
1000, 0100, 0010, 0001,
1100, 1010, 1001, 0110, 0101, 0011,
1110, 1101, 1011, 0111,
1111

A quick inspection reveals that this is just examining combinations of no variables, one variable, two variables, three variables, and four variables. Further examination shows us the way to do this recursively. All combinations of k variables can be found by setting x_i to one for i from one to n-k+1, fixing x₁, ... , x_i , and looking at all combinations of k-1 variables from the sequence x_i+1 , ... , x_n

The algorithm of figure 4 works provides this sequence when called from a loop which sets k to zero through n.

Figure 4 - Finding the Optimum by Breadth-First Enumeration

This seems to be reasonable, but maybe if we are clever, we might restrict our examination to a portion of the depth-first search tree. At each vertex we could decide whether or not to descend further. For example, if setting a variable to 1 will not lead to:

a) a feasible solution, or
b) a better objective function value,

then we should not continue on down that portion of the search tree any further. Another decision which might reduce enumeration time is to carefully select which branch of the graph (in figure 1) to pursue so that we go directly to the subtree that has the greatest chance of containing an optimum solution.

Let us examine this with a very simple problem. Consider the problem shown in figure 5. This is one which was mapped from satisfiability to 0-1 integer programming.

	minimize z = 2x₁ + 4x₂ + x₃
	subject to the conditions:
(x₁ , x₂)	x₁ + x₂ ³ 1
(x₂ , x₃ , x₄)	x₂ + x₃ + x₄ ³ 1
(x₁ , x₄)	x₁ + x₄ ³ 1
	where all x_i Î {0,1}

Figure 5 - Clauses and a 0-1 Integer Programming Problem

We first check out the solution where all x_i are set to zero and find that not a single equation (or clause) is satisfied and the objective function is zero. If we set each variable (individually) to 1 then we observe the following for the problem.

Action:	x₁ = 1	x₂ = 1	x₃ = 1	x₄ = 1
Equations Satisfied:	2	2	1	2
Objective Function:	2	4	1	0

Obviously setting x₁, x₂, or x₄ to 1 will improve the values of the constraints the most. Setting x₂ to 1 however, improves the objective function the most. Based upon this, let us rearrange our depth-first search tree as indicated in figure 6.

Figure 6 - Modified Search Tree

At this point we shall set fix the value of x₂ as 1 and proceed. Note that only the second constraint is violated now. Thus setting any of the other variables to 1 might help. Evaluating the these actions provides:

Action:	x₁ = 1	x₃ = 1	x₄ = 1
Equations Satisfied:	3	2	3
Objective Function:	6	5	4

Again, we have a tie when we consider satisfying the constraints. Setting x₁, or x₄ to one both provide feasible solutions. Taking x₁ and x₂ as one provides us with a feasible solution with the best objective function value, namely six. We now rearrange the search tree once more to reflect the priority of setting variables to one and get the tree of figure 7.

Figure 7 - The New Search Tree

Setting additional variables to 1 will not satisfy any more equations, but does bring a better value for the objective function.

Action:	x₃ = 1	x₄ = 1
Equations Satisfied:	3	3
Objective Function:	7	6

Setting x₁, x₂, and x₃ as one gives us the most improvement in the objective function, so we shall do that. Continuing in this manner for the entire enumeration provides the search tree depicted in figure 8.

Figure 8 - The Rearranged Depth-First Search Tree

In the search tree, feasible solutions occur at the shaded nodes and the value of the objective function is provided for each combination of variables. The search tree was rearranged so that feasible solutions (or combinations of variables closest to feasible solutions) were examined first and these in turn, were ordered by the value of the objective function at each level.

Note that searching could be terminated when the objective function reached seven for the <x₁, x₂, x₃> combination since that is the maximum value that can be achieved. In general however things are not this simple, but one should always watch for this to happen.

Developing the algorithm is not very difficult. As before, we use depth first search on the graph of Figure 1, but this time we are smarter about selecting the branches to go down. Thus we must keep track of the variables which we set as we traverse the search tree. One way to do this is to order the variables at each step as was done above.

It should be noted that ordering the variables requires some computation time. Before implementing a clever search algorithm, one should consider this and compare the added computation to that of much simpler search techniques.