Proving that the state of a controlled nonlinear system always stays inside a time moving bubble (or capture tube) amounts to proving the inconsistency of a set of nonlinear inequalities in the time-state space. In practice however, even with a good intuition, it is difficult for a human to find such a capture tube except for simple examples. In 2014, Jaulin et al. established properties that support a new interval approach for validating a quasi capture tube, i.e. a candidate tube (with a simple form) from which the mobile system can escape, but into which it enters again before a given time. A quasi capture tube is easy to find in practice for a controlled system. Merging the trajectories originated from the candidate tube yields the smallest capture tube enclosing it. This paper proposes an interval constraint programming solver dedicated to the quasi capture tube validation. The problem is viewed as a differential CSP where the functional variables correspond to the state variables of the system and the constraints define system trajectories that escape from the candidate tube "for ever". The solver performs a branch and contract procedure for computing the trajectories that escape from the candidate tube. If no solution is found, the quasi capture tube is validated and, as a side effect, a corrected smallest capture tube enclosing the quasi one is computed. The approach is experimentally validated on several examples having 2 to 5 degrees of freedom.

A Constraint Satisfaction Problem is composed by a set of variables, their related domains and a set of constraints among the variables that must be satisfied. These are known as hard problems to be solved. Many algorithms have been proposed to solve these problems. Metaheuristics and in particular ant-based algorithms have been used to solve difficult instances. In this paper, we propose new heuristics to be included in an ant-based algorithm in order to improve its performance when tackling hard constraint satisfaction problems. These heuristics are focused on the availability of consistent variable values and to restrict the ants collaborative information to the feasibility. To evaluate these heuristics we used the well-known Ant Solver algorithm and tested with problem instances from the transition phase. Results show that using our heuristics the Ants algorithm increases the number of problems that it is able to solve. Finally, a statistical analysis is presented to compare these approaches.

The parameter estimation problem is awidespread and challenging problem in engineering sciencesconsisting in computing the parameters of a parametricmodel that fit observed data. Calibration or geolocation canbe viewed as specific parameter estimation problems. In thispaper we address the problem of finding all the instances ofa parametric model that can explain at least q observationswithin a given tolerance. The computer vision communityhas proposed the RANSAC algorithm to deal with outliersin the observed data. This randomized algorithm is efficientbut non-deterministic and therefore incomplete. Jaulin etal. proposes a complete and combinatorial algorithm thatexhaustively traverses the whole space of parameter vectors toextract the valid model instances. This algorithm is based oninterval constraint programming methods and on a so calledq-intersection operator, a relaxed intersection operator thatassumes that at least q observed data are inliers. This paperproposes several improvements to Jaulin et al.'s algorithm.Most of them are generic and some others are dedicated tothe shape detection problem used to validate our approach.Compared to Jaulin et al.'s algorithm, our algorithm canguarantee a number of fitted observations in the producedmodel instances. Also, first experiments in plane and circlerecognition highlight speedups of two orders of magnitude.

An operator called CID and an efficient variant 3BCID wereproposed 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 ofsub-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.

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 and Stadherr for producing a reliable outer and inner polyhedral approximation of the solution set and alinearization 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 outperforms the best reliable global optimizers.

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.

The process of designing an evolutionary algorithm requires the definition of an adequate representation, a set of components as operators, parameters and parameters values. In practice, some operators can not be helping the evolutionary algorithm to perform his work, thus we require to be able to detect these situations. In this paper we are interested on analyzing the capabilities of off-line calibration techniques, originally designed to tune parameter values, to recognize situations more related to the design process of an evolutionary algorithm. We experimentally analyze the results of the off-line calibration techniques on some specific situations. For that purpose we use some specially designed operators for an evolutionary algorithm which solves the traveling salesman problem.

Most metaheuristics define a set of parameters that must be tuned. A good setup of those parameter values can lead to take advantage of all the metaheuristic capabilities to solve the problem at hand. Tuning techniques are step by step methods based on multiple runs of the algorithm. In this study we compare three automated tuning methods: F-Race, Revac and ParamILS. We evaluate the performance of each method using a genetic algorithm for combinatorial optimization. The differences and advantages of each technique are discussed. Finally we establish some guidelines that might help to choose a tuning process to use.

When handling 2D packing problems, numerous incomplete and complete algorithms maintain a so-called bottom-left (BL) property: every rectangle placed in a container is propped up bottom and left. While it is easy to make a rectangle BL when it is is added in a container, it is more expensive to maintain all the placed pieces BL when a rectangle is removed. This prevents researchers from designing incremental moves for metaheuristics or efficient complete optimization algorithms. This paper investigates the possibility of violating the BL property. Instead, we propose to maintain only the set of "maximal holes", which allows incremental additions and removals of rectangles. To validate our alternative approach, we have designed an incremental move, maintaining maximal holes, for the strip-packing problem, a variant of the famous 2D bin-packing. We have also implemented a generic metaheuristic using this move and standard greedy heuristics. Experimental results show that the approach is competitive with the best known incomplete algorithms, especially the other metaheuristics (able to escape from local minima).

To cope with a growing number of applications, the basic formalism of constraint satisfaction problems has to be augmented in various directions. One of these directions is the concept of dynamic constraint problems i.e. problems to which constraints can be added but also retracted at any time. To handle dynamic problems, it is important to adapt efficiently the solution procedures that are available on static ones. Of particular interest is the arc-consistency enforcement procedure; the goal of the paper is to present an adaptation of it to dynamic problems. Contrary to previous approaches, the one presented here does not rely on any reason maintenance system and consequently has the advantage of a low space complexity. The detailed algorithm of the procedure is given and an experimental evaluation of its performances is displayed. Some benefits gained by the approach regarding flexibility and extensibility are highlighted.>