Portfolio Selection Optimization Problem

Principles learned

  • Add float decision variables

  • Minimize a non-linear objective

Problem

../_images/portfolio.svg

This portfolio problem is a simplification of the Markowitz portfolio selection optimization problem. A portfolio has to be invested among a set of stocks. The return for each stock and the covariance matrix of risk are known. We want to reach an expected profit, minimizing the risk of the portfolio. The expected profit is fixed.

The goal is to find the part of the portfolio to invest in each stock. All the portfolio has to be used.

Download the example


Data

The format of the data files is as follows:

  • First line: expected profit (in percentage of the portfolio)

  • Second line: number of stocks

  • Covariance matrix representing the balance risk for each pair of stocks

  • Last line: for each stock, the variation of its price

Program

The decision variables are floating variables that model the proportion of the portfolio invested in each stock.

The return of the portfolio is the weighted sum of all the profits of the stocks, where the weights are the proportion of the portfolio dedicated to each stock.

The portfolio risk is a convex quadratic function, obtained by summing for each stock pair the product between the proportions invested and the corresponding covariance.

The constraints are that the whole portfolio has to be invested and that the profit cannot be less than the expected profit. The objective of the problem consists in minimizing the risk.

Execution:
localsolver portfolio.lsp inFileName=instances/small_01.txt [outFileName=] [lsTimeLimit=]
use io;
use random;

/* Read instance data */
function input() {
    local usage = "Usage: localsolver portfolio.lsp inFileName=instanceFile"
            + " [outFileName=outputFile] [lsTimeLimit=timeLimit]";

    if (inFileName == nil) throw usage;

    inFile = io.openRead(inFileName);

    // Expected profit, in percentage of the portfolio
    expectedProfit = inFile.readDouble();

    // Number of stocks
    nbStocks = inFile.readInt();

    // Covariance among the stocks
    sigmaStocks[s in 0..nbStocks-1][t in 0..nbStocks-1] = inFile.readDouble();

    // Variation of the price of each stock
    deltaStock[s in 0..nbStocks-1] = inFile.readDouble();

    inFile.close();
}

/* Declare the optimization model */
function model() {
    // Proportion of the portfolio invested in each stock
    portfolioStock[0..nbStocks-1] <- float(0, 1);

    // Risk of the portfolio
    risk <- sum[s in 0..nbStocks-1][t in 0..nbStocks-1](portfolioStock[s] *
        portfolioStock[t] * sigmaStocks[s][t]);

    // Return of the portfolio in percentage
    profit <- sum[s in 0..nbStocks-1](portfolioStock[s] * deltaStock[s]);

    // All the portfolio is used
    constraint sum[s in 0..nbStocks-1](portfolioStock[s]) == 1.0;

    // The profit is at least the expected profit
    constraint profit >= expectedProfit;

    // Minimize the risk
    minimize risk;

}

/* Parameterize the solver */
function param() {
    if (lsTimeLimit == nil) lsTimeLimit = 60;
}

/* Write the solution in a file with the following format:
 *  - for each stock, the proportion of the porfolio invested
    - the final profit in percentage of the portfolio */
function output() {
    if (outFileName != nil) {
        outFile = io.openWrite(outFileName);
        println("Solution written in file ", outFileName);
        for [s in 0..nbStocks-1] {
            local proportion = portfolioStock[s].value;
            outFile.println("Stock ", s, ": ", round(proportion * 1000) / 10, "%");
        }
        outFile.println("Profit: " + profit.value + "%");
    }
}
Execution (Windows)
set PYTHONPATH=%LS_HOME%\bin\python
python portfolio.py instances\small_01.txt
Execution (Linux)
export PYTHONPATH=/opt/localsolver_11_5/bin/python
python portfolio.py instances/small_01.txt
from re import S
import localsolver
import sys


