The aim of this chapter is to introduce the different notions of the techniques used to solve the portfolio design problem. These techniques can be divided into two exact (or complete) methods and approached (or incomplete) methods. In the first part, the authors provide the exact approaches, namely linear programming and constraint programming, as well as the techniques of symmetry breaking, the modeling notions, and the different solving algorithms. The second part concerns approached methods, namely Simulated Annealing, IDWalk, Tabu Search, GWW, and Variable Neighborhood Search, including the techniques of studying the performance profiles of a method.
TopBackground
Operations Research (OR) is a discipline which deals with computer science and applied mathematics to make decisions. During these last few years, (OR) has become omnipresent in many problems of optimization, namely financial portfolio optimization, scheduling, economics, industry, etc.Operations Research is conceived as a set of techniques of decision support; the solution (or the decision) is computed via rational bases and represents the best decision that should be taken by the human.
Combinatorial Optimization is a field coming from (OR). It includes all types of methods which are conceived to solve an optimized solution, such as maximizing the gain of a factory or minimizing its spending. It computes the optimal solution from an initial solution, within a set of realizable solutions (Definition 1.1).
Definition 2.1(Combinatorial Optimization Problem)
A combinatorial optimization problem P(V,C,D) is a problem which can be modeled in a graph or in an integer program, where:
- •
V: a set of variables {v1,v2,…,vn}, such that vi is a continuous or a discrete variable.
- •
C: a set of constraints {c1,c2,…,cm}, such that cj is a constraint defined on variables ofV.
- •
D: a set of domains {D1,D2,…,Dn}, such that Di is a domain of the variable vi.
- •
An objective function of minimizing or maximizing noted f, such that: f: D1×D2×…Dn→ℝ
In the literature, we find different solving techniques coming from Operations Research, which seem to divide naturally into two categories: exact methods and approximate methods. The major difference between the both classes lies on finding the global optimum (Definition 1.2). Generally, optimization approaches start with initial solution s0, computed randomly or by a greedy or exact algorithm, and attempt to improve s0 (or the current solution), at each iteration until reaching the desired optimum (global or approximated)
Figure 1 shows a search space which contains three local optima, where only one corresponds to the global optimum.
Figure 1. Local optimum and global optimum in a search space (El-Ghazali, 2009)
The disadvantage of approximate methods is becoming stuck at a local optimum (Definition 2.3), due to searching for the best solution in the same neighborhood.