Abstract:

We present a new randomized algorithm for counting, rare-events 
simulation, uniform sampling on different regions, and approximating the 
solutions of quite general NP-hard combinatorial (integer) optimization 
problems. Similar to the existing randomized algorithms the proposed one 
is based on the MCMC (Gibbs) sampler equipped with importance sampler 
and it also uses a sequential sampling
plan to decompose a ``difficult'' problem into a sequence of ``easy'' ones.
The main differences between the existing and the proposed algorithm is 
that the latter one has a special device, called the ``cloning'' device, 
which makes our algorithm very fast and accurate. In particular it is 
well suited for solving problems associated with the Boltzmann 
distribution, like estimating the partition functions in an Ising model 
and for sampling random variables uniformly distributed on different 
convex bodies.
We present efficient numerical results, while solving quite general integer
and combinatorial optimization problems as well as counting ones, like 
SAT and Hamiltonian cycles.