Anyone do integer optimization?

Water Cooler Investing
#1

I’m just writing up some support code to do something I thought would be simple, but turns out to be trickier than I expected.

Basically, if my process generates target weights for a portfolio, but I am constrained by integer share or contract sizes, I want to find the combination of integer shares that fits my budget constraint (long only in this case) and optimizes some value (say Sharpe ratio).

I figured that I’d find the non-integer share/contract counts at the optimal, based on my system criteria, then expand a search sphere (technically a hypersphere) around that point until I find the first point inside that consists of only integers. But I discover that I still need to find a way to compute the nearest all-integer points to sample, and it’s possible that a point farther away might actually have a better objective value (if the optimal falls away faster in one direction than the other).

Alternately, I figured I’d take some sphere around the theoretically optimal point and search all integer-only point, then compute the objective function (e.g. sharpe ratio) for each and then select the best one. Again, finding the nearest all-integer points is the hang-up.

Apparently I am too dumb to figure out how to do either. Have any of you MFE or CQF types done this?

I’m thinking that maybe what I need to do is to take the highest priced share or contract, find the integer that is just above and below the non-integer target number, then expand that number by one to either side (so if the target calls for 8.1 contracts, it will take 8 and 9 as the next-door integers, and expand by one each way to get 7 through 10). Then I look at the smaller cost contracts and figure out what integer spreads * contract price cover the same price range. Repeat for each asset. Then go through each combination and compute the objective function, skipping the calculation for each set of points that doesn’t fit the budget constraint. – this is a brute force solution, but it seems highly inefficient. Surely there is something more elegant.

In practice, I’d been approximating manually, and that’s been ok, but I figured that it’d be nice to get the machine to do it for me, and I thought I would ask the quantsters here if they have a solution (either a description of an algorithm, a reference, or even a code library that does this).

Any ideas? maratikus? jmh? ohai? anyone else?

#2

You said on an earlier post that you calculate the covariance matrix. Using that, you could set up a integer programming solver to minimize the tracking error between your ideal portfolio and the one that can actually be constructed, subject to typical constraints plus the integer requirement.

I did a simple example in excel to minimize the tracking error such that weights are rounded to tenths. All that is required is that the adjustable cells are integers, so it just requires an extra step where you optimize over some integers and calculate the weights and tracking error using a transformation of the integers.

In practice, it may be easier to do this in terms of dollars and holdings rather than weights (so you would need to adjust your covariance matrix and target portfolio accordingly, allowing for decimals in the target portfolio). For instance, you could set it up so that you invest in x holdings for each asset, each 1 holding could represent the lowest amount you are willing to trade (like 100 shares of stock or 1 futures contract) and then you have a price associated with this holding that adds up to how much you are willing to invest. This makes things somewhat simpler since then you don’t have to worry about differences between types of instruments and account for prices easier.

#3

Thanks jmh. I forgot that Solver had an integer-only constraint setting that you can use. And most other optimizers have them too.

I actually had been doing pure volatility weighting (either with an implicit 0 correlation or 1 correlation assumption). This is simpler to solve and therefore doesn’t need an optimizer, and was done in part so I could run backtests in excel without hundreds of calls to Solver.

But then I ran into the problem that the integer contracts constraint requires some kind of optimization.

I figured since I wrote the weighting algorithm without requiring a separate library, and that I had the local neighborhood via the non-integer target weights or shares, I should be able to write the integer optimization part fairly easily too, but it turns out not to be the case. So maybe reverting to a standard optimizer and turning the integer contraint on is the right way to do it.

#4

As I see the simplest solution to code is to calculate all possible portfolios within your budget and rank them according to your criterias, might not be the fastest solution but certainly works