Bonjour,

> > Could you send around the source code to this?  I intuitively knew
> > that such performance results were likely, but had never had such
> > a convincing example to wave at people.
>
> Yes. The implementation of traveling salesman given in my book is
> another example which is several orders of magnitude faster than the
> C/C++/Fortran implementations given in all of the other text books
> that I have read.

Branch-and-bound algorithms (pure integer, not LP based) are good
candidates for important speed-ups due to data persistence : when you
backtrack it is most of the time much faster to restart from a
memorized data structure than to reconstruct it, specially with
structured data like ordered sets, graphs, etc.

Generally speaking, the _good_ paradigm to program B&B solvers for
NP-hard problems is mixed functional/imperative programming (in other
words ML), because you benefit from fast recursion, data persistence,
garbage collection while you use very few floating point computations.

Actually, most of the commercial C/C++ libraries for constraint
programming (= integer branch and bound) include a 'functional layer'
that contains one or several garbage collectors, persistent data
structures, a system to make persistent user-defined data structures,
function objects, etc.

Winning against a mixed imperative/functional implementation in e.g.
C/C++ require a lot of low-level implementation work - and you will
end anyway implementing some kind of 'functional core'. Worse,
algorithmic wins (better algorithms) are most of the time several
order of magnitude superior than implementation wins (better
implementation).

Therefore it is also more convenient to use a high level language like
Caml in order to focalize on algorithms rather than implementation.


        Diego Olivier