Effective linear programming heuristics for a portfolio selection problem

The problem of selecting a portfolio has been largely faced in terms of minimizing the risk given the return. While the original computational problems arising in the solution of the quadratic programming model due to Markowitz have been overcome by the progress in algorithmic research, the introduction of different risk functions, which give rise to linear programming models, has stimulated interest in new problems obtained by taking into account additional characteristics of the portfolio selection problem. In this paper new heuristics are proposed for the solution of a mixed integer linear model which takes into account minimum transaction lots. The heuristics are based on the construction of mixed integer subproblems (using only a part of the securities available) formulated using the information obtained from the solution of the relaxed problem (selected securities and reduced costs). The heuristics have been tested with respect to (1992–1994) time period, using real data from the Milan Stock Exchange.