How to set up a constraint that represents a median?

Question

I'm trying to create an optimization problem where one of my constraints represents a median of another decision variable. Suppose I have decision variables $\bf{y}$ and $z$. My problem will look something like:

\begin{align}\min &\quad f(z)\\\ \text{s.t.} &\quad\text{constraint that defines z to be the median value of y}\\\ &\quad [\text{other constraints with y}]\end{align}

I'm not sure how to express this constraint. Any ideas?

Answer 1

Suppose you have an odd number of variables $y_1,\dots,y_{2k+1}$. Introduce binary variables $u_i$ and $v_i$ to indicate whether $z \ge y_i$ or $z \le y_i$, respectively. Now impose constraints \begin{align} \sum_i u_i &= k+1 \tag1\label1 \\ \sum_i v_i &= k+1 \tag2\label2 \\ u_i = 1 &\implies z \ge y_i &&\text{for all $i$} \tag3\label3 \\ v_i = 1 &\implies z \le y_i &&\text{for all $i$} \tag4\label4 \end{align} You can linearize the indicator constraints \eqref{3} and \eqref{4} via big-M constraints: \begin{align} y_i - z &\le M(1-u_i) &&\text{for all $i$} \tag{3'}\label{3'} \\ z - y_i &\le M(1-v_i) &&\text{for all $i$} \tag{4'}\label{4'} \end{align}

Answer 2

First you may need to sort your optimization variables. Taking idea from Dr. Kalvelagen (link) & YALMIP define additional continuous variable $0 z$, $x$ of same domain s $y$ & $i \times i$ matrix of binary variables $p$

Basically
$x_i = p_{i,j}x_i$

$\sum_i z_{i,j} = y_j \quad \forall j$
$\sum_j z_{i,j} = x_i \quad \forall i$
$\sum_i p_{i,j} = 1$
$\sum_j p_{i,j} = 1$
$x_i \le x_{i+1}$
$z_{i,j} \le Mp_{i,j}$

Median = $x_{I+1\over2}$ if $I$ or $J$ is odd, else ${x_{k}+x_{k+1}}\over 2$ where $k={{I}\over2}$