This chapter introduces Constraint Programming (CP) approaches for solving efficiently a ðnancial portfolio design problem. The CP includes powerful techniques for modeling and solving complex problems. Symmetry breaking coming firstly from CP has proved its efficiency in minimizing CPU times when the problem is symmetric. The authors have adopted CP techniques to model the problem in a constraints system to capitalize on the flexibility of the CP paradigm and to take into consideration the symmetric aspect of the problem. The authors propose different CP models and different hybridizations of symmetry breaking techniques to tackle the problem. Experimental results on non-trivial instances of the problem show the effectiveness of the CP approach.
TopBackground
Constraint Programming (CP) (Rossi, van Beek & Walsh, 2006) is a powerful paradigm which is the result of many scientific works focusing on the resolution of the problems coming from Combinatorial Optimization. It is the result of exploiting a wide range of techniques coming from Artificial Intelligence, Information Technology, databases, programming languages and Operations Research. Nowadays, CP is a field providing many techniques which succeed in solving problems within different fields such as scheduling, planning, vehicle routing, automation, networks and bioinformatics.
Constraint Programming provides a strong modeling tool based on formulating a problem in constraints. CP handles all kinds of constraint, namely logical constraints, linear constraints, non-linear constraints, and sets constraints. CP resolution algorithms based on filtering and propagation algorithms have proven their efficiency in solving large instances of complex problems. A Constraint Satisfaction Problem is a set of variables and a set of constraints which states simply the relation between variables.
A Constraint Satisfaction Problem (CSP) is defined as follows (Definition 5.1) (Rossi, van Beek & Walsh, 2006)
Definition 5.1 (Constraint Satisfaction Problem)
A CSP P is triple 
where X is an n-tuple of variables X={x1,x2,…,xn}, D is an n-tuple of domains D={D1,D2,…,Dn} such that xi∈Di and C is a t-tuple of constraints, C={c1,c2,…,cn}.
(5.1)A constraint cjis a pair 
where 
is a relation on the variables in Sj=scope(cj). In other words, 
is a subset of the Cartesian product of the domains of the variables in Si.
Let be a problem with three variables x1∈{1,3}, x2∈{1,3} and x3∈{2,3}, which must be pairwise distinct.
The problem can be represented by a 3-ary constraint (Figure 1) or by n-ary constraints (Figure 2). The corresponding CSP to Figure 2 is given by P’ (Model 5.2) as follows:
(5.2)