  We present a physics inspired heuristic method for solving combinatorial
optimization problems. Our approach is specifically motivated by the desire to
avoid trapping in metastable local minima- a common occurrence in hard problems
with multiple extrema. Our method involves (i) coupling otherwise independent
simulations of a system ("replicas") via geometrical distances as well as (ii)
probabilistic inference applied to the solutions found by individual replicas.
The {\it ensemble} of replicas evolves as to maximize the inter-replica
correlation while simultaneously minimize the local intra-replica cost function
(e.g., the total path length in the Traveling Salesman Problem within each
replica). We demonstrate how our method improves the performance of rudimentary
local optimization schemes long applied to the NP hard Traveling Salesman
Problem. In particular, we apply our method to the well-known "$k$-opt"
algorithm and examine two particular cases- $k=2$ and $k=3$. With the aid of
geometrical coupling alone, we are able to determine for the optimum tour
length on systems up to $280$ cities (an order of magnitude larger than the
largest systems typically solved by the bare $k=3$ opt). The probabilistic
replica-based inference approach improves $k-opt$ even further and determines
the optimal solution of a problem with $318$ cities and find tours whose total
length is close to that of the optimal solutions for other systems with a
larger number of cities.
