Minimizing the median, integer programming 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? 
 A: 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.
A: 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)}$.
