In the recent past, many examples of hybrid applications have
been described and the adopted hybrid algorithms shown to provide
better results than pure algorithms based on only one technology.
Yet the number of cases in which cooperative strategies have been
applied remains very small compared to the number of cases in
which they could potentially prove useful.
There might be several explanations for this fact. First, most
work on cooperative optimization strategies has been focused either
on the resolution of a particular problem at hand or on the design
of generic software integration principles. A finer understanding
of what makes a cooperative strategy work on a particular application
and of the variants of the problem that could be solved well with
the same cooperative strategy would be needed to allow an efficient
generalization to similar yet different applications. Second,
cooperative strategies are hard to develop: (a) appropriate sub-models
or alternative models have to be designed and implemented, which
often takes more time than the design and implementation of a
unique model; (b) the design of the cooperative strategy requires
some understanding of what each component does, of the strengths
and weaknesses of different technologies (specific polynomial
algorithms, mathematical programming, constraint programming,
local search) for the resolution of different types of problems;
(c) cooperative strategies are hard to tune, probably just because
the number of parameters that can be tuned is much higher than
in the case of a "pure"strategy.
Given an optimization application, two complementary issues must
be considered. First, the application must be "efficient", i.e.,
provide a "good"solution within reasonable time and resource limits
(CPU, memory). Second, the application must be "robust" with respect
to three types of variations in the problem instances: variations
in problem size, variations in numerical characteristics, and
addition of side constraints. The goal of hybridization is to
improve either efficiency or robustness (or both) without sacrificing
the other.
Looking at examples from the literature, two generic cooperative
schemes emerge. The "decomposition"scheme consists in applying
one technique (the "slave") to a sub-problem of the overall problem,
in order to gain information. This information is then used by
another technique (the "master"), to solve the overall problem.
The sub-problem given to the slave may be a reduced problem with
less variables, an approximation, a relaxation, or a tightened
version of the overall problem. In some cases, the results given
by the slave may be used by the master to focus the overall search,
without any risk of missing the optimal solution. In other cases,
the results given by the slave may be used as a guide toward good
solutions, but do not strictly allow to reduce the search space.
In the "multiple search" scheme, two or more optimization techniques
are used in turn or in parallel to provide solutions to the full
problem. In the simplest case, each optimization component operates
independently from the others. In most cases, however, the solutions
found by one component and, more generally, information generated
by one component as part of its own optimization process, can
be used by other components to better focus subsequent search.
In the end, it appears that the reasons for the success of these
two cooperative schemes are highly related to the concepts of
diversification (in the methods used to explore the search space),
and intensification (on promising parts of the search space).
Further work on these concepts may actually convey a better understanding
of what makes instances of these two schemes work well on specific
problems.
