A portable and scalable algorithm for a class of constrained combinatorial optimization problems

This paper presents a portable and scalable approach for a class of constrained combinatorial optimization problems (CCOPs) which requires to satisfy a set of constraints and to optimize an objective function simultaneously. In particular, this paper is focused on the class of CCOPs that admits a representation in terms of a square matrix of constraints C. The algorithm consists of a hybrid neural–genetic algorithm, formed by a Hopfield Neural Network (HNN) which solves the problem's constraints, and a Genetic Algorithm (GA) for optimizing the objective function. This separated management of constraints and optimization procedures makes the proposed algorithm scalable and robust. The portability of the algorithm is given by the fact that the HNN dynamics depends only on the matrix C of constraints. We show these properties of scalability and portability by solving three different CCOPs with our algorithm, the frequency assignment problem in a mobile telecommunications network, the reduction of the interference in satellite systems and the design of FPGAs with segmented channel routing architecture. We compare our results with previous approaches to these problems, obtaining very good results in all of them.