def read_instance(filename):
    with open(filename) as f:
        lines = f.readlines()

    first_line = lines[0].split()

    # Expected profit, in percentage of the portfolio
    expected_profit = float(first_line[0])

    second_line = lines[2].split()

    # Number of stocks
    nb_stocks = int(second_line[0])

    # Covariance among the stocks
    sigma_stocks = [[0 for i in range(nb_stocks)] for j in range(nb_stocks)]
    for s in range(nb_stocks):
        line = lines[s+4].split()
        for t in range(nb_stocks):
            sigma_stocks[s][t] = float(line[t])

    # Variation of the price of each stock
    delta_stock = [0 for i in range(nb_stocks)]
    line = lines[nb_stocks+5].split()
    for s in range(nb_stocks):
        delta_stock[s] = float(line[s])
        print(delta_stock[s])

    return expected_profit, nb_stocks, sigma_stocks, delta_stock


def main(instance_file, output_file, time_limit):
    expected_profit, nb_stocks, sigma_stocks, delta_stock = read_instance(
        instance_file)

    with localsolver.LocalSolver() as ls:
        #
        # Declare the optimization model
        #
        model = ls.model

        # Proportion of the portfolio invested in each stock
        portfolio_stock = [model.float(0, 1) for s in range(nb_stocks)]

        # Risk of the portfolio
        risk = model.sum(portfolio_stock[s] * portfolio_stock[t] * sigma_stocks[s][t]
                         for t in range(nb_stocks) for s in range(nb_stocks))

        # Return of the portfolio in percentage
        profit = model.sum(portfolio_stock[s] * delta_stock[s]
                           for s in range(nb_stocks))

        # All the portfolio is used
        model.constraint(
            model.sum(portfolio_stock[s] for s in range(nb_stocks)) == 1.0)

        # The profit is at least the expected profit
        model.constraint(profit >= expected_profit)

        # Minimize the risk
        model.minimize(risk)

        model.close()

        # Parameterize the solver
        ls.param.time_limit = time_limit

        ls.solve()

        # Write the solution in a file with the following format:
        # - for each stock, the proportion of the porfolio invested
        # - the final profit in percentage of the portfolio
        if output_file != None:
            with open(output_file, "w") as f:
                print("Solution written in file", output_file)
                for s in range(nb_stocks):
                    proportion = portfolio_stock[s].value
                    f.write("Stock " + str(s+1) + ": " + str(round(proportion * 100, 1))
                            + "%" + "\n")
                f.write("Profit: " + str(round(profit.value, 4)) + "%")


if __name__ == '__main__':
    if len(sys.argv) < 2:
        print(
            "Usage: python portfolio.py instance_file [output_file] [time_limit]")
        sys.exit(1)

    instance_file = sys.argv[1]
    output_file = sys.argv[2] if len(sys.argv) >= 3 else None
    time_limit = int(sys.argv[3]) if len(sys.argv) >= 4 else 60
    main(instance_file, output_file, time_limit)
Compilation / Execution (Windows)
cl /EHsc portfolio.cpp -I%LS_HOME%\include /link %LS_HOME%\bin\localsolver115.lib
portfolio instances\small_01.txt
Compilation / Execution (Linux)
g++ portfolio.cpp -I/opt/localsolver_11_5/include -llocalsolver115 -lpthread -o portfolio
./portfolio instances/small_01.txt
#include "localsolver.h"
#include <algorithm>
#include <fstream>
#include <iostream>
#include <limits>
#include <numeric>
#include <vector>

using namespace localsolver;

class Portfolio {
private:
    // Expected profit, in percentage of the portfolio
    float expectedProfit;
    // Number of stocks
    int nbStocks;
    // Covariance among the stocks
    std::vector<std::vector<float>> sigmaStocks;
    // Variation of the price of each stock
    std::vector<float> deltaStock;

    // LocalSolver
    LocalSolver localsolver;
    // Proportion of the portfolio invested in each stock
    std::vector<LSExpression> portfolioStock;
    // Return of the portfolio in percentage
    LSExpression profit;

public:
    Portfolio() : localsolver() {}

    void readInstance(const std::string &fileName) {
        std::ifstream infile;
        infile.exceptions(std::ifstream::failbit | std::ifstream::badbit);
        infile.open(fileName.c_str());

        infile >> expectedProfit;
        infile >> nbStocks;

        for (int s = 0; s < nbStocks; s++) {
            sigmaStocks.push_back(std::vector<float>(nbStocks, 0.0));
            for (int t = 0; t < nbStocks; t++) {
                infile >> sigmaStocks[s][t];
            }
        }

        deltaStock = std::vector<float>(nbStocks, 0.0);
        for (int s = 0; s < nbStocks; s++) {
            infile >> deltaStock[s];
            deltaStock[s] = deltaStock[s];
        }

        infile.close();
    }

