A SAT encoding for the portfolio selection problem

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.