Contact email: gt04+@andrew.cmu.edu

Title: Solving Maximal Clique Problems By Using Variants of the Column
Subraction Method of Harche and Thompson
       (Tentative title which may be changed.)
Author:  Gerald L. Thompson, GSIA, Carnegie Mellon Univeristy,
Pittsburgh, Pa.  15213.

    In this paper we will consider the problem of finding a maximal
clique in a given graph in its equivalent form of finding a maximal
independent set in its complementary graph.  In its current form I have
not provided a subroutine in the program to change a graph into its
complementary graph, but that would be easy to do.

    The Maximal Independent Set problem in a graph G = (V, E) can stated
as the following integer program:

                Max ex | {Ax <= f, x belongs to [0,1]}
 
where A is the edge-vertex incidence matrix of G, e is a row vector of
ones, and f is a column vector of ones.  The linear programming
relaxation of this problem is obtained by replacing the conditions on x
by simply requiring each component of x to lie between 0 and 1.

    The column subtraction method of F. Harche and G. L. Thompson can be
applied to finding the solution to any zero-one integer programming
problem. The author (with others) have developed CSM codes for solving
set partitioning, set covering, set packing, logical inference, and
postman problems as well as the maximal independent set (clique) problem.

    An outline of how the CSM method works on an arbitrary problem P can
be stated as follows:

    1.  Solve  problem P by a heuristic code if possible, and save its answer.

    2.  Set up and solve the linear programming relaxation of  problem
P.  Let T be the final tableau of the solution.

    3.  Order the columns of T in nondecreasing order of reduced costs.

    4.  In order to fix a nonbasic variable (which is currently at 0) to
1, all that is necessary is to subtract the column which the nonbasic
variable labels in the final tableau T from the right hand side of T. 
(The proof of correctness of this rule is easy.)
    Using this technique, carry out a greedy branch and bound search,
using the heuristic bound found in Step 1. as the initial upper bound,
and replacing that bound by better bounds as they are found.  Here
greedy means use columns with small reduced costs in the search before
using columns with large reduced costs.

    Note that a forward step of the search, in which a variable is
changed from 0 to 1, requires the subtraction of one of the column of T
from its last one.  The backward step of the search, in which the
variable is changed from 1 back to 0 can be accomplished by simply
changing the value of a single pointer.  After making a forward step it
is also necessary to evaluate the current solution to see whether it is
a 0-1 solution, and this requires a single scan of the final column of
the tableau.  Each node of a search tree requires one forward step, one
evaluation step, and one backward step; it follows that the amount of
work needed for each node is very small compared to that required by
most BAB routines. Hence, we do not care if the method requires a large
number of search nodes, since they can be evaluated quickly.

    I have written a C code that implements this BAB search routine. 
With it I have constructed some maximal independent set problems that
are especially difficult, that it, they have a large gap between the
lower bound given by the LP relaxation and the optimal value.

    I also have written two other versions of the code that have
different ways of going through the search tree.  These can be
summarized as follows:
     (a)  The Iterative Deepening search strategy.  In this case we do
not calculate a heuristic solution as in (1) above, but simply carry out
a modified breadth first strategy.  First we generate all solutions that
are at the level of the initial lower bound, then all those that are at
level one above the initial lower bound, etc., stopping whenever we find
an integer solution for the first time, which must be optimal since we
have already evaluated all solutions having values less than that of the
integer solution found.  Note that in order to evaluate the solutions at
a given level we have to repeat all of the work needed to reach the
previous level.  This method is popular with computer science
researchers.
    (b)  The Change Tree search strategy.  This is a new strategy that I
have recently devised.  It is like the previous one except that we first
move to the desired level and then generate all solutions at that level.

    The final paper will include a general discussion of various
strategies for examining search trees.  In particular the two strategies
just described will be evaluated and reasons given for their differing
performances.

    I also plan to put these algorithms on the CM2 Connection Machine,
since such a machine could speed up the real time performance of the
algorithm considerably.  This will take some time, and completion date
for this phase of the research effort is difficult to predict.