Objective as a Feature for Robust Search Strategies
| Autor: | Anthony Palmieri, Guillaume Perez |
|---|---|
| Přispěvatelé: | Equipe CODAG - Laboratoire GREYC - UMR6072, Groupe de Recherche en Informatique, Image et Instrumentation de Caen (GREYC), Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU)-Normandie Université (NU)-Université de Caen Normandie (UNICAEN), Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia-Antipolis (I3S) / Equipe CEP, Modèles Discrets pour les Systèmes Complexes (Laboratoire I3S - MDSC), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA) |
| Jazyk: | angličtina |
| Rok vydání: | 2018 |
| Předmět: |
060201 languages & linguistics
Mathematical optimization Optimization problem Computer science Process (engineering) Heuristic (computer science) media_common.quotation_subject Feature selection 06 humanities and the arts 02 engineering and technology [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI] Feature (computer vision) Constraint graph 0602 languages and literature 0202 electrical engineering electronic engineering information engineering Constraint programming 020201 artificial intelligence & image processing [INFO]Computer Science [cs] Function (engineering) media_common |
| Zdroj: | Objective as a Feature for Robust Search Strategies International Conference on Principles and Practice of Constraint Programming International Conference on Principles and Practice of Constraint Programming, Aug 2018, Lille, France. pp.328-344, ⟨10.1007/978-3-319-98334-9_22⟩ Lecture Notes in Computer Science ISBN: 9783319983332 CP |
| Popis: | International audience; 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|