Mapping and Combining Combinatorial Problems into Energy Landscapes via Pseudo-Boolean Constraints

摘要

This paper introduces a novel approach to the specification of hard combinatorial problems as pseudo-Boolean constraints. It is shown (ⅰ) how this set of constraints defines an energy landscape representing the space state of solutions of the target problem, and (ⅱ) how easy is to combine different problems into new ones mostly via the union of the corresponding constraints. Graph colouring and Traveling Salesperson Problem (TSP) were chosen as the basic problems from which new combinations were investigated. Higher-order Hopfield networks of stochastic neurons were adopted as search engines in order to solve the mapped problems.