An Interval Filtering Operator for Upper and Lower Bounding in Constrained Global Optimization

Olivier Sans 1 Remi Coletta 1, 2 Gilles Trombettoni 1
1 COCONUT - Agents, Apprentissage, Contraintes
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : This paper presents a new interval-based operator for continuous constrained global optimization. It is built upon a new filtering operator, named TEC, which constructs a bounded subtree using a Branch and Contract process and returns the parallel-to-axes hull of the leaf domains/boxes. Two extensions of TEC use the information contained in the leaf boxes of the TEC subtree to improve the two bounds of the objective function value: (i) for the lower bounding, a polyhedral hull of the (projected) leaf boxes replaces the parallel-to-axes hull, (ii) for the upper bounding, a good feasible point is searched for inside a leaf box of the TEC subtree, following a look-ahead principle. The algorithm proposed is an auto-adaptive version of TEC that plays with both extensions according to the outcomes of the upper and lower bounding phases. Experimental results show a significant speed-up on several state-of-the-art instances.
Document type :
Conference papers
Complete list of metadatas

Cited literature [20 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01466843
Contributor : Joël Quinqueton <>
Submitted on : Tuesday, February 14, 2017 - 4:44:00 PM
Last modification on : Thursday, February 7, 2019 - 2:20:56 PM
Long-term archiving on : Monday, May 15, 2017 - 6:07:09 PM

File

tec_ictai_2016.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Olivier Sans, Remi Coletta, Gilles Trombettoni. An Interval Filtering Operator for Upper and Lower Bounding in Constrained Global Optimization. ICTAI: International Conference on Tools with Artificial Intelligence, Nov 2016, San José, CA, United States. pp.218-225, ⟨10.1109/ICTAI.2016.0042⟩. ⟨lirmm-01466843⟩

Share

Metrics

Record views

187

Files downloads

239