The Experts below are selected from a list of 53313 Experts worldwide ranked by ideXlab platform
Christophe Jermann - One of the best experts on this subject based on the ideXlab platform.
-
A standard branch-and-bound approach for nonlinear semi-infinite problems
European Journal of Operational Research, 2020Co-Authors: Antoine Marendet, Gilles Chabert, Alexandre Goldsztejn, Christophe JermannAbstract:This paper considers nonlinear semi-infinite problems, which contain at least one semi-infinite Constraint (SIC). The standard branch-and-bound algorithm is adapted to such problems by extending usual upper and lower bounding techniques for nonlinear inequality Constraints to SICs. This is achieved by defining the interval evaluation of parametrized functions and their generalized gradients, by also adapting Numerical Constraint programming techniques to quantified inequalities, and by introducing linear relaxations and restrictions for SICs. The overall efficiency of our algorithm is demonstrated on a standard set of benchmarks from the literature, in comparison with the best state of the art alternative.
-
Solving under-constrained Numerical Constraint satisfaction problems with IBEX
2018Co-Authors: Gilles Chabert, Alexandre Goldsztejn, Christophe JermannAbstract:Under-constrained systems of equations gives rise to manifolds of solution, which are difficult to compute. We show how the Numerical Constraint solver IBEXsolve is able to certify the computation of such positive dimensional manifolds using a parametric interval Newton operator.
-
Variable symmetry breaking in Numerical Constraint problems
Artificial Intelligence, 2015Co-Authors: Alexandre Goldsztejn, Christophe Jermann, Vicente Ruiz De Angulo, Carme TorrasAbstract:Symmetry breaking has been a hot topic of research in the past years, leading to many theoretical developments as well as strong scaling strategies for dealing with hard applications. Most of the research has however focused on discrete, combinatorial, problems, and only few considered also continuous, Numerical, problems. While part of the theory applies in both contexts, Numerical problems have specificities that make most of the technical developments inadequate.In this paper, we present the rlex Constraints, partial symmetry-breaking inequalities corresponding to a relaxation of the famous lex Constraints extensively studied in the discrete case. They allow (partially) breaking any variable symmetry and can be generated in polynomial time. Contrarily to lex Constraints that are impractical in general (due to their overwhelming number) and inappropriate in the continuous context (due to their form), rlex Constraints can be efficiently handled natively by Numerical Constraint solvers. Moreover, we demonstrate their pruning power on continuous domains is almost as strong as that of lex Constraints, and they subsume several previous work on breaking specific symmetry classes for continuous problems. Their experimental behavior is assessed on a collection of standard Numerical problems and the factors influencing their impact are studied. The results confirm rlex Constraints are a dependable counterpart to lex Constraints for Numerical problems.
-
A Branch and Prune Algorithm for the Computation of Generalized Aspects of Parallel Robots
Artificial Intelligence, 2014Co-Authors: Stéphane Caro, Alexandre Goldsztejn, Daisuke Ishii, Damien Chablat, Christophe JermannAbstract:Parallel robots enjoy enhanced mechanical characteristics that have to be contrasted with a more complicated design. In particular, they often have parallel singularities at some poses, and the robots may become uncontrollable, and could even be damaged, in such configurations. The computation of the connected components in the set of nonsingular reachable configurations, called generalized aspects, is therefore a key issue in their design. This paper introduces a new method, based on Numerical Constraint programming, to compute a certified enclosure of the generalized aspects. Though this method does not allow counting their number rigorously, it constructs inner approximations of the nonsingular workspace that allow commanding parallel robots safely. It also provides a lower-bound on the exact number of generalized aspects. It is moreover the first general method able to handle any parallel robot in theory, though its computational complexity currently restricts its usage to robots with three degrees of freedom. Finally, the contraint programming paradigm it relies on makes it possible to consider various additional Constraints (e.g., collision avoidance), making it suitable for practical considerations.
-
Constraint Based Computation of Periodic Orbits of Chaotic Dynamical Systems
2013Co-Authors: Alexandre Goldsztejn, Laurent Granvilliers, Christophe JermannAbstract:The chaos theory emerged at the end of the 19th century, and it has given birth to a deep mathematical theory in the 20th century, with a strong practical impact (e.g., weather forecast, turbulence analysis). Periodic orbits play a key role in understanding chaotic systems. Their rigorous computation provides some insights on the chaotic behavior of the system and it enables computer assisted proofs of chaos related properties (e.g., topological entropy). In this paper, we show that the (Numerical) Constraint programming framework provides a very convenient and efficient method for computing periodic orbits of chaotic dynamical systems: Indeed, the flexibility of CP modeling allows considering various models as well as including additional Constraints (e.g., symmetry breaking Constraints). Furthermore, the richness of the different solving techniques (tunable local propagators, search strategies, etc.) leads to highly efficient computations. These strengths of the CP framework are illustrated by experimental results on classical chaotic systems from the literature.
Nedialko S. Nedialkov - One of the best experts on this subject based on the ideXlab platform.
-
Computing reachable sets for uncertain nonlinear hybrid systems using interval Constraint propagation techniques
Nonlinear Analysis: Hybrid Systems, 2011Co-Authors: Nacim Ramdani, Nedialko S. NedialkovAbstract:We investigate solution techniques for Numerical Constraint satisfaction problems and vali- dated Numerical set integration methods for computing reachable sets of nonlinear hybrid dynamical systems in presence of uncertainty. To use interval simulation tools with higher dimensional hybrid systems, while assuming large domains for either initial continuous state or model parameter vectors, we need to solve the problem of flow/sets intersection in an effective and reliable way. The main idea developed in this paper is first to derive an ana- lytical expression for the boundaries of continuous flows, using interval Taylor methods and techniques for controlling the wrapping effect. Then, the event detection and localization problems underlying flow/sets intersection are expressed as Numerical Constraint satisfaction problems, which are solved using global search methods based on branch-and-prune algo- rithms, interval analysis and consistency techniques. The method is illustrated with hybrid systems with uncertain nonlinear continuous dynamics and nonlinear invariants and guards.
-
Computing reachable sets for uncertain nonlinear hybrid systems using interval Constraint-propagation techniques
Nonlinear Analysis: Hybrid Systems, 2011Co-Authors: Nacim Ramdani, Nedialko S. NedialkovAbstract:Abstract We investigate solution techniques for Numerical Constraint-satisfaction problems and validated Numerical set integration methods for computing reachable sets of nonlinear hybrid dynamical systems in the presence of uncertainty. To use interval simulation tools with higher-dimensional hybrid systems, while assuming large domains for either initial continuous state or model parameter vectors, we need to solve the problem of flow/sets intersection in an effective and reliable way. The main idea developed in this paper is first to derive an analytical expression for the boundaries of continuous flows, using interval Taylor methods and techniques for controlling the wrapping effect. Then, the event detection and localization problems underlying flow/sets intersection are expressed as Numerical Constraint-satisfaction problems, which are solved using global search methods based on branch-and-prune algorithms, interval analysis and consistency techniques. The method is illustrated with hybrid systems with uncertain nonlinear continuous dynamics and nonlinear invariants and guards.
-
ADHS - Computing reachable sets for uncertain nonlinear hybrid systems using interval Constraint propagation techniques
IFAC Proceedings Volumes, 2009Co-Authors: Nacim Ramdani, Nedialko S. NedialkovAbstract:Abstract We investigate solution techniques for Numerical Constraint satisfaction problems and validated Numerical set integration methods for computing reachable sets of nonlinear hybrid dynamical systems in presence of uncertainty. To use interval simulation tools with higher dimensional hybrid systems, while assuming large domains for either initial continuous state or model parameter vectors, we need to solve the problem of flow/sets intersection in an effective and reliable way. The main idea developed in this paper is first to derive an analytical expression for the boundaries of continuous flows, using interval Taylor methods and techniques for controlling the wrapping effect. Then, the event detection and localization problems underlying flow/sets intersection are expressed as Numerical Constraint satisfaction problems, which are solved using global search methods based on branch-and-prune algorithms, interval analysis and consistency techniques. The method is illustrated with a hybrid system with uncertain nonlinear continuous dynamics and nonlinear invariants and guards.
Nacim Ramdani - One of the best experts on this subject based on the ideXlab platform.
-
Computing reachable sets for uncertain nonlinear hybrid systems using interval Constraint propagation techniques
Nonlinear Analysis: Hybrid Systems, 2011Co-Authors: Nacim Ramdani, Nedialko S. NedialkovAbstract:We investigate solution techniques for Numerical Constraint satisfaction problems and vali- dated Numerical set integration methods for computing reachable sets of nonlinear hybrid dynamical systems in presence of uncertainty. To use interval simulation tools with higher dimensional hybrid systems, while assuming large domains for either initial continuous state or model parameter vectors, we need to solve the problem of flow/sets intersection in an effective and reliable way. The main idea developed in this paper is first to derive an ana- lytical expression for the boundaries of continuous flows, using interval Taylor methods and techniques for controlling the wrapping effect. Then, the event detection and localization problems underlying flow/sets intersection are expressed as Numerical Constraint satisfaction problems, which are solved using global search methods based on branch-and-prune algo- rithms, interval analysis and consistency techniques. The method is illustrated with hybrid systems with uncertain nonlinear continuous dynamics and nonlinear invariants and guards.
-
Computing reachable sets for uncertain nonlinear hybrid systems using interval Constraint-propagation techniques
Nonlinear Analysis: Hybrid Systems, 2011Co-Authors: Nacim Ramdani, Nedialko S. NedialkovAbstract:Abstract We investigate solution techniques for Numerical Constraint-satisfaction problems and validated Numerical set integration methods for computing reachable sets of nonlinear hybrid dynamical systems in the presence of uncertainty. To use interval simulation tools with higher-dimensional hybrid systems, while assuming large domains for either initial continuous state or model parameter vectors, we need to solve the problem of flow/sets intersection in an effective and reliable way. The main idea developed in this paper is first to derive an analytical expression for the boundaries of continuous flows, using interval Taylor methods and techniques for controlling the wrapping effect. Then, the event detection and localization problems underlying flow/sets intersection are expressed as Numerical Constraint-satisfaction problems, which are solved using global search methods based on branch-and-prune algorithms, interval analysis and consistency techniques. The method is illustrated with hybrid systems with uncertain nonlinear continuous dynamics and nonlinear invariants and guards.
-
ADHS - Computing reachable sets for uncertain nonlinear hybrid systems using interval Constraint propagation techniques
IFAC Proceedings Volumes, 2009Co-Authors: Nacim Ramdani, Nedialko S. NedialkovAbstract:Abstract We investigate solution techniques for Numerical Constraint satisfaction problems and validated Numerical set integration methods for computing reachable sets of nonlinear hybrid dynamical systems in presence of uncertainty. To use interval simulation tools with higher dimensional hybrid systems, while assuming large domains for either initial continuous state or model parameter vectors, we need to solve the problem of flow/sets intersection in an effective and reliable way. The main idea developed in this paper is first to derive an analytical expression for the boundaries of continuous flows, using interval Taylor methods and techniques for controlling the wrapping effect. Then, the event detection and localization problems underlying flow/sets intersection are expressed as Numerical Constraint satisfaction problems, which are solved using global search methods based on branch-and-prune algorithms, interval analysis and consistency techniques. The method is illustrated with a hybrid system with uncertain nonlinear continuous dynamics and nonlinear invariants and guards.
Boi Faltings - One of the best experts on this subject based on the ideXlab platform.
-
Enhancing Numerical Constraint propagation using multiple inclusion representations
Annals of Mathematics and Artificial Intelligence, 2009Co-Authors: Djamila Sam-haroud, Boi FaltingsAbstract:Building tight and conservative enclosures of the solution set is of crucial importance in the design of efficient complete solvers for Numerical Constraint satisfaction problems (NCSPs). This paper proposes a novel generic algorithm enabling the cooperative use, during Constraint propagation, of multiple enclosure techniques. The new algorithm brings into the Constraint propagation framework the strength of techniques coming from different areas such as interval arithmetic, affine arithmetic, and mathematical programming. It is based on the directed acyclic graph (DAG) representation of NCSPs whose flexibility and expressiveness facilitates the design of fine-grained combination strategies for general factorable systems. The paper presents several possible combination strategies for creating practical instances of the generic algorithm. The experiments reported on a particular instance using interval Constraint propagation, interval arithmetic, affine arithmetic, and linear programming illustrate the flexibility and efficiency of the approach.
-
Branch-and-Prune Search Strategies for Numerical Constraint Solving
arXiv: Artificial Intelligence, 2005Co-Authors: Xuan-ha Vu, Djamila Sam-haroud, Marius-calin Silaghi, Boi FaltingsAbstract:When solving Numerical Constraints such as nonlinear equations and inequalities, solvers often exploit pruning techniques, which remove redundant value combinations from the domains of variables, at pruning steps. To find the complete solution set, most of these solvers alternate the pruning steps with branching steps, which split each problem into subproblems. This forms the so-called branch-and-prune framework, well known among the approaches for solving Numerical Constraints. The basic branch-and-prune search strategy that uses domain bisections in place of the branching steps is called the bisection search. In general, the bisection search works well in case (i) the solutions are isolated, but it can be improved further in case (ii) there are continuums of solutions (this often occurs when inequalities are involved). In this paper, we propose a new branch-and-prune search strategy along with several variants, which not only allow yielding better branching decisions in the latter case, but also work as well as the bisection search does in the former case. These new search algorithms enable us to employ various pruning techniques in the construction of inner and outer approximations of the solution set. Our experiments show that these algorithms speed up the solving process often by one order of magnitude or more when solving problems with continuums of solutions, while keeping the same performance as the bisection search when the solutions are isolated.
-
combining multiple inclusion representations in Numerical Constraint propagation
International Conference on Tools with Artificial Intelligence, 2004Co-Authors: Djamila Samharoud, Boi FaltingsAbstract:This work proposes a novel generic scheme enabling the combination of multiple inclusion representations to propagate Numerical Constraints. The scheme allows bringing into the Constraint propagation framework the strength of inclusion techniques coming from different areas. The scheme is based on the DAG representation of the Constraint system. This enables devising fine-grained combination strategies involving any factorable Constraint system. The paper presents several possible combination strategies for creating practical instances of the generic scheme. The experiments reported on a particular instance using interval Constraint propagation, interval arithmetic, affine arithmetic and linear programming illustrate the flexibility and efficiency of the approach.
-
a generic scheme for combining multiple inclusion representations in Numerical Constraint propagation
2004Co-Authors: Djamila Samharoud, Boi FaltingsAbstract:This paper proposes a novel generic scheme enabling the combination of multiple inclusion representations to propagate Numerical Constraints. The scheme allows bringing into the Constraint propagation framework the strength of inclusion techniques coming from different areas such as interval arithmetic, affine arithmetic or mathematical programming. The scheme is based on the DAG representation of the Constraint system. This enables devising fine-grained combination strategies involving any factorable Constraint system. The paper presents several possible combination strategies for creating practical instances of the generic scheme. The experiments reported on a particular instance using interval propagation, interval arithmetic, affine arithmetic and linear programming illustrate the flexibility and efficiency of the approach.
-
ICTAI - Combining multiple inclusion representations in Numerical Constraint propagation
16th IEEE International Conference on Tools with Artificial Intelligence, 1Co-Authors: Djamila Sam-haroud, Boi FaltingsAbstract:This work proposes a novel generic scheme enabling the combination of multiple inclusion representations to propagate Numerical Constraints. The scheme allows bringing into the Constraint propagation framework the strength of inclusion techniques coming from different areas. The scheme is based on the DAG representation of the Constraint system. This enables devising fine-grained combination strategies involving any factorable Constraint system. The paper presents several possible combination strategies for creating practical instances of the generic scheme. The experiments reported on a particular instance using interval Constraint propagation, interval arithmetic, affine arithmetic and linear programming illustrate the flexibility and efficiency of the approach.
Daisuke Ishii - One of the best experts on this subject based on the ideXlab platform.
-
Scalable Parallel Numerical Constraint Solver Using Global Load Balancing
Proceedings of the ACM SIGPLAN Workshop on X10, 2015Co-Authors: Daisuke Ishii, Kazuki Yoshizoe, Toyotaro SuzumuraAbstract:We present a scalable parallel solver for Numerical Constraint satisfaction problems (NCSPs). Our parallelization scheme consists of homogeneous worker solvers, each of which runs on an available core and communicates with others via the global load balancing (GLB) method. The parallel solver is implemented with X10 that provides an implementation of GLB as a library. In experiments, several NCSPs from the literature were solved and attained up to 516-fold speedup using 600 cores of the TSUBAME2.5 supercomputer.
-
scalable parallel Numerical Constraint solver using global load balancing
arXiv: Distributed Parallel and Cluster Computing, 2015Co-Authors: Daisuke Ishii, Kazuki Yoshizoe, Toyotaro SuzumuraAbstract:We present a scalable parallel solver for Numerical Constraint satisfaction problems (NCSPs). Our parallelization scheme consists of homogeneous worker solvers, each of which runs on an available core and communicates with others via the global load balancing (GLB) method. The search tree of the branch and prune algorithm is split and distributed through the two phases of GLB: a random workload stealing phase and a workload distribution and termination phase based on a hyper-cube-shaped graph called lifeline. The parallel solver is simply implemented with X10 that provides an implementation of GLB as a library. In experiments, several NCSPs from the literature were solved and attained up to 516-fold speedup using 600 cores of the TSUBAME2.5 supercomputer. Optimal GLB configurations are analyzed.
-
A Branch and Prune Algorithm for the Computation of Generalized Aspects of Parallel Robots
Artificial Intelligence, 2014Co-Authors: Stéphane Caro, Alexandre Goldsztejn, Daisuke Ishii, Damien Chablat, Christophe JermannAbstract:Parallel robots enjoy enhanced mechanical characteristics that have to be contrasted with a more complicated design. In particular, they often have parallel singularities at some poses, and the robots may become uncontrollable, and could even be damaged, in such configurations. The computation of the connected components in the set of nonsingular reachable configurations, called generalized aspects, is therefore a key issue in their design. This paper introduces a new method, based on Numerical Constraint programming, to compute a certified enclosure of the generalized aspects. Though this method does not allow counting their number rigorously, it constructs inner approximations of the nonsingular workspace that allow commanding parallel robots safely. It also provides a lower-bound on the exact number of generalized aspects. It is moreover the first general method able to handle any parallel robot in theory, though its computational complexity currently restricts its usage to robots with three degrees of freedom. Finally, the contraint programming paradigm it relies on makes it possible to consider various additional Constraints (e.g., collision avoidance), making it suitable for practical considerations.
-
Scalable Parallel Numerical CSP Solver
Lecture Notes in Computer Science, 2014Co-Authors: Daisuke Ishii, Kazuki Yoshizoe, Toyotaro SuzumuraAbstract:We present a parallel solver for Numerical Constraint satisfaction problems (NCSPs) that can scale on a number of cores. Our proposed method runs worker solvers on the available cores and simultaneously the workers cooperate for the search space distribution and balancing. In the experiments, we attained up to 119-fold speedup using 256 cores of a parallel computer.
-
A Branch and Prune Algorithm for the Computation of Generalized Aspects of Parallel Robots
2012Co-Authors: Stéphane Caro, Alexandre Goldsztejn, Daisuke Ishii, Damien Chablat, Christophe JermannAbstract:Parallel robots enjoy enhanced mechanical characteristics that have to be contrasted with a more complicated design. In particular, they often have parallel singularities at some poses, and the robot may become uncontrollable, and could even be damaged, in such configurations. The computation of singularity free sets of reachable poses, called generalized aspects, is therefore a key issue in their design. A new methodology based on Numerical Constraint programming is proposed to compute a certified enclosure of such generalized aspects which fully automatically applies to arbitrary robot kinematic model.
