The authors study the experimental approximated solutions of three famous NP-complete optimization problems, the minimum vertex cover, the maximum independent set and the maximum clique, by using the Boltzmann machine neural network model. They treat the general case of all the problems that is the case when costs are associated to the vertices describing them, the case of cardinality becoming a particular case in the present approach. The model comprises a connection matrix which, for all the studied problems, captures efficiently the information about them (constraints, optimization function), this efficiency of the connected matrix being based on the relation between the local optima of the network’s defined energy and their feasible solutions. The numerical studies that have been performed verify also this efficiency. The obtained results provide an excellent experimental approximation ratio and are superior compared with the ones provided by a natural greedy heuristic algorithm.
