Skip to Main content Skip to Navigation
Journal articles

Adaptive constructive interval disjunction: algorithms and experiments

Bertrand Neveu 1, 2, 3 Gilles Trombettoni 4 Ignacio Araya 5
2 imagine [Marne-la-Vallée]
LIGM - Laboratoire d'Informatique Gaspard-Monge, CSTB - Centre Scientifique et Technique du Bâtiment, ENPC - École des Ponts ParisTech
4 COCONUT - Agents, Apprentissage, Contraintes
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : An operator called CID and an efficient variant 3BCID were proposed in 2007. For the numerical CSP handled by interval methods, these operators compute a partial consistency equivalent to Partition-1-AC for the discrete CSP. In addition to the constraint propagation procedure used to refute a given subproblem, the main two parameters of CID are the number of times the main CID procedure is called and the maximum number of sub-intervals treated by the procedure. The 3BCID operator is state-of-the-art in numerical CSP, but not in constrained global optimization, for which it is generally too costly. This paper proposes an adaptive variant of 3BCID called ACID. The number of variables handled is auto-adapted during the search, the other parameters are fixed and robust to modifications. On a representative sample of instances, ACID appears to work efficiently, both with the HC4 constraint propagation algorithm and with the state-of-the-art Mohc algorithm. Experiments also highlight that it is relevant to auto-adapt only a number of handled variables, instead of a specific set of selected variables. Finally, ACID appears to be the best interval constraint programming operator for solving and optimization, and has been therefore added to the default strategies of the Ibex interval solver.
Document type :
Journal articles
Complete list of metadata

Cited literature [25 references]  Display  Hide  Download

https://hal-enpc.archives-ouvertes.fr/hal-01119535
Contributor : Bertrand Neveu <>
Submitted on : Thursday, October 18, 2018 - 12:39:01 PM
Last modification on : Wednesday, May 26, 2021 - 12:30:02 PM
Long-term archiving on: : Saturday, January 19, 2019 - 2:01:14 PM

File

acid_constraints_2015.pdf
Files produced by the author(s)

Identifiers

Citation

Bertrand Neveu, Gilles Trombettoni, Ignacio Araya. Adaptive constructive interval disjunction: algorithms and experiments. Constraints, Springer Verlag, 2015, 20 (7), pp.452-467. ⟨10.1007/s10601-015-9180-3⟩. ⟨hal-01119535⟩

Share

Metrics

Record views

567

Files downloads

314