Approximate methods of discrete optimization
ad...@o2.pl
I've spent a lot of time trying to find the best possible way of
grouping approximate methods of discrete optimization. I must write a
work about them and the problem is that in all resources that I've
searched I couldn't find straight and simple division of that problems.
I know it's not that simple but I must somehow classify them all.
I managed to divide these problems with some book like this:
1 Local search methods
2 Ant algorithms
3 Descending search methods
4 Random search methods
5 Tabu search method
6 Adaptive memory search methods
7 Beam search methods
8 Path search methods
9 Evolutionary, genetic search methods
10 Threshold search methods
11 Scatter search method
12 Artificial intelligence methods
13 Simulated annealing method
14 Simulated jumping method
15 Expert systems methods
16 Multiagents methods
17 Neural networks methods
18 Randomized methods
19 Geometric method
20 Cultural algorithms
21 Memetic algorithms
22 Hybrid methods
23 Parallel methods
The problem is that:
1. I have that slight feeling that the division is not appropriate,
maybe too detailed on first level (and why only first level) - what do
you think, how should I modify this division?
2. I don't have many books in which there are descriptions of the
problems in that list - actually only two - documents on the Internet
are very often too detailed - they have descriptions of some
sophisticated algorithms used in exact situation - I'm looking for some
help, materials, docs, pdfs whatever that would help me to describe
approximate methods of discrete optimization.
If you have any materials or document that would cover the topic of
approximate method of DO, please send them to my email.
I am looking forward to your help,
Adam
Paul A. Rubin
Hi,
I'm not sure what distinction you have in mind between random search
methods (4) and randomized methods (18).
A number of the methods listed could be grouped under the heading of
metaheuristics. See, for instance,
http://www.metaheuristics.org/index.php?main=1. (I would also include
memetic algorithms under the heading of metaheuristics.)
Again, I'm not sure what you mean by parallel methods (23). If you're
referring to parallel processing, many (most?) (all??) of the methods
you list are candidates for parallel implementations.
/Paul
ad...@o2.pl
technique - my mistake. The same aplies to randomized methods - these
are those in which deterministic parts can be replaced by some random
elements and it gives us a better approximate solution to optimal - so
once again, it's technique. I deleted both and also create category '
Metaheuristics ' as you proposed. Now, it looks like this:
1 Metaheuristics
1.1 Local search methods
1.2 Simulated annealing method
1.3 Tabu search method
1.4 Evolutionary, genetic search methods
1.4.1 Cultural algorithms
1.5 Ant algorithms
1.6 Memetic algorithms
2 Descending search methods
3 Random search method (historically known as Monte Carlo method)
4 Adaptive memory search methods
5 Beam search methods
6 Path search methods
7 Threshold search methods
8 Scatter search method
9 Artificial intelligence methods
10 Simulated jumping method
11 Expert systems methods
12 Multiagents methods
13 Neural networks methods
14 Geometric method
15 Hybrid methods
1. I'm not sure if evolutionary methods equals genetic methods...
2. Hybrid methods (i.e. GA + LS) are also rather a kind of techniques,
but because of good results it's suitable to write about them
separately.
3. I put ' Cultural algorithms ' as a subclass of ' Evolutionary
methods '.
4. I've read about ' Constraint satisfaction (CS) ' as methods, but I
don't know where I should include them.
5. I've also read about ' Guided local search (GLS) '. Is it a special
case of ' Local search methods ' ?
Thanks for all suggestions,
Adam
Paul A. Rubin
> 1. I'm not sure if evolutionary methods equals genetic methods...
According to the wikipedia, GAs are a subset of EAs:
http://en.wikipedia.org/wiki/Evolutionary_algorithms.
> 4. I've read about ' Constraint satisfaction (CS) ' as methods, but I
> don't know where I should include them.
I've never quite figured out if "constraint satisfaction" (CS),
"constraint programming" (CP) and "constraint logic programming" (CLP)
are synonyms (although I'm pretty sure the second and third are).
Assuming for the moment they're all synonymous, I'm not sure if they fit
in here, in that they're not (necessarily) approximate methods.
Assuming sufficient time and memory (and an uninterrupted power supply),
CP algorithms will solve problems to optimality -- they're exhaustive,
in the same way that branch-and-cut is for integer/mixed-integer
programming problems.
That said, it's entirely possible that there are CP heuristics that are
not exhaustive. I don't recall seeing any, but then it's not my area.
> 5. I've also read about ' Guided local search (GLS) '. Is it a special
> case of ' Local search methods ' ?
I took a peek at http://cswww.essex.ac.uk/CSP/gls.html for a definition.
It certainly uses local search, but it seems to be a metaheuristic
rather than a heuristic.
/Paul
ad...@o2.pl
some suggestions how should I modify more the list of problems in the
3rd message, leave a note.
I started describing the problems according to the list in 3rd message.
It's easier to make a deduction to which group something belongs when
working with it.
Tim
Programming" originates from the early attempts at implementing
constraint-based problem solving that were often carried out by making
extensions to Prolog, the "classic" logic programming language. This
took hold quite well after the CHIP Esprit project ("Constraint
Handling In Prolog"?) in the early/mid 80's, and led to all sorts of
commercialised spin-offs including Cosytec's Chip, Imperial College
(IC-PARC)'s Eclipse, Bull's Charme, and others. This work used the
built-in backtracking search in Prolog augmented by explicit domain
reduction propagation algorithms with finite domains. There's still
plenty out there, and quite a few prolog implementations now include
some constraint programming support. Look at GNU prolog for example -
http://gnu-prolog.inria.fr/
In the meantime, of course, others were also doing constraint
programming in other languages (e.g. variants of Scheme, such as
Screamer) and solving constraint satisfaction problems. Out of this
other work come tools like ILOG Solver - but if you dig into the
internals of older versions of ILOG Solver (pre-Concert) it feels like
you are digging about inside a prolog-like virtual machine. I even
remember writing a sort-of mini-prolog using ILOG Solver 2.x many years
ago.
So I would say that CP and CLP are not quite synonymous - CLP should
rightly be considered a subset of CP. And CP is just one of the ways of
solving a CSP. But of course the boundaries are a bit fuzzy...
Just my 0.02 euros - keeping some history alive? Makes me feel quite
old!
Tim
ad...@o2.pl
discrete optimization, there are thousands of documents, especially
those concerning proposed algorithms. But I still haven't found the
document with an attempt to classify these problems. Maybe it's
impossible - everything is changing so quickly, dynamically. All the
time new methods, new algoritms, new trends...
By the way: Could someone tell me where to find some reliable tests
with which I could check effeciency of an approximate discrete
optimization algoritm?
Paul A. Rubin
>
> By the way: Could someone tell me where to find some reliable tests
> with which I could check effeciency of an approximate discrete
> optimization algoritm?
>
If you're looking for test problems (with known solutions, or at least
objective bounds), there are a number of libraries scattered around. I
believe one is hosted at the OR-Library, Imperial College, London. The
URL I have bookmarked is mscmga.ms.ic.ac.uk, but I'm not sure if it's
current.
Typically, though, you need to search for instances of a particular type
of problem (for instance, traveling salesperson, machine scheduling, ...).
/Paul