Interval Constraint Programming and Global Optimization
(or how to optimize a function under nonlinear (non convex)
equality and inequality constraints by using interval
methods (often) based on constraint programming
principles)
- Contraction algorithms for search space reduction
in polynomial time. See papers about
Mohc,
OccurrenceGrouping,
3BCID,
I-CSE,
Box-k,
PolyBox,
eXtremal interval Newton.
- Reliable non convex constrained global
optimization 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,
sinus, 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.
- Integration of new algorithms in the Ibex interval-based solver.
- Dedicated interval-based solvers, e.g., in a
short-term: calibration (parallel robots), parameter
estimation.
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.