Use ParadisEO-MOEO to solve the Association rules discovery problem

In this contribution, the problem of association rules discovery has been modeled as a multi-objective combinatorial optimization problem using Paradiseo framework. A hybrid approach, combining a dedicated genetic algorithm and an enumerative procedure is proposed.


Problem description

The association rules problem was first called the market-basket problem. The initial problem was the following: given a set of items and a large collection of sales records, which consist in a transaction date and the items bought in the transaction, the task is to find relationships between the items contained in the different transactions. An association rule is an expression of the form: IF C THEN P. This kind of rules contains two parts: the IF part which is called the rule condition (C) and the THEN part which is called the rule prediction (P), where both parts, the C and the P parts, contain a conjunction of terms indicating specific values for specific attributes.

Solver description

This problem is tackled by a genetic algorithm implemented using ParadisEO-MOEO (see the main_ea.cpp in the archive).


To install the package, follow these steps:

  • Download one of the previous archives and decompress it.
  • Edit the "install.cmake" file and replace the path by the absolute path of ParadisEO
    => Example:
SET(PARADISEO_DIR "/home/.../ParadiseoDirectory" CACHE PATH "ParadisEO directory" FORCE)
  • Go in the "build" directory
  • Run (in a terminal/console): cmake .. -G"<generator type>"
    (Several generators exist: see)
  • Compile using the appropriate tool (run "make" if you choose the "Unix Makefiles" generator)
  • Install the data for testing the tool (run "make install")