Informatica

Portfolio optimization is to find the stock portfolio minimizing the risk for a required return or maximizing the return for a given risk level. The seminal work in this field is the m ean-variance model formulated as a quadratic programming problem. Since it is not computationally practical to solve the original model directly, a number of alternative models have been proposed.

We propose a new hybrid approach to solve the unbounded integer knapsack problem (UKP), where valid inequalities are generated based on intermediate solutions of an equivalent forward dynamic programming formulation. These inequalities help tighten the initial LP relaxation of the UKP, and therefore improve the overall computational efficiency. We also extended this approach to solve the multi-dimensional unbounded knapsack problem (d-UKP). Computational results demonstrate the effectiveness of our approach on both problems.