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 xk, 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:
- 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.