This chapter provides a global synthesis of the realized results by applying exact and approximate approaches on the portfolio design (PD) problem. The authors introduce an experimental analysis of best approaches based on linear programming and constraint programming techniques, according to the CPU time. Next, a global experiment synthesis of the best approximate approaches based on Simulated Annealing, IDWalk, Tabu Search, GWW, and VNS is realized according to the number of success and the CPU time. First results show that constraint programming with breaking all the detected symmetries is the best as an exact approach, VNS combined with simulated annealing is effective on non-trivial instances of the problem, and simulated annealing is the most effective as a simple local search.
TopIntroduction
Through the previous chapters of this book, we introduced and applied various approaches coming from two classes of optimization techniques, namely complete and incomplete methods. Each type of method is applied and analyzed separately. The Linear Programming approaches are discussed in Chapter 4, Constraint Programming approaches in Chapter 5, Local Search approaches in Chapter 6 and finally the VNS approaches which are studied in Chapter 7. Finally, a general analysis of all the applied techniques is needed, in order to filter the applied methods according to their effectiveness in computing the desired optimized CDO Squared portfolio.
Thus, in this chapter, we provide a global synthesis of exact and approximate methods applied on a financial portfolio design problem (PD) modeled in a 0-1 quadratic model (Model 3.14 in Chapter 3). We analyze the results reached with exact approaches, namely Linear Programming and Constraint Programming. The best solutions given are provided by the LP approach without symmetry breaking and implemented under the SCIP solver, and the CP approach with breaking all the detected symmetries, by combining static and dynamic techniques of symmetry breaking.
We offer a general synthesis of the experimental results of the applied approximate methods, respectively Simple and Population based Local Search, and Variable Neighborhood Search. The best results achieved were provided by Simulated Annealing launched with the FLIP neighborhood function (Chapter 6), Skewed Variable Neighborhood Search combined with IDWalk and launched with the SWAP neighborhood function, and Variable Neighborhood Search combined with Simulated Annealing and launched with the FLIP neighborhood function.
A global synthesis of exact and approximate approaches is given separately, due to the major differences between the two. In exact approaches, the quality of solutions is proved and the CPU time is conditioned by the size of the instance. But approximate approaches provide acceptable solutions in a reasonable CPU time.
The chapter is organized as follows. In Section 2, the best realized experimental results with exact approaches are given along with a global synthesis of the corresponding methods. In section 3, we introduce the results of the implemented approximate methods. We present a summary table and performance profiles, to lead to a clear and global synthesis. Finally, we conclude the chapter.