    void solve(int timeLimit) {
        // Declare the optimization model
        LSModel model = localsolver.getModel();

        // Proportion of the portfolio invested in each stock
        portfolioStock.resize(nbStocks);
        for (int s = 0; s < nbStocks; s++)
            portfolioStock[s] = model.floatVar(0.0, 1.0);

        // Risk of the portfolio
        LSExpression risk = model.sum();
        for (int s = 0; s < nbStocks; s++) {
            for (int t = 0; t < nbStocks; t++) {
                risk.addOperand(portfolioStock[s] * portfolioStock[t] * sigmaStocks[s][t]);
            }
        }

        // Return of the portfolio in percentage
        profit = model.sum();
        for (int s = 0; s < nbStocks; s++) {
            profit.addOperand(portfolioStock[s] * deltaStock[s]);
        }

        // All the portfolio is used
        model.constraint(model.sum(portfolioStock.begin(), portfolioStock.end()) == 1.0);

        // The profit is at least the expected profit
        model.constraint(profit >= expectedProfit);

        // Minimize the risk
        model.minimize(risk);

        model.close();

        // Parameterize the solver
        localsolver.getParam().setTimeLimit(timeLimit);

        localsolver.solve();
    }

    /* Write the solution in a file with the following format:
        - for each stock, the proportion of the porfolio invested
        - the final profit in percentage of the portfolio */
    void writeSolution(const std::string &fileName) {
        std::ofstream outfile(fileName.c_str());
        if (!outfile.is_open()) {
            std::cerr << "File " << fileName << " cannot be opened." << std::endl;
            exit(1);
        }
        std::cout << "Solution written in file " << fileName << std::endl;

        for (unsigned int s = 0; s < nbStocks; ++s) {
            float proportion = portfolioStock[s].getDoubleValue();
            outfile << "Stock " << s + 1 << ": " << round(proportion * 1000) / 10 << "%" << std::endl;
        }
        outfile << "Profit: " << profit.getDoubleValue() << "%" << std::endl;
        outfile.close();
    }
};

int main(int argc, char **argv) {
    if (argc < 2) {
        std::cout << "Usage: portfolio instanceFile [outputFile] [timeLimit]" << std::endl;
        exit(1);
    }

    const char *instanceFile = argv[1];
    const char *outputFile = argc > 2 ? argv[2] : NULL;
    const char *strTimeLimit = argc > 3 ? argv[3] : "60";

    Portfolio model;
    try {
        model.readInstance(instanceFile);
        const int timeLimit = atoi(strTimeLimit);
        model.solve(timeLimit);
        if (outputFile != NULL)
            model.writeSolution(outputFile);
        return 0;
    } catch (const std::exception &e) {
        std::cerr << "An error occurred: " << e.what() << std::endl;
        return 1;
    }
}
Compilation / Execution (Windows)
copy %LS_HOME%\bin\localsolvernet.dll .
csc Portfolio.cs /reference:localsolvernet.dll
Portfolio instances\small_01.txt
using System;
using System.IO;
using System.Linq;
using localsolver;

public class Portfolio : IDisposable
{
    // Expected profit, in percentage of the portfolio
    private float expectedProfit;

    // Number of stocks
    private int nbStocks;

    // Covariance among the stocks
    private float[][] sigmaStocks;

    // Variation of the price of each stock
    private float[] deltaStock;

    // LocalSolver
    private LocalSolver localsolver;

    // Proportion of the portfolio invested in each stock
    private LSExpression[] portfolioStock;

    // Return of the portfolio in percentage
    private LSExpression profit;

    public Portfolio()
    {
        localsolver = new LocalSolver();
    }

