We present a new approach to 3D scene modeling based on geometrical constraints. Contrary to most of the existing methods, we can obtain 3D scene models that respect the given constraints exactly. Our system can describe a large variety of linear and non-linear constraints in a flexible way. The constraint solving is based on a constraint system decomposition technique called GPDOF. It is a simple, polynomial-time and complete algorithm that can find a reduced parameterization of a scene, and a decomposition of the whole constraint system into small sub-systems which can be solved in a very efficient way. The execution process is interleaved with a bundle adjustment, an optimization method based on a Levenberg-Marquadt algorithm. We have validated our approach in reconstructing, from images, 3D models of buildings.

We propose a constraint based formulation for the alldiff matrix, a matrix in which all the elements in each row/column have to be different. The alldiff matrix is the underlying structure of several real world problems, such as sports scheduling, timetabling, and fiber optics routing. We discuss symmetry breaking strategies for the alldiff matrix. Our formulation is very effective for this highly combinatorial problem, substantially outperforming Integer Programming formulations.

This work presents a hybrid approach to solving the maximum stable set problem, using constraint and semidefinite programming. The approach consists of two steps: subproblem generation and subproblem solution. First we rank the variable domain values, based on the solution of a semidefinite relaxation. Using this ranking, we generate the most promising subproblems first, by exploring a search tree using a limited discrepancy strategy. Then the subproblems are solved using a constraint programming solver. To strengthen the semidefinite relaxation, we propose to infer additional constraints from the discrepancy structure. Computational results show that the semidefinite relaxation is very informative, since solutions of good quality are found in the first subproblems or optimality is proven immediately.