# Rank-dependent constraints in linear programming

I have a typical linear optimization problem:

$c'x \to \max_x$

s.t. $~~l \leq Ax \leq u,$

where $x = (x_1, ...,x_n)'$, $A - k \times n$ matrix of constraints coefficient, $l$ and $u$ are $k \times 1$ vectors of lower and upper bounds, respectively.

I need to add specific constraints on $i$-th largest element in vector $x$:

$x_{(i)} \leq b_i, ~~ i = 1...n$,

where $x_{(1)} \geq x_{(2)} \geq ... \geq x_{(n)}$.

In other words, each variable's individual bound depends on its rank. Is there a way to reformulate it as an LP constraint?

By setting the first $n-1$ values of $b$ to $\infty$, you would effectively have a method to implement $\min x \leq b_n$, which isn't LP-representable as $\min$ is concave. Hence, not possible.
Constraining the sum of the $k$ largest elements is LP-representable though (and your constraint is mixed-integer LP-representable).
• The naive way would be to use the fact that a sorted vector $s$ can be generated by writing $s = Bx$ where $B$ is a binary matrix with every row and column summing to $1$, and the constraints $s_i \geq s_{i-1}$. All left now is to implement binary times continuous ($Bx$) and that is done using standard big-M methods. You can probably write more efficient combinatoric models. If you use YALMIP (modelling layer for optimization in MATLAB developed by me) you would simply use the overloaded sort operator, and there are probably similar constructs in other modelling languages. – Johan Löfberg Aug 10 '18 at 20:29