    public void ReadInstance(string fileName)
    {
        using (StreamReader input = new StreamReader(fileName))
        {
            char[] separators = new char[] { '\t', ' ' };
            string[] splitted = input
                .ReadLine()
                .Split(separators, StringSplitOptions.RemoveEmptyEntries);
            expectedProfit = float.Parse(splitted[0]);
    
            input.ReadLine();
            splitted = input
                .ReadLine()
                .Split(separators, StringSplitOptions.RemoveEmptyEntries);
            nbStocks = int.Parse(splitted[0]);

            sigmaStocks = new float[nbStocks][];
            input.ReadLine();
            for (int s = 0; s < nbStocks; ++s)
            {
                sigmaStocks[s] = new float[nbStocks];
                splitted = input
                    .ReadLine()
                    .Split(separators, StringSplitOptions.RemoveEmptyEntries);
                for (int t = 0; t < nbStocks; ++t)
                    sigmaStocks[s][t] = float.Parse(splitted[t]);
            }

            input.ReadLine();
            splitted = input
                .ReadLine()
                .Split(separators, StringSplitOptions.RemoveEmptyEntries);

            deltaStock = new float[nbStocks];
            for(int s = 0; s < nbStocks; ++s)
                deltaStock[s] = float.Parse(splitted[s]);
        }
    }

    public void Dispose()
    {
        localsolver.Dispose();
    }

    public void Solve(int timeLimit)
    {
        // Declare the optimization model
        LSModel model = localsolver.GetModel();

        // Proportion of the portfolio invested in each stock
        portfolioStock = new LSExpression[nbStocks];
        for(int s = 0; s < nbStocks; s++)
            portfolioStock[s] = model.Float(0.0, 1.0);

        // Risk of the portfolio
        LSExpression risk = model.Sum();
        for(int s = 0; s < nbStocks; s++)
        {
            for(int t = 0; t < nbStocks; t++)
                risk.AddOperand(portfolioStock[s] * portfolioStock[t] * sigmaStocks[s][t]);
        }

        // Return of the portfolio in percentage
        profit = model.Sum();
        for(int s = 0; s < nbStocks; s++)
            profit.AddOperand(portfolioStock[s] * deltaStock[s]);

        // All the portfolio is used
        model.Constraint(model.Sum(portfolioStock) == 1.0);

        // The profit is at least the expected profit
        model.Constraint(profit >= expectedProfit);

        // Minimize the risk
        model.Minimize(risk);

        model.Close();

        // Parameterize the solver
        localsolver.GetParam().SetTimeLimit(timeLimit);

        localsolver.Solve();
    }

    /* Write the solution in a file with the following format:
     *  - for each stock, the proportion of the porfolio invested
        - the final profit in percentage of the portfolio */
    public void WriteSolution(string fileName)
    {
        using (StreamWriter output = new StreamWriter(fileName))
        {
            Console.WriteLine("Solution written in file " + fileName);
            for (int s = 1; s <= nbStocks; ++s)
            {
                double proportion = portfolioStock[s - 1].GetDoubleValue();
                output.WriteLine("Stock " + s + ": " +
                    Math.Round(proportion * 100, 1) + "%");
            }
            output.WriteLine("Profit: " + Math.Round(profit.GetDoubleValue(), 4) + "%");
        }
    }

    public static void Main(string[] args)
    {
        if (args.Length < 1)
        {
            Console.WriteLine("Usage: Portfolio instanceFile [outputFile] [timeLimit]");
            System.Environment.Exit(1);
        }

        string instanceFile = args[0];
        string outputFile = args.Length > 1 ? args[1] : null;
        string strTimeLimit = args.Length > 2 ? args[2] : "60";

        using (Portfolio model = new Portfolio())
        {
            model.ReadInstance(instanceFile);
            model.Solve(int.Parse(strTimeLimit));
            if (outputFile != null)
                model.WriteSolution(outputFile);
        }
    }
}
Compilation / Execution (Windows)
javac Portfolio.java -cp %LS_HOME%\bin\localsolver.jar
java -cp %LS_HOME%\bin\localsolver.jar;. Portfolio instances\small_01.txt
Compilation / Execution (Linux)
javac Portfolio.java -cp /opt/localsolver_11_5/bin/localsolver.jar
java -cp /opt/localsolver_11_5/bin/localsolver.jar:. Portfolio instances/small_01.txt
import java.io.File;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Scanner;

