In this thesis we extend the Markowitz Mean-Variance model to a rebalancing portfolio optimization problem incorporating realistic considerations such as transaction costs and a risk-free asset with short-selling allowed, and we apply the Tabu Search (TS) heuristic to solve practical portfolio problems. First of all, we propose a biobjective portfolio optimization model which we expect to yield a portfolio equilibrium by combining the two objectives: maximize the portfolioââ'¬â"¢s expected return and minimize its risk. For realistic portfolio problems we consider the multi-objective portfolio optimization models incorporating the risk-free asset and its short-selling and nonlinear transaction costs based on a single-period and a rebalancing portfolio optimization problem. Especially, to solve the rebalancing portfolio problem, we develop an adaptive, advanced TS algorithm having an evolutionary neighborhood structure, and we solve the problem with an iterative folding back procedure in the decision tree structure. Computational studies are performed with a risk-free asset and the number of risky assets to be 5, 10, 12, and 15 for both the single-period and rebalancing portfolio problems.