## costfunction.org

## Welcome on Costfunction.org

Welcome on the costfunction.org , the aims of this web site is to promote cost function network in providing Benchmark and teaching material , solver demo , link to articule about cost function used in the contexte of constraint programming.

The web hosts also some Research projet directely connected to cost function .

Last Updated (Friday, 09 September 2011 17:15)

## Ficolofo ProjectMany combinatorial problems can be naturally modelled as a network of local interactions between discrete variables. In the simplest cases, the local interactions are simply compatibility/incompatibility relations and the network is a constraint network (CN). A fundamental property of such a network is its consistency (or feasibility): is it possible to find a value for each variable in the network in such a way that no incompatibility appears ? Answering this question defines the Constraint Satisfaction Problem (CSP). This problem has been the object of intense research in the last 30 years and the french community is very weel represented at the international level. The dedicated techniques developed to solve CSP form the foundations of constraint programming languages such as IBM ILOG Solver, Cosytec CHIP, Cisco Eclipse... These tools have shown very good complementarity with mathematical programming techniques, for example in area such as resource scheduling and configuration... Many industrial size problems have been solved using this approach. The ubiquitous and fundamental technique used inside these constraint solvers is the process of filtering by local consistency. This process consists in transforming a given constraint network in an equivalent network (having the same set of solutions) which is also more explicit and simple (characterized by specific properties). The most usual filtering techniques act at the level of single constraints and are known as filtering by arc consistency. In 2000, these techniques have been extended to cost function networks (CFN, also called Weighted or Soft Constraint Networks). Cost function networks define an extension of pure constraint networks that allows to directly capture complex optimization problems mixing arbitrary constraints and cost functions (possibly non linear). In the last years, this technical advance has been combined with branch and bound, where it provides the required incremental lower bound. This approach has been sophisticated to the point where different hard combinatorial optimization problems, open for more than 15 years, have been solved to optimality. Cost function networks have also been used to solve very large problems in bioinformatics (genetics, molecular biology) and applied to large stochastic graphical models (bayesian nets and Markov random fields).
To guide these developments, we will rely on the complete set of benchmark problems accumulated in the "
FICOLOFO project is funded by the Agence nationale de la Recherche (ANR) Last Updated (Friday, 04 February 2011 08:40) |