This paper proposes a transformation of the portfolio selection problem into SAT. SAT was the first problem to be shown to be NP-complete, and has been widely investigated ever since. We derive the SAT instances from the Portfolio Selection ones using the concept of cover, and reduce their size via established reduction techniques. The resulting instances are based on the use of variance as the main risk measure, and are solved via both a standard SAT solver and an adaptive genetic algorithm. Results show that adaptive genetic algorithms are effective in solving these variance-based instances. Further work will be devoted to investigate other SAT formulations based on different risk measures.

A SAT encoding for the portfolio selection problem

Raffaele Pesenti;
In corso di stampa

Abstract

This paper proposes a transformation of the portfolio selection problem into SAT. SAT was the first problem to be shown to be NP-complete, and has been widely investigated ever since. We derive the SAT instances from the Portfolio Selection ones using the concept of cover, and reduce their size via established reduction techniques. The resulting instances are based on the use of variance as the main risk measure, and are solved via both a standard SAT solver and an adaptive genetic algorithm. Results show that adaptive genetic algorithms are effective in solving these variance-based instances. Further work will be devoted to investigate other SAT formulations based on different risk measures.
In corso di stampa
in corso di stampa
File in questo prodotto:
File Dimensione Formato  
A_SAT_encoding_for_the_portfolio_selection_problem.pdf

non disponibili

Tipologia: Documento in Pre-print
Licenza: Accesso chiuso-personale
Dimensione 266.87 kB
Formato Adobe PDF
266.87 kB Adobe PDF   Visualizza/Apri

I documenti in ARCA sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10278/5047722
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact