Finding Solutions by Finding Inconsistencies
| Autor: | Charlotte Truchet, Marie Pelleau, Antoine Miné, Ghiles Ziat |
|---|---|
| Přispěvatelé: | Algorithmes, Programmes et Résolution (APR), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Théorie, Algorithmes et Systèmes en Contraintes (TASC ), Laboratoire des Sciences du Numérique de Nantes (LS2N), IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Nantes - UFR des Sciences et des Techniques (UN UFR ST), Université de Nantes (UN)-Université de Nantes (UN)-École Centrale de Nantes (ECN)-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Université de Nantes (UN)-Université de Nantes (UN)-École Centrale de Nantes (ECN)-Centre National de la Recherche Scientifique (CNRS) |
| Rok vydání: | 2018 |
| Předmět: |
Computer science
[INFO.INFO-OH]Computer Science [cs]/Other [cs.OH] 020207 software engineering 02 engineering and technology Solver Linear subspace Set (abstract data type) Constraint (information theory) Operator (computer programming) 0202 electrical engineering electronic engineering information engineering Constraint programming 020201 artificial intelligence & image processing Focus (optics) Algorithm Subspace topology |
| Zdroj: | Principles and Practice of Constraint Programming-24th International Conference, CP 2018, Lille, France, August 27-31, 2018, Proceedings Lecture Notes in Computer Science ISBN: 9783319983332 CP Lecture Notes in Computer Science Lecture Notes in Computer Science-Principles and Practice of Constraint Programming CP 2018-24th International Conference on Principles and Practice of Constraint Programming CP 2018-24th International Conference on Principles and Practice of Constraint Programming, Aug 2018, Lille, France. pp.1-16 |
| ISSN: | 0302-9743 1611-3349 |
| DOI: | 10.1007/978-3-319-98334-9_28 |
| Popis: | International audience; In continuous constraint programming, the solving process alternates propagation steps, which reduce the search space according to the constraints, and branching steps. In practice, the solvers spend a lot of computation time in propagation to separate feasible and infeasi-ble parts of the search space. The constraint propagators cut the search space into two subspaces: the inconsistent one, which can be discarded, and the consistent one, which may contain solutions and where the search continues. The status of all this consistent subspace is thus indeterminate. In this article, we introduce a new step called elimination. It refines the analysis of the consistent subspace by dividing it into an indeterminate one, where the search must continue, and a satisfied one, where the constraints are always satisfied. The latter can be stored and removed from the search process. Elimination relies on the propagation of the negation of the constraints, and a new difference operator to efficiently compute the obtained set as an union of boxes, thus it uses the same representations and algorithms as those already existing in the solvers. Combined with propagation, elimination allows the solver to focus on the frontiers of the constraints, which is the core difficult part of the problem. We have implemented our method in the AbSolute solver, and present experimental results on classic benchmarks with good performances. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|