Interval Constraint Programming for Non Convex Problems: Global Optimization, Parameter Estimation, Dynamic Systems

• Contraction algorithms for search space reduction in polynomial time. See papers about Mohc, OccurrenceGrouping, 3BCID/ACID, I-CSE, Box-k, PolyBox, eXtremal interval Newton.
• Reliable non convex constrained global optimization (NLP) using a new interval branch and bound approach. The most difficult problem is handled, in which the objective function and the constraints (over the reals) can contain operators such as x^k, division, exp, log, sine, etc. Our global optimizer can provide an optimal solution and its cost with a bounded error, e.g., 10^-8, or a proof of unfeasibility. Have a look at the first paper in English or in French about this new approach. In addition to the contraction algorithms mentioned above, this constrained optimization is endowed with two important features:
  • Upper bounding algorithms based on the extraction of inner (entirely feasible) regions.
  • Sophisticated best-first search space exploration.
• Parameter estimation using interval techniques. Our generic strategy can compute the parameters of a model fitting a maximum number of observation constraints in presence of outliers (inverse problem). The contributions include the study of the q-intersection problem (computational study and new algorithms), and application to shape recognition and stereovision (essential matrix estimation).
• Dynamic systems mixing differential equations (ODEs) and other constraints (algebraic constraints and other constraints on trajectories: observation constraints, delay constraints, other inter-temporal constraints). A first generic solver has been developed in the Tubex library, with first promising results on boundary value problems. This subject is studied in the CONTREDO ANR project.
• These algorithms are integrated in the Ibex interval-based solver (C++ library).

Decomposition of (geometrical) constraint systems

• Algorithms for decomposing systems of nonlinear equations. See papers about GPDOF, dataflow constraints.
• Application in computer vision: 3D model/scene reconstruction under geometrical constraints. See papers: journal, conference.
• Algorithms for decomposing systems of geometrical constraints using the rigidity property. See papers: survey, algorithm.
• Solving of a decomposed system with interval methods and inter-block backtracking. Read about IBB version 1, version 2, version 3.

Incomplete algorithms for combinatorial optimization

• New general-purpose and simple metaheuristics. See papers about ID Walk, GWW.
• Dedicated incomplete algorithm for strip-packing (2D packing). The latest results appear here.