# How to set up a constraint that represents a median?

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?

• Do you have an odd number of $y$ variables? Commented Jan 7 at 0:46
• or.stackexchange.com/questions/8633/… Commented Jan 7 at 0:52
• Following up on @RobPratt's question, if $y$ has even dimension do you need $z$ to be the mean of the two middle $y$ values are just anything between the two middle values?
– prubin
Commented Jan 7 at 1:16
• @RobPratt I'd like to set it up such that the code works whether we have an odd or even number of variables, if possible. Commented Jan 7 at 20:32
• @prubin If there are an even number of variables, I'd need $z$ to be the mean of the two middle values. Commented Jan 7 at 20:33

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}

• Thank you, this looks great! My initial ideas to solve this were much more complicated. Commented Jan 7 at 21:10

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}$$

• I think you meant something else instead of $x_i=p_{i,j}x_i$, which would imply that $p_{i,j}=1$ or $x_i=0$. Also, we are not given that $y_i \ge 0$, so you should not impose $x_i \ge 0$. Commented Jan 7 at 17:51
• Also, you want $k=I/2$ in the even case. Commented Jan 7 at 17:57
• Nice links. ... Commented Jan 7 at 18:33