- Research activity in 2003
1. Development, implementation and experimentation of
global optimization algorithms in order to detect the minimal energy configuration
according to the Morse or Lennard-Jones potential function. The minimal energy
of a cluster of identical and uncharged atoms, where the energy between
any pair of atoms is represented by the Morse pair potential, is searched.
Morse clusters provide a though test system for global optimization algorithms.
Techniques for tranforming the Morse potential in order to increase efficiency
of optimization methods have been developed. The resulting combined methodes
have proved to be extremely powerful on very difficult instances from the
literature.
2. Analysis of objective functions with a special landscape and detection
of efficient methods for these problems. These methods are mostly related
to the Basin Hopping approach and are based on a smoothing transformation
of the objective function.
3. Undominated D.C. decomposition for nonconvex quadratic problems. D.C.
(Difference-of-Convex) decompositions are a well known method to derive bounds
for quadratic problems. Conditions for detecting so called undominated decompositions,
which lead to better bounds, have been developed.
4. Max-clique problems, i.e. finding the maximum clique (the complete
subgraph of a graph with highest cardinality) are very challenging problems
in combinatorial optimization. New optimization algorithms have been developed
for such problems; such algorithms are both powerful and simple, in that
they are comparable -- with respect to computational effort and solution
quality -- with the best known heuristic techniques, though they exibhit
considerably simpler structure.
5. The single-machine total tardiness problem calls for sequencing a number
of jobs on a limited-capacity machine in order to minimize the total (or
average) delay against given due dates. The most common sequencing heuristics
for this NP-hard problem have been investigated; arbitrarily bad approximation
ratios have been mathematically proved for each of them.
- 2003 Publications
Papers
M.Locatelli, "A note on the
Griewank test function", Journal of Global Optimization, 25, 169-174
(2003).
M.Locatelli, F.Schoen, "Efficient
algorithms for large scale global optimization: Lennard-Jones clusters",
Computational Optimization
and Applications, 26 (2): 173-190 (2003).
P.Fosser, R.Glantz, M.Locatelli, M.Pelillo, "Swap
strategies for graph matching", Lecture Notes in Computer Science,
2726, 142-153 (2003).
Chapters in books
M. Locatelli, F. SchoenGlobal Minimization of Lennard-Jones Clusters by a Two-Phase Monotonic
Method in Optimization and Industry: new frontiers, P.M.Pardalos and V.Korothkikh
(eds), 2003.
Conferences
F.Della Croce, A.Grosso, V.Th.Paschos, "Lower bounds
on the approximation ratios of leading heuristics for the single machine total
tardiness problem", 6th workshop on Models and Algorithms for Planning and
Scheduling Problems (MAPSP 03), Aussois, France, 2003, pp. 52-53.
