I am trading futures contracts in baskets at ratios that I compute by some method. Suppose there are $n$ contracts in a basket, and the ratio is given by $\mathbf{r}\in \mathbb{Z}^n$, so that the price of a basket is given by $\mathbf{r} \cdot \mathbf{p}$, where $\mathbf{p}$ is the price vector of the outright contract.
The problem is this: I can also buy baskets of two contracts called Exchange-Traded Spreads (ETSs) directly from the futures exchange, so if I want, I can incorporate ETSs into the construction of my basket. Buying a single ETS for contracts $i$ and $j$ puts $1$ contract $i$ in my basket, and subtracts $1$ contract $j$ from my basket. I'll denote this ETS by $E_{ij}$. So for example, if my ratio was $\mathbf{r}=(1, -1, 1, -1)$, I could accomplish this by buying $E_{12}$ and $E_{34}$, i.e. $\mathbf{r}=E_{12}+E_{34}$. Some ratios are not conducive to being built entirely from ETSs though. For example, for $\mathbf{r}=(1, -1, 1)$, I would not be able to construct it just from ETSs (I don't think, at least). However, I could construct it using a combination of ETSs and outrights, for instance by buying $E_{12}$ and then buying one unit of the third contract, i.e. $\mathbf{r}=E_{12}+c_3$ where $c_3=(0,0,1)$.
For various reasons, it is preferable to minimize number of outright contracts contributing to the basket -- if possible, it is preferable to build the basket only out of ETSs. Is there an algorithm or some methods which would help me achieve something like this? I have a simple algorithm that finds an ETS construction for $n=3$, but it doesn't seem to scale up.
I think the problem can be stated like this:
Minimize $\sum_{i=1}^n|a_i|$ subject to $\mathbf{r}=\sum_{i<j} e_{ij}E_{ij} + \sum_{i=1}^n a_i c_i$.
It's very simple. The number of outright contracts required is $\textbf{r}\cdot (1,1,...,1)$, i.e. the sum of the terms in r.
The reason is that each ETS doesn't change that sum, while each outright contract adds 1.
A good algorithm to construct a specific r would be to take the largest terms in r and use enough outright buys to lower the sum of terms to 0, and then match up positive terms with negative terms via ETS's.
Example: (3,1,-1,-1) adds up to 2. So consider the option of 2 outright buys (I.e. $2c_1$) leaving (1,1,-1,-1) which can be written as E13+E24, for instance.