065: Optimal Financial Portfolio Design

Proposed by Pierre Flener, Jean-Noël Monette

An OPD problem $\langle v, b, r \rangle$ is to find a matrix of $v$ rows and $b$ columns of $0$-$1$ values such that each row sums to $r$, and the maximum, denoted $\lambda$, of the dot products beween all pairs of distinct rows is minimal. Equivalently, the objective is to find $v$ subsets of cardinality $r$ drawn from a given set of $b$ elements, such that the largest intersection of any two of the $v$ sets has minimal cardinality, denoted $\lambda$.

This is an abstract description of a problem that appears in finance: full details are given by [Flener_CP04] and [Flener_CONS07_CDO2]. In a typical OPD in finance, we have $250 \leq v \leq 500$ and $4 \leq b \leq 25$, with $r \approx 100$. This is one order of magnitude larger than the largest BIBDs that have been built by computer using systematic search; the BIBD problem, which is a constraint satisfaction problem, is closely related to the OPD problem, which is a constrained optimisation problem. A lower bound on the number of shared elements of any pair of same-sized subsets drawn from a given set was established by cite{Sivertsson:MSc05, Flener:AOC08}: this lower bound can be applied to the objective value $\lambda$. A first constraint-based model, with advanced symmetry-handling methods, was proposed by [Flener_CP04], then improved by [Sivertsson_MSc05] and ultimately by [Flener_CONS07_CDO2], by using the lower bound. As pointed out by [Agren_CP05], one can advantageously exploit the many symmetries by using local search instead of systematic search; this was confirmed by [Lebbah_ENDM15], by [Lebbah_IJAMC15], and at the MiniZinc Challenge 2015, where a constraint-based local search solver outperformed all systematic search solvers, even on sub-realistic instances.