Heuristic methods for the problem of quadratic transportion

Many indices have been proposed in order to measure the connection between two statistical variables, taken from a finite population. The maxima of some of these indices have been determined inside the class of Frèchet. Instead, the maximum of the chi-square of Pizzetti-Pearson is not known. To find such a maximum, it is necessary to solve a transportation problem, with a convex quadratic objective function to be maximized. In this paper five fast heuristics are presented for the solution of this problem. Four of them are ‘greedy’ ones, the fifth consists in the solution of a linear relaxation of the problem and gives also an upper bound of the optimum. In addition, with the method of Frank-Wolfe, the solutions of the five heuristics can be further improved. Under appropriate conditions, these methods give optimal solutions; moreover, the upper bound of the optimum given by one of the heuristics is always better than the one used to calculate the mean contingency index. Experimental results, obtained by randomly generated test examples, have permitted to select the two most efficient ‘greedy’ heuristics, with an error often less than 1%.