Combinatorial optimization algorithms
We develop algorithms for tackling combinatorial optimization problems, and
analyze their properties and relative merits.
They are then sometimes used to understand the statistical
properties of the optimum, low cost solutions, or energy landscapes.
Keywords:
Local search, simulated annealing, iterated local search,
genetic algorithms, renormalization, multilevel,
parallel and distributed computation, PVM.
Systems investigated:
Traveling salesman problems, graph bipartitioning problems,
maxcut (spin glasses).
Publications in reverse chronological order:

O.C. Martin,
Probing spin glasses with heuristic optimization algorithms,
Chapter in "New Optimization Algorithms in Physics",
Eds. A. K. Hartmann and H. Rieger, Wiley VCH Verlag Berlin (May 2004).
This 24 page chapter surveys some heuristic algorithms and how they can be
used to study energy landscapes of different spin glass models.
The publisher authorized a 3 page
summary to be posted electronically.

H.R. Lourenco, O.C. Martin and T. Stutzle,
Iterated Local Search ,
In "Handbook of Metaheuristics", Ed. F. Glover
and G. Kochenberger,
International Series in Operations Research & Management Science,
volume 57, p 321353 (2002), Kluwer.
This is a survey of "Iterated Local Search", a general purpose
metaheuristic for finding good solutions of combinatorial
optimization problems. It is based on building a sequence of
(locally optimal) solutions by: (1) perturbing the current solution;
(2) applying local search to that modified solution. At a high level,
the method is simple, yet it allows for a detailed use of
problemspecific properties. After giving a general framework, we
cover the uses of Iterated Local Search on a number of
well studied problems.

J. Houdayer and O.C. Martin,
A hierarchical approach for computing spin glass ground states,
Phys. Rev. E 64, 056704 (2001).
We describe a numerical algorithm for computing spin glass ground
states with a high level of reliability. The method uses a population
based search and applies optimization on multiple scales. Benchmarks
are given leading to estimates of the performance on large lattices.

G.R. Schreiber and O.C. Martin,
Cut Size Statistics of Graph Bisection Heuristics.
SIAM Journal on Optimization 10(1), p231251
(1999).
We investigate the statistical properties of cut sizes generated
by heuristic algorithms which solve approximately the graph bisection
problem. On an ensemble of sparse random graphs, we find numerically
that the distribution of cut sizes found by ``local'' algorithms becomes
peaked as the number of vertices in the graphs becomes large. Evidence
is given that this distribution tends towards a Gaussian whose mean
and variance scales linearly with the number of vertices of the graphs.
Given the distribution of cut sizes associated with each heuristic,
we provide a ranking procedure which takes into account both the
quality of the solutions and the speed of the algorithms. This procedure
is demonstrated for a selection of local graph bisection heuristics.

J. Houdayer and O.C. Martin,
Renormalization for Discrete Optimization,
Phys. Rev. Lett. 83(5) 10301033 (1999).
The renormalization group has proven to be a very powerful
tool in physics for treating systems with many length scales. Here
we show how it can be adapted to provide a new class of algorithms
for discrete optimization. The heart of our method uses renormalization
and recursion, and these processes are embedded in a genetic
algorithm. We perform tests on the traveling salesman and
the spin glass problems. The results
show that our ``genetic renormalization algorithm'' is extremely powerful.

O.C. Martin and S.W. Otto,
Combining Simulated Annealing with Local Search Heuristics.
Annals of Operations Research 63, 5775
(1996).
A general presentation of our Chained Local Optimization (CLO)
methodology is given and then developed for the TSP and GPP.
We have parallelized these two codes using the PVM protocole leading
to near linear speedup on a heterogeneous network of workstations.

O.C. Martin and S.W. Otto,
Partitioning
of Unstructured Meshes for Load Balancing.
Concurrency: Practice and Experience 7(4)
p303314 (1995).
This paper focuses on the graph bipartitioning problem
in the context of unstructured meshes. We chain together
local optimizations (small steps) to generate large step Markov chains,
a procedure we call Chained Local Optimization.

O. Martin, S.W. Otto and E.W. Felten,
Largestep
Markov chains for the TSP incorporating local search heuristics.
Operations Research Letters 11
p219224 (1992).
This is a shorter version of the next paper and is
written for the operation
research community, showing that our heuristic for the TSP is a
new champion.

O. Martin, S.W. Otto and E.W. Felten,
Largestep
Markov chains for the traveling salesman problem.
Complex Systems 5(3)
299326 (1991).
We show how simulated annealing can be greatly improved
by applying a quench before applying the accept/reject rule, allowing
one to use large steps and maintain good acceptance.
This procedure corresponds to an enhanced parthenogenetic algorithm.
The method is applied with great success to the TSP; we also show
how optimization at the population level can be introduced.
LPTMS Home Page
IPN Home Page
Olivier MARTIN Home Page
Last modified: May 2006
in anti spam format: olivier adothere martin (at sign) upsud adotthere fr
http://ipnweb.in2p3.fr/lptms/membres/martino