In the paper “Mean-Absolute Deviation Portfolio Optimization Model and Its Applications to Tokyo Stock Market,” Hiroshi Konno and Hiroaki Yamazaki, Management Science, Vol. 37, No. 5 (May, 1991), pp. 519-531 (http://www.jstor.org/pss/2632458) the following Linear Programming model is presented:
Here x(j) is the allocation (the variable we are interested in), and y(t) are auxiliary variables. The data are:
- a(j,t) are mean adjusted returns
- M0 is the budget
- rho is the required return
- r(j) are the stock returns
This model is in fact almost identical to what is presented in this blog before: http://yetanothermathprogrammingconsultant.blogspot.com/2009/07/ms-solver-foundation-excel-interface_07.html. Actually the formulation in the paper by Konno e.a. is slightly non-optimal: the big data block sum(j, a(j,t)*x(j)) is present twice in the model. For large data sets this can be felt in larger solution times. Hence a slightly better formulation could be:
Model Konno ea Improved variables 2300 2600 equations 602 302 nonzero elements 1,204,900 605,200 simplex iterations 2031 1224 solution time 8.9 2.97
GAMS/Gurobi did not really like my improved formulation:
| Starting Gurobi... Presolve time: 0.34s |
This is probably due to this 100% dense block. I’ll pass it on for investigation. Gurobi is under active development so this may be already working ok with later versions. To humble me it solves the original formulation from Konno/Yamazaki just fine!
The above timings were for Cplex/dual. As the original authors used MINOS, here are some timings with MINOS:
The timings with Cplex/dual and Minos/primal point in the same direction. Note that MINOS is faster with the improved model than Cplex on the Konno model. So proper modeling can sometimes help more than choosing a faster solver (of course both having a better formulation and a faster solver is even better). The importance of proper modeling is usually more important for MIP models, but here we see some real differences in performance for different formulations in an LP.
I did a talk at Informs in Washington 2008 about L1 and Linf norms. Actually it is a tricky issue, where you have to think carefully about how you formulate the model in relation to the simplex algorithm. You can specialize the primal simplex algorithm to do something similar as boundswapping in the dual (which is one of the main reasons dual simplex is on average fastest simplex algo) i.e you explore duplicated columns to take longer stepsizes, the speed up is dramatic.
ReplyDeleteYou should be able to see the slides under my slideshare section at linked in :
http://dk.linkedin.com/in/bojensen
if not let me know and I will email it to you.
Looks like this is about Mosek primal and dual simplex. I believe this particular problem is dominated by how you handle this dense data. Mosek's default interior point solver does very good on this problem, the simplex solvers not so much.
ReplyDeleteThis looks like an issue that we fixed in Gurobi 2.0.2 a few months back. What version are you using?
ReplyDeleteThis was with Gurobi 2.0.1 (the latest available from GAMS). I'll ask the GAMS people when they will make 2.0.2 available.
ReplyDeleteI don't think Gurobi 2.0.2 was ever made available to GAMS users. They will have to wait for version 3.0. This a little bit unfortunate as there were a few somewhat important issues fixed related to the above model. See: 2.0.2. notes.
ReplyDeleteYour second formulation is definitely better for interior-point methods as yourself suggest. A useful heuristic is to think about the number of nonzeros in the constraint matrix which is about half in the second formulation.
ReplyDeleteLet me know if you put the GAMS/MPS file anywhere.
Here they are:
ReplyDeleteData: L1portfolio.gdx,
original model: L1Portfolio1.gms,
improved model: L1Portfolio2.gms
Gurobi 3 solves both models fine (as expected: model 2 solves faster than model 1).
ReplyDelete