A Robust Knapsack Based Constrained Portfolio Optimization

Document Type : Original Article


Department of Industrial Engineering, Iran University of Science and Technology, Tehran, Iran


Many portfolio optimization problems deal with allocation of assets which carry a relatively high market price. Therefore, it is necessary to determine the integer value of assets when we deal with portfolio optimization. In addition, one of the main concerns with most portfolio optimization is associated with the type of constraints considered in different models. In many cases, the resulted problem formulations do not yield in practical solutions. Therefore, it is necessary to apply some managerial decisions in order to make the results more practical. This paper presents a portfolio optimization based on an improved knapsack problem with the cardinality, floor and ceiling, budget, class, class limit and pre-assignment constraints for asset allocation. To handle the uncertainty associated with different parameters of the proposed model, we use robust optimization techniques. The model is also applied using some realistic data from US stock market. Genetic algorithm is also provided to solve the problem for some instances.


1.  Markowitz, H., “Portfolio selection”, The Journal of Finance, Vol.
7, No. 1, (1952), 77–91. 
2.  Markowitz, H. M., “Portfolio Selection: Efficient Diversification of
Investment”, John Wiley & Sons, New York, USA, (1959). 
3.  Corazza, M. and Favaretto, D., “On the existence of solutions to the
quadratic mixed-integer mean–variance portfolio selection
problem”, European Journal of Operational Research, Vol. 176,
No. 3, (2007), 1947–1960. 
4.  Li, H.L. and Tsai, J.F., “A distributed computation algorithm for
solving portfolio problems with integer variables”, European
Journal of Operational Research, Vol. 186, No.2, (2008),882–891. 
5.  Bonami, P. and Lejeune, M. A., “An exact solution approach for
portfolio optimization problems under stochastic and integer
constraints”, Operations Research, Vol. 57, No. 3, (2009), 650–670. 
6.  Castro, F., Gago, J., Hartillo, I., Puerto, J., and Ucha, J. M., “An
algebraic approach to integer portfolio problems”, European
Journal of Operational Research, Vol. 210, No.3, (2011), 647–659. 
7.  Adams, W. W., Adams, W. W., Loustaunau, P., ADAMS, W. H.,
and Adams, W. W., “An Introduction to Gröbner Bases”, American
Mathematical Soc, (1994). 
8.  Zymler, S., Rustem, B., and Kuhn, D., “Robust portfolio
optimization with derivative insurance guarantees”, European
Journal of Operational Research, Vol. 210, No.2, (2011), 410–424. 
9.  Scutellà, M. G. and Recchia, R., “Robust portfolio asset allocation
and risk measures”, Annals of Operations Research, Vol. 204,
No.1, (2013), 145–169. 
10.  Huang, J.-J., Tzeng, G.-H., and Ong, C.-S., “A novel algorithm for
uncertain portfolio selection”, Applied Mathematics and
computation, Vol. 173, No.1, (2006), 350–359. 
11. Gregory, C., Darby-Dowman, K., and Mitra, G., “Robust
optimization and portfolio selection: The cost of robustness”,
European Journal of Operational Research, Vol. 212, No.2,
(2011), 417–428. 
12.  Bertsimas, D. and Sim, M., “Robust discrete optimization and
network flows”, Mathematical Programming, Vol. 98, No. 1–3,
(2003), 49–71. 
13.  Bertsimas, D. and Sim, M., “The price of robustness”, Operations
Research, Vol. 52, No.1, (2004), 35–53. 
14.  Sadjadi, S. J., Gharakhani, M., and Safari, E., “Robust optimization
framework for cardinality constrained portfolio problem”, Applied
Soft Computing, Vol. 12, No. 1, (2012), 91–99. 
15.  Ben-Tal, A. and Nemirovski, A., “Robust convex optimization”,
Mathematics of Operations Research, Vol. 23, No. 4, (1998), 769–
16.  Ben-Tal,  A.  and  Nemirovski,  A.,  “Robust  solutions  of uncertain 
 linear programs”, Operations Research Letters, Vol. 25, No. 1,
