%A Ioannis T. Christou
%A Wayne Martin
%A Robert R. Meyer
%T Genetic Algorithms as Multi-Coordinators in Large-Scale Optimization
%D December 1996
%R 96-14
%I COMPUTER SCIENCES DEPARTMENT, UNIVERSITY OF WISCONSIN
%C MADISON, WI
%X
We present high-level, decomposition-based algorithms
for large-scale block-angular optimization problems containing integer
variables, and demonstrate
their effectiveness in the solution of large-scale graph partitioning
problems.
These algorithms
combine the subproblem-coordination paradigm (and lower bounds)
of price-directive decomposition methods
with knapsack and genetic approaches to the utilization of ``building
blocks"
of partial solutions.
Even for graph partitioning problems
requiring billions of variables in a standard 0-1 formulation,
this approach produces high-quality solutions (as measured by deviations
from an easily computed lower bound), and substantially
outperforms widely-used graph partitioning techniques based on
heuristics and spectral methods.