A replica exchange Markov Chain Monte Carlo (MCMC) engine is developed with automatic temperature adjustment for solving combinatorial optimization problems by minimizing the energy of the Ising model. The automatic temperature adjustment scheme ensures that the MCMC process is optimized at every stage of the execution. This approach is performed by dynamically adjusting temperatures of all replicas, based on the properties of any given problem, in addition to the capability of automatically inserting new replicas or removing any existing replicas to achieve the best possible resource efficiency and execution time. The proposed algorithm is integrated with parallel evaluation of energy increment and update scheme. The engine is implemented on the FPGA platform with a capacity of running up to 42 replicas in pipeline, each running 1024 fully-connected Ising spins in parallel. The performance of the hardware is examined with three different classes of problems, Vertex Cover, Maximum-Cut, and Travelling Salesman using the engine in three modes, simulated annealing, with replica exchange while the adjustments are turned on or off. Up to 16x speedup is observed by turning on the replica exchange capability in addition to the advantage of eliminating the challenging process of finding an optimal annealing schedule for simulated annealing process.