Adaptive Constructive Interval Disjunction

Bertrand Neveu (1, 2, 3) , Gilles Trombettoni (4)

1 LIGM - Laboratoire d'Informatique Gaspard-Monge
2 imagine [Marne-la-Vallée]
3 ENPC - École des Ponts ParisTech
4 COCONUT - Agents, Apprentissage, Contraintes

An operator called CID and an efficient variant 3BCID were proposed in 2007. For numerical CSPs handled by interval methods, these operators compute a partial consistency equivalent to Partition-1-AC for discrete CSPs. The two main 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 solving, but not in constrained global optimization. This paper proposes an adaptive variant of 3BCID. 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 be the best approach in solving and optimization, and has been added to the default strategies of the Ibex interval solver.

Mots clés: Interval constraint programming

Domaines: Informatique [cs]; Recherche opérationnelle [cs.RO]

Bertrand Neveu, Gilles Trombettoni. Adaptive Constructive Interval Disjunction. ICTAI: International Conference on Tools with Artificial Intelligence, Nov 2013, Washington, DC, United States. pp.900-906, ⟨10.1109/ICTAI.2013.138⟩. ⟨hal-00936654⟩