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 x^{k}, 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.