(1999), 1–13. 
17.  Ghahtarani, A. and Najafi, A.A., “Robust goal programming for
multi-objective portfolio selection problem”, Economic Modelling,
Vol. 33, (2013), 588–592. 
18.  Kim, W. C., Kim, J. H., Mulvey, J. M., and Fabozzi, F. J., “Focusing
on the worst state for robust investing”, International Review of
Financial Analysis, Vol. 39, (2015), 19–31. 
19.  Maillet, B., Tokpavi, S., and Vaucher, B., “Global minimum
variance portfolio optimisation under some model risk: A robust
regression-based approach”, European Journal of Operational
Research, Vol. 244, No. 1, (2015), 289–299. 
20.  Huang, X. and Di, H., “Uncertain portfolio selection with
background risk”, Applied Mathematics and Computation, Vol.
276, (2016), 284–296. 
21.  Fernandes, B., Street, A., Valladão, D., and Fernandes, C., “An
adaptive robust portfolio optimization model with loss constraints
based on data-driven polyhedral uncertainty sets”, European
Journal of Operational Research, Vol. 255, No. 3, (2016), 961–
22.  Chen, C. and Zhou, Y., “Robust multiobjective portfolio with higher
moments”, Expert Systems with Applications, Vol. 100,
23.  Xidonas, P., Hassapis, C., Soulis, J., and Samitas, A., “Robust
minimum variance portfolio optimization modelling under scenario
uncertainty”, Economic Modelling, Vol. 64, (2017), 60–71. 
24.  Xidonas, P., Mavrotas, G., Hassapis, C., and Zopounidis, C.,
“Robust multiobjective portfolio optimization: A minimax regret
approach”, European Journal of Operational Research, Vol. 262,
No. 1, (2017), 299–305. 
25.  Huang, X., “Fuzzy chance-constrained portfolio selection”, Applied
Mathematics and Computation, Vol. 177, No. 2, (2006),500–507. 
26.  Li, X., Qin, Z., and Yang, L., “A chance-constrained portfolio
selection model with risk constraints”, Applied Mathematics and
Computation, Vol. 217, No. 2, (2010), 949–951. 
27.  Soyster, A. L., “Convex programming with set-inclusive constraints
and applications to inexact linear programming”, Operations
research, Vol. 21, No. 5, (1973), 1154–1157. 
28.  Ben-Tal, A. and Nemirovski, A., “Robust solutions of linear
programming problems contaminated with uncertain data”,
Mathematical Programming, Vol. 88, No. 3, (2000), 411–424. 
29.  Bertsimas, D. and Sim, M., “Tractable approximations to robust
conic optimization problems”, Mathematical Programming, Vol.
107, No. 1–2, (2006), 5–36. 
30.  Vaezi, F., Sadjadi, S. J., and Makui, A., “A portfolio selection model
based on the knapsack problem under uncertainty”, PLOS One, Vol.
14, No. 5, (2019), 1-19. 
31.  Chang, T.J., Meade, N., Beasley, J. E., and Sharaiha, Y. M.,
“Heuristics for cardinality constrained portfolio optimisation”,
Computers & Operations Research, Vol. 27, No. 13, (2000), 1271–
32.  Anagnostopoulos, K. P. and Mamanis, G., “Multiobjective
evolutionary algorithms for complex portfolio optimization
problems”, Computational Management Science, Vol. 8, No. 3,
(2011), 259–279. 
33.  Lenstra, J. K. and Kan, A. R., “Computational complexity of discrete
optimization problems”, Annals of Discrete Mathematics,Vol. 4,
(1979), 121–140. 
34.  Papadimitriou, C. H., “On the complexity of integer programming”,
Journal of the Assoclauon for Compuung Machinery, Vol. 28, No.
4, (1981) 765–768. 
35.  Kellerer, H., Pferschy, U., and Pisinger, D., “Introduction to NPCompleteness
of knapsack problems”, In: Knapsack Problems,
Springer, Berlin, Heidelberg, (2004), 483–493. 
36.  Khuri, S., Bäck, T., and Heitko╠łtter, J., “The zero/one multiple
knapsack problem and genetic algorithms”, In Proceedings of the
1994 ACM Symposium on Applied Computing, ACM, (1994), 188–
37.  Holland, J.H., “Adaptation in Natural and Artificial Systems: An
Introductory Analysis with Applications to Biology, Control, and
Artificial Intelligence”, MIT press, (1992). 
38.  Gen, M. and Cheng, R., “Genetic Algorithms and Engineering
Optimization”, John Wiley & Sons, (2000). 
39.  Coello, C.A.C., “Theoretical and numerical constraint-handling
techniques used with evolutionary algorithms: a survey of the state
of the art”, Computer Methods in Applied Mechanics and
Engineering, Vol. 191, No. 11–12, (2002), 1245–1287. 
40.  Mitchell, M., “An Introduction to Genetic Algorithms”, MIT press,
41.  Sivanandam, S.N. and Deepa, S.N., “Genetic algorithms”, In:
Introduction to Genetic Algorithms, Springer, Berlin, Heidelberg,
(2008), 15–37. 
42.  Back, T., “Evolutionary Algorithms in Theory and Practice:
Evolution Strategies, Evolutionary Programming, Genetic
Algorithms”, Oxford university press, (1996).