Minimizing the median, integer programming

Question

Suppose we want to $ min_i$ median$(a_i)$

$a_i$ are real numbers

Does someone know how to pose this as an integer programming problem or point me in the direction of a resource?

Answer 1

EDIT: Removing a simpler model which was incorrect.

The way median

y = median(a)

is implemented in the optimization modelling toolbox YALMIP is roughly by (writing in MATLAB pseudo code)

y = s(length(a)/2); s = sort(a);

Hence, to model median we need to model sort. This can be done by introducing a binary matrix Z with

s = Z*a, sum(Z) = 1, sum(Z') = 1, diff(s) >= 0

and we're down to model binary times continuous, which is done using standard big-M methods.

Answer 2

Given bounded variables $a_{1},\dots,a_{N}$ subject to some constraints, you can minimize their median with $N$ additional binary variables $z_{1},\dots,z_{N}$ and one additional continuous variable $y$ if $N$ is odd (or if you are a bit sloppy about the definition of ``median''). You minimize $y$ subject to the constraints $y\ge a_{i}-M_{i}z_{i},\, i=1,\dots,N$ and $\sum_{i=1}^{N}z_{i}=\left\lfloor \frac{N}{2}\right\rfloor $, where the $M_{i}$ are suitably large constants. The constraint force $y$ to be greater than or equal to $\left\lceil \frac{N}{2}\right\rceil $ of the $a_{i}$; the objective will result in those being the $\left\lceil \frac{N}{2}\right\rceil $ smallest of them and in $y$ being no bigger than the largest of that set, making $y$ the median.

If $N$ is even and $a_{(1)},\dots,a_{(N)}$ is the order statistic of the $a$ variables, the median is technically $(a_{\left(\left\lfloor \frac{N}{2}\right\rfloor \right)}+a_{\left(\left\lceil \frac{N}{2}\right\rceil \right)})/2$. If you can live with using $a_{\left(\left\lfloor \frac{N}{2}\right\rfloor \right)}$ as the ``median'', the above should work. Otherwise, you need a second set of binary variables ($w_{1},\dots,w_{N}$) and a second continuous variable (replace $y$ with $y_{1}$ and $y_{2}$). You minimize $(y_{1}+y_{2})/2$ subject to the constraints \begin{align*} y_{1} & \ge a_{i}-M_{i}z_{i}\quad\forall i\\ y_{2} & \ge a_{i}-M_{i}w_{i}\quad\forall i\\ \sum_{i=1}^{N}z_{i} & =\frac{N}{2}-1\\ \sum_{i=1}^{N}w_{i} & =\frac{N}{2} \end{align*} where the $M_{i}$ are as above. The constraints force $y_{1}$ to be at least as large as $\frac{N}{2}+1$ of the $a_{i}$ and $y_{2}$ to be at least as large as $\frac{N}{2}$ of them. The minimum objective value will occur when $y_{1}=a_{\left(\frac{N}{2}+1\right)}$ and $y_{2}=a_{\left(\frac{N}{2}\right)}$.