  Given an Eulerian graph G, in the Maximum Eulerian Cycle Decomposition
problem, we are interested in finding a collection of edge-disjoint cycles
{E_1, E_2, ..., E_k} in G such that all edges of G are in exactly one cycle and
k is maximum. We present an algorithm to solve the pricing problem of a column
generation Integer Linear Programming (ILP) model introduced by Lancia and
Serafini (2016). Furthermore, we propose a greedy heuristic, which searches for
minimum size cycles starting from a random vertex, and a heuristic based on
partially solving the ILP model. We performed tests comparing the three
approaches in relation to the quality of solutions and execution time, using
distinct sets of Eulerian graphs, each set grouping graphs with different
numbers of vertices and edges. Our experimental results show that the ILP based
heuristic outperforms the other methods.
