Journées de l'optimisation 2007 Optimizations days

We present a parallel constraint programming algorithm to solve the traveling tournament problem. The algorithm uses a heuristic ranking of the possible values of the variables based on the reduced costs obtained by solving a linear programming relaxation of an integer programming formulation of the problem. We use Discrepancy Based Search (DBS) to generate the best subproblems at the beginning of the search.

Distributed Constraint Optimization is increasingly used to formalize problem solving by multiple agents. However, there are situations where agents represent an organization made up of heterogeneous agents (e.g. network of companies) in which the context, the structure, and the business rules define the interactions that are possible between them. The solution space for those hierarchical problems is reminiscent of the ones of centralized combinatorial problems. Therefore, we propose a distributed algorithm (MacDS) that performs a discrepancy-based search which is known to perform well for centralized problems. The proposed algorithm is complete and aims at producing good solutions in a short amount of time. It allows concurrent computation and is tolerant to message delays. It has been evaluated using real industrial problems with complex subproblems, for which it showed good performance.

We show how different global constraints can be decomposed into elementary constraints without hindering propagation. The use of a decomposition offers many advantages compare to the use of a monolithic propagator. We present the decomposition of the REGULAR, the GRAMMAR, and the SEQUENCE constraints as well as some decompositions of linear constraints.

Recent studies have shown the potential of counting-based heuristics in terms of easy-to-use and efficiency. The basic idea is to enrich the constraint inference framework in order not only to reduce the search space but also to guide the search towards area that are likely to contain an high number of solutions. Although preliminary results seem very promising, its applicability has to face some open issues such as efficient counting for the widely-used all-different constraint. In this talk, we will present the state-of-the-art of approximated counting algorithms for the all-different constraint. We will propose an improvement over one of the algorithms that seems to better suit our needs. Experimental results will show the effectiveness of our approach as well as its impact in a counting-based heuristic framework.