import localsolver.LSExpression;
import localsolver.LSModel;
import localsolver.LocalSolver;

public class Portfolio {
    // Expected profit, in percentage of the portfolio
    private float expectedProfit;
    // Number of stocks
    private int nbStocks;
    // Covariance among the stocks
    private float[][] sigmaStocks;
    // Variation of the price of each stock
    private float[] deltaStock;

    // LocalSolver
    private final LocalSolver localsolver;
    // Proportion of the portfolio invested in each stock
    private LSExpression[] portfolioStock;
    // Return of the portfolio in percentage
    private LSExpression profit;

    public Portfolio(LocalSolver localsolver) throws IOException {
        this.localsolver = localsolver;
    }

    public void readInstance(String fileName) throws IOException {
        try (Scanner input = new Scanner(new File(fileName))) {
            expectedProfit = input.nextFloat();
            nbStocks = input.nextInt();

            sigmaStocks = new float[nbStocks][];
            for (int s = 0; s < nbStocks; ++s) {
                sigmaStocks[s] = new float[nbStocks];
                for (int t = 0; t < nbStocks; ++t) {
                    sigmaStocks[s][t] = input.nextFloat();
                }
            }

            deltaStock = new float[nbStocks];
            for (int s = 0; s < nbStocks; ++s) {
                deltaStock[s] = input.nextFloat();
            }
        }

    }

    public void solve(int timeLimit) {
        // Declare the optimization model
        LSModel model = localsolver.getModel();

        // Proportion of the portfolio invested in each stock
        portfolioStock = new LSExpression[nbStocks];
        for (int s = 0; s < nbStocks; s++) {
            portfolioStock[s] = model.floatVar(0.0, 1.0);
        }

        // Risk of the portfolio
        LSExpression risk = model.sum();
        for (int s = 0; s < nbStocks; s++) {
            for (int t = 0; t < nbStocks; t++) {
                LSExpression sigmaST = model.createConstant(sigmaStocks[s][t]);
                risk.addOperand(model.prod(portfolioStock[s], portfolioStock[t], sigmaST));
            }
        }

        // Return of the portfolio in percentage
        profit = model.sum();
        for (int s = 0; s < nbStocks; s++) {
            LSExpression deltaS = model.createConstant(deltaStock[s]);
            profit.addOperand(model.prod(portfolioStock[s], deltaS));
        }

        // All the portfolio is used
        LSExpression one = model.createConstant(1.0);
        model.constraint(model.eq(model.sum(portfolioStock), one));

        // The profit is at least the expected profit
        model.constraint(model.geq(profit, expectedProfit));

        // Minimize the risk
        model.minimize(risk);

        model.close();

        // Parameterize the solver
        localsolver.getParam().setTimeLimit(timeLimit);

        localsolver.solve();
    }

    /*
     * Write the solution in a file with the following format:
     * - for each stock, the proportion of the porfolio invested
     * - the final profit in percentage of the portfolio
     */
    public void writeSolution(String fileName) throws IOException {
        try (PrintWriter output = new PrintWriter(fileName)) {
            System.out.println("Solution written in file " + fileName);
            for (int s = 1; s <= nbStocks; ++s) {
                output.write("Stock " + s + ": " + portfolioStock[s - 1].getDoubleValue() * 100 + "% \n");
            }
            output.write("Profit: " + profit.getDoubleValue() + "% \n");
        }
    }

    public static void main(String[] args) {
        if (args.length < 1) {
            System.out.println("Usage: java Portfolio instanceFile [outputFile] [timeLimit]");
            System.exit(1);
        }

        String instanceFile = args[0];
        String outputFile = args.length > 1 ? args[1] : null;
        String strTimeLimit = args.length > 2 ? args[2] : "60";

        try (LocalSolver localsolver = new LocalSolver()) {
            Portfolio model = new Portfolio(localsolver);
            model.readInstance(instanceFile);
            model.solve(Integer.parseInt(strTimeLimit));
            if (outputFile != null) {
                model.writeSolution(outputFile);
            }
        } catch (Exception ex) {
            System.err.println(ex);
            ex.printStackTrace();
            System.exit(1);
        }
    }
}