@device(postscript)
@libraryfile(Mathematics10)
@libraryfile(Accents)
@style(fontfamily=timesroman,fontscale=11)
@pagefooting(immediate, left "@c<Technical Report 1996>",
center "@c<Computer Science>",
right "@c<Carnegie Mellon>")
@heading(Design of Maximum-Cardinality and Maximum-Weight
Clique Heuristics with Applications)
@heading(CMU-CS-96-127)
@center(@b(William J. Niehaus))
@center(May 1996 - Ph.D. Thesis)
@center(FTP: Unavailable)
@blankspace(1)
@begin(text)

In this thesis, we explore new heuristics for the maximum-cardinality
and the maximum-weight clique problems. These heuristics utilize
efficient procedures to solve the problems optimally on special
subgraphs of the original graph @y(M) those induced by the union of two
known cliques.  In the unweighted case, this subproblem is solved by
using bipartite matching in the complement graph.  In the vertex-weighted 
case, this subproblem is solved by finding minimum cuts in a network
easily derivable from the bipartite, complement graph.
We present these efficient procedures, and show how to organize repeated
calls to them to produce heuristics which perform well on most classes
of graphs.

We also explore genetic algorithms which incorporate these same procedures
into new heuristics that find good solutions faster than our original
heuristics.  Aggarwal, Orlin, and Tai recognized that our operation on a
pair of cliques can be considered an "optimized cross-over" step in a
genetic algorithm.  We consider variations in each element of their genetic
algorithm @y(M) mutation, selection, and population replacement @y(M) and
develop a steady-state genetic algorithm which outperforms it competitors
on most problems.

Finally, we apply our clique heuristics to produce good solutions to another
classical optimization problem, the set-partitioning problem.  We start with
our basic heuristic for the maximum-weight clique problem, and add several
features which help the heuristic find better set-partitioning solutions.
We develop a heuristic that often finds better solutions than CPLEX
finds (in long but incomplete runs) on a collection of difficult
set-partitioning problems.

Throughout the thesis, computational results testify to the effectiveness
of our heuristics both for the maximum clique problems and for the
set-partitioning problem.

@blankspace(2line)
@begin(transparent,size=10)
@b(Keywords:@ )@c<Heuristic, maximum-clique, maximum matching,
set-partitioning, genetic algorithms, optimized crossover>
@end(transparent)
@blankspace(1line)
@end(text)
@flushright(@b[(160 pages)])