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:

Systems investigated:

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 321-353 (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 problem-specific 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), p231-251 (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) 1030-1033 (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, 57-75 (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 speed-up 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) p303-314 (1995). This paper focuses on the graph bi-partitioning 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, Large-step Markov chains for the TSP incorporating local search heuristics. Operations Research Letters 11 p219-224 (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, Large-step Markov chains for the traveling salesman problem. Complex Systems 5(3) 299-326 (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 partheno-genetic 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