Boosting incomplete search with conflict learning

Amélioration des méthodes de recherche incomplète par des techniques d'apprentissage de conflits

Trong-Hieu Tran (1) , Cédric Pralet (2) , Hélène Fargier (1, 3)

1 IRIT-ADRIA - Argumentation, Décision, Raisonnement, Incertitude et Apprentissage
2 DTIS, ONERA, Université de Toulouse [Toulouse]
3 CNRS - Centre National de la Recherche Scientifique

In this paper, we introduce an ongoing work regarding a hybrid approach usable for obtaining high quality solutions to large-scale combinatorial optimization problems. This approach divides the process of solving a global problem into a master process that performs constraint-based search and a slave process that uses specific incomplete search techniques. In this hybrid architecture, the master level takes advantage of the conflicts discovered during incomplete search at the slave level, and reciprocally enhances the efficiency of the incomplete search since conflicts collected by the master level are used to avoid visiting the same parts of the search space over and over again. One of the novelties of this work is that the conflicts are memorized over the long-term in compact data structures, namely OBDDs or MDDs. The experimental results obtained on OPTW and FJSP instances show that even in our preliminary implementation, this kind of approach can reach some best-known results.

Mots clés: incomplete search; knowledge compilation; conflict learning; GRAS

Mots clés: OPTIMISATION COMBINATOIRE; EXPLICATION; RECHERCHE INCOMPLÈTE

Domaines: Sciences de l'ingénieur [physics]; Physique [physics]

Trong-Hieu Tran, Cédric Pralet, Hélène Fargier. Boosting incomplete search with conflict learning. CP 2024, Sep 2024, Gérone, Spain. ⟨10.4230/LIPIcs.CP-DP.2021.7⟩. ⟨hal-04778224⟩