A neural network for the minimum set covering problem

Mhand Hifi, CERMSEM
Vangelis Th. Paschos*, LAMSADE
Vassilis Zissimopoulos**, LIPN

Résumé. Dans ce papier, nous proposons un algorithme approché pour la résolution du problème de la couverture d'ensembles. L'algorithme s'appuie principalement sur la combinaison entre les réseaux de neurones, la machine de Boltzmann ainsi que quelques stratégies de la combinatoire. Nous comparons les solutions obtenues par le modèle aux solutions produites par deux algorithmes de la littérature : (i) l'algorithme glouton de Johnson et (ii) l'algorithme de Beasley qui utilise la relaxation Lagrangienne. Par ailleurs, nous proposons un schéma de décomposition polynomial afin de traiter les instances de grande taille. Finalement, nous montrons la relation existante entre le temps de convergence du modèle et la taille des instances du problème de couverture d'ensembles.
Mots clés : Optimisation combinatoire, machine de Boltzmann, réseaux de neurones, couverture d'ensemble.

Abstract. We solve approximately the weighted set covering problem by putting together a neural network model, the Boltzmann machine, and some combinatorial ideas. We compare the solutions provided by the network with the ones obtained using the greedy set covering heuristic and the Lagrangian heuristic developed by Beasley. Moreover, we use a simple and intuitive polynomial decomposition schema treating large instances by decomposing them into smaller ones. Finally, we report on the relation between the convergence time of the model and the size of the instances of set covering.
Keywords : Combinatorial optimization, Boltzmann machine, neural network, set covering.

JEL Classification : C44, C61, C63.

*LAMSADE, Université Paris-Dauphine, Place du Maréchal de Lattre de Tassigny, 75775 Paris Cedex 16, France.
**LIPN, Université Paris XIII, Avenue Jean Baptiste Clément, 93430 Villetaneuse, France.