Understanding Approximate Solutions

When running certain optimizations, why do I get an approximate solution message?

A
Updated over a week ago

When running some optimizations, a message may be returned as follows:

"Warning: Solution is approximate. The best solution given the time limit has been provided. To possibly increase solution quality, try increasing maxTime."

There is a class of optimizations known as ‘Mixed Integer Programming’ (MIP) that are very hard to solve. Specifically, these optimizations are discrete in nature and thus are subject to the law of combinatorics which scales on the order of factorials. A very simple example would be to take all names in the Russell 3000 (assume there are actually 3000 names) and only hold 10 names to minimize total risk. In this case there are 1.6E28 different portfolios of 10 names that could possibly have the lowest risk!

Instead of using brute force to look at all of these portfolios which would take an extraordinary amount of time, Omega Point uses advanced optimization heuristics to quickly weed out the suboptimal portfolios and focus on the portfolios with possible better solutions. As the optimization is ran, we find better and better solutions while also eliminating solutions that are clearly worse and/or infeasible relative to the solution we have already found. While there does exist a ‘true mathematically optimal’ solution, in some cases it can take a very very long time to find this exact solution. Furthermore, the optimizer quickly converges closer to the ‘true mathematically optimal’ solution and only incrementally increases solution quality per time spent searching for better solutions - i.e. there are diminishing returns to solution quality per unit of time.

This process for a constrained risk minimization problem can be visualized as follows:

The time spent searching for a solution is controlled via the API option ‘maxTime’ and has a limit of 60 seconds in the standard production/development environment. The following constraints in Omega Point are MIP in nature: minTrade, maxPositions, minConcentration, longOrShort securities, longMarketValue, and shortMarketValue. In the case one is using one or more of these constraints, the number of possible solution combinations increases and thus the problem becomes much harder to solve.

The message warning of an ‘approximate solution’ is provided precisely to indicate the trade-off being made: Omega Point tries to find a very good solution very quickly. Just because the solution is ‘approximate’ doesn’t mean the solution is ‘bad’ - it simply means Omega Point has returned the best solution found given the time provided. In the high majority of cases, increasing maxTime would only provide very slightly better solutions. Turning off all MIP constraints (when possible) can often help provide users a sanity check with how far off the idealized non-MIP solution is from the MIP solution.

This can also mean that given the same exact optimization, solutions returned can vary slightly. In most cases the differences in solutions will be very small - on the order of 1E-4 in terms of numerical tolerance - but hard to notice by the human eye looking at portfolio positions. Omega Point also offers ‘Optimization Burst’ capabilities which provides extended run times for those looking to run lots of very hard to solve problems more quickly - the maxTime limit is triple that of the normal production environment.