Understanding MIPs, Approximate Solutions, & Optimizer points

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.

Optimizer points may trigger an API Rate Limit either because a single query is very complex in nature. This happens when the query points is above the 5000 points API rate threshold, which can incur when using MIP constraints. Relaxing maxTime is a good first step to reduce the points complexity.

Similarly, when backtesting / iterating quickly, these high frequency requests can hit exceed the 50,000 points allocation and trigger a 10-minute cooldown period.

To help customers with large research and optimization needs, Omega Point 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. The Burst capability effectively reduces the points complexity of a single optimization so either more complex or more optimization iterations can occur within our API rate limit.

Please reach out to your customer support manager for more information about this Optimization Burst package.
​