Integer allocation problem alternative to MI-SOCP?

62 Views Asked by At

Can the following problem be solved without needing to use a MI-SOCP solver? I think I can code it as just a simple parallel branch-and-bound search but I'm not sure if the performance will be close to MI-SOCP for low dimensions or scale well.

A number of integer share quantities $q_i$ bought at a price $p_i$ need to be integer allocated $a_{ij}$ to a number of accounts with a given total quantity $n_j = \sum_i a_{ij}$ such that the accounts get the most similar possible average prices $\frac {\sum_i a_{ij} p_i}{n_j}$.

1

There are 1 best solutions below

3
On BEST ANSWER

Let $\bar{p} = \frac{\sum_i p_i}{\sum_j n_j}$ be the global average price. Introduce nonnegative surplus $s_j$ and slack $t_j$ variables. Here are two linear approaches.

  • Minimize the sum of absolute differences to $\bar{p}$: minimize $\sum_j (s_j + t_j)$ subject to \begin{align} \sum_j a_{ij} &= q_i &\text{for all $i$} \\ \sum_i a_{ij} &= n_j &\text{for all $j$} \\ \frac{\sum_i p_i a_{ij}}{n_j} - s_j + t_j &= \bar{p} &\text{for all $j$} \end{align}

  • Minimize the maximum absolute difference to $\bar{p}$: minimize $z$ subject to \begin{align} \sum_j a_{ij} &= q_i &\text{for all $i$} \\ \sum_i a_{ij} &= n_j &\text{for all $j$} \\ \frac{\sum_i p_i a_{ij}}{n_j} - s_j + t_j &= \bar{p} &\text{for all $j$} \\ s_j + t_j &\le z &\text{for all $j$} \end{align}