Bertrand Neveu

EAAI Journal 2021 Journal Article

Learning and focusing strategies to improve ACO that solves CSP

• Nicolás Rojas-Morales
• María-Cristina Riff
• Bertrand Neveu

AAAI Conference 2011 Conference Paper

Inner Regions and Interval Linearizations for Global Optimization

• Gilles Trombettoni
• Ignacio Araya
• Bertrand Neveu
• Gilles Chabert

Researchers from interval analysis and constraint (logic) programming communities have studied intervals for their ability to manage infinite solution sets of numerical constraint systems. In particular, inner regions represent subsets of the search space in which all points are solutions. Our main contribution is the use of recent and new inner region extraction algorithms in the upper bounding phase of constrained global optimization. Convexification is a major key for efficiently lower bounding the objective function. We have adapted the convex interval taylorization proposed by Lin & Stadtherr for producing a reliable outer and inner polyhedral approximation of the solution set and a linearization of the objective function. Other original ingredients are part of our optimizer, including an efficient interval constraint propagation algorithm exploiting monotonicity of functions. We end up with a new framework for reliable continuous constrained global optimization. Our interval B&B is implemented in the interval-based explorer Ibex and extends this free C++ library. Our strategy significantly outperforms the best reliable global optimizers.

AAAI Conference 2010 Conference Paper

Exploiting Monotonicity in Interval Constraint Propagation

• Ignacio Araya
• Gilles Trombettoni
• Bertrand Neveu

We propose in this paper a new interval constraint propagation algorithm, called MOnotonic Hull Consistency (Mohc), that exploits monotonicity of functions. The propagation is standard, but the Mohc-Revise procedure, used to filter/contract the variable domains w. r. t. an individual constraint, uses monotonic versions of the classical HC4-Revise and BoxNarrow procedures. Mohc-Revise appears to be the first adaptive revise procedure ever proposed in (interval) constraint programming. Also, when a function is monotonic w. r. t. every variable, Mohc-Revise is proven to compute the optimal/sharpest box enclosing all the solutions of the corresponding constraint (hull consistency). Very promising experimental results suggest that Mohc has the potential to become an alternative to the state-of-the-art HC4 and Box algorithms.

EAAI Journal 2009 Journal Article

A revision of recent approaches for two-dimensional strip-packing problems

• María Cristina Riff
• Xavier Bonnaire
• Bertrand Neveu

IJCAI Conference 2007 Conference Paper

• Carlos Grand
• oacute; n
• Gilles Chabert
• Bertrand Neveu

This paper deals with systems of parametric equations over the reals, in the framework of interval constraint programming. As parameters vary within intervals, the solution set of a problem may have a non null volume. In these cases, an inner box (i. e. , a box included in the solution set) instead of a single punctual solution is of particular interest, because it gives greater freedom for choosing a solution. Our approach is able to build an inner box for the problem starting with a single point solution, by consistently extending the domain of every variable. The key point is a new method called generalized projection.

IJCAI Conference 2003 Conference Paper

Algorithms for Identifying Rigid Subsystems in Geometric Constraint Systems

• Christophe Jermann
• Bertrand Neveu
• Gilles Trombettoni

The structural rigidity property, a generalization of Laman's theorem which characterizes rigid bar frameworks in 2D, is generally considered a good approximation of rigidity in geometric constraint satisfaction problems (GCSPs). However, it may fail even on simple GCSPs because it does not take geometric properties into account. In this paper, we question the flow-based algorithm used by Hoffmann et ai to identify rigid subGC- SPs. We show that this algorithm may fail because of the structural rigidity, but also by design. We introduce a new flow-based algorithm which uses Jermann et al. 'S characterization of rigidity. We show that this algorithm is correct in 2D and 3D, and can be used to tackle the major issues related to rigidity: deciding whether a GCSP is rigid or not and identifying rigid (or over-rigid) subGCSPs.

ECAI Conference 2002 Conference Paper

Progressive Focusing Search

• Nicolas Prcovic
• Bertrand Neveu

IJCAI Conference 1997 Conference Paper

Computational Complexity of Multi-way, Dataflow Constraint Problems

• Gilles Trombettoni
• Bertrand Neveu

Although it is acknowledged that multi-way dataflow constraints are useful in interactive applications, concerns about their tractability have hindered their acceptance. Certain local propagation algorithms that solve these constraints are polynomial, others (such as Sky- Blue) are exponential. Every system handles a specific problem and the influence of any particular restriction on the computational complexity is not yet precisely determined. In this paper, we present three theoretical results that allow us to classify existing multi-way constraint problems. Especially, we prove that the problem handled by SkyBlue is NP-hard.