Objective as a Feature for Robust Search Strategies - GREYC codag Accéder directement au contenu
Communication Dans Un Congrès Année : 2018

Objective as a Feature for Robust Search Strategies

Résumé

In constraint programming the search strategy entirely guides the solving process, and drastically affects the running time for solving particular problem instances. Many features have been defined so far for the design of efficient and robust search strategies, such as variables' domains, constraint graph, or even the constraints triggering fails. In this paper, we propose to use the objective functions of constraint optimization problems as a feature to guide search strategies. We define an objective-based function, to monitor the objective bounds modifications and to extract information. This function is the main feature to design a new variable selection heuristic, whose results validate human intuitions about the objective modifications. Finally, we introduce a simple but efficient combination of features, to incorporate the objective in the state-of-the-art search strategies. We illustrate this new method by testing it on several classic optimization problems, showing that the new feature often yields to a better running time and finds better solutions in the given time.
Fichier principal
Vignette du fichier
OBS.pdf (1.62 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02118552 , version 1 (03-05-2019)

Identifiants

Citer

Anthony Palmieri, Guillaume Perez. Objective as a Feature for Robust Search Strategies. International Conference on Principles and Practice of Constraint Programming, Aug 2018, Lille, France. pp.328-344, ⟨10.1007/978-3-319-98334-9_22⟩. ⟨hal-02118552⟩
106 Consultations
144 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More