Skip to main content
2 of 4
added 246 characters in body
RobPratt
  • 5.4k
  • 1
  • 15
  • 25

As @ManfredWeis noted, the objective is equivalent to minimizing $\sum_{i=1}^K \frac{x_i^2}{y_i}$. A natural reformulation introduces binary decision variables $u_{ij}$ for $i\in\{1,\dots,K\}$ and $j\in \{0,\dots, X\}$ and $v_{ik}$ for $i\in\{1,\dots,K\}$ and $k\in \{1,\dots, Y\}$. The problem is to minimize the quadratic function $$\sum_{i=1}^K \sum_{j=0}^X \sum_{k=1}^Y \frac{j^2}{k} u_{ij} v_{ik} \tag1\label1$$ subject to linear constraints \begin{align} \sum_i x_i &= X \\ \sum_i y_i &= Y \\ x_i &\le y_i &&\text{for all $i$} \\ \sum_j u_{ij} &= 1 &&\text{for all $i$} \\ \sum_j j u_{ij} &= x_i &&\text{for all $i$} \\ \sum_k v_{ik} &= 1 &&\text{for all $i$} \\ \sum_k k v_{ik} &= y_i &&\text{for all $i$} \end{align} You can call an MIQP (or BQP) solver.

Alternatively, you can linearize \eqref{1} by introducing nonnegative variables $w_{ijk}$ to represent the product $u_{ij} v_{ik}$. You can then minimize $$\sum_{i=1}^K \sum_{j=0}^X \sum_{k=1}^Y \frac{j^2}{k} w_{ijk} \tag{1p}\label{1'}$$ The usual linearization imposes linear constraints \begin{align} w_{ijk} &\ge u_{ij} + v_{ik} - 1 \tag2\label2 \\ w_{ijk} &\le u_{ij} \tag3\label3 \\ w_{ijk} &\le v_{ik} \tag4\label4 \end{align} But you can omit \eqref{3} and \eqref{4} because the objective will drive these constraints to be satisfied naturally.

A more compact linearization instead replaces \eqref{2} with \begin{align} \sum_j w_{ijk} &= v_{ik} &&\text{for all $i$ and $k$} \\ \sum_k w_{ijk} &= u_{ij} &&\text{for all $i$ and $j$} \end{align}

It is also worth noting that without the linking constraints $\sum_i x_i = X$ and $\sum_i y_i = Y$ the problem decomposes into independent problems, one for each $i$. So Dantzig-Wolfe decomposition or Lagrangian relaxation might perform well.

RobPratt
  • 5.4k
  • 1
  • 15
  • 25