How to represent a constraint on the kth-smallest function?

Question

How can I represent the following set of constraints in a linear program, where $c_1,\ldots, c_n$ are constants and $f_1,\ldots,f_n$ are functions of the optimization variables?

The smallest of $f_1(x),\ldots,f_n(x)$ is at least $c_1$;

The second-smallest of $f_1(x),\ldots,f_n(x)$ is at least $c_2$;

The third-smallest of $f_1(x),\ldots,f_n(x)$ is at least $c_3$;

...

The largest of $f_1(x),\ldots,f_n(x)$ is at least $c_n$.

Answer 1

The first constraint is convex, and can be handled without use of logical constraints or introduction of binary variables: $$f_1(x) \ge c_1, ..., f_n(x) \ge c_1$$

The remaining constraints are non-convex, and so require logical constraints or binary variables to handle.

For simplicity of exposition, I will assume logical constraints are available. If not, they can be handled by standard big M modeling, such as in the "If $f(x)\le0$ then a" section of Logics and integer-programming representations, or as found on this site.

For each $k$ from $2$ to $n$, and for each $i$ from $1$ to $n$, let $b_{k,i}$ be a binary variable, and specify the logical constraints $$b_{k,i} = 1 \implies f_i(x) \ge c_k.$$ For each $k$ from $2$ to $n$, impose the constraint: $$\sum_{i=1}^n b_{k,i} \ge n-k+1$$

Edit: I corrected a typo and improved the formulation, both as pointed out in the comments by @RobPratt. By switching the direction (specifying the contrapositive) of the logic constraints, the need for an $\epsilon$ fudge factor was eliminated.

Answer 2

It is equivalent to say that there exists a permutation of $c_i$, say $c_{(i)}$, that satisfies $$ f_i(x) \geq c_{(i)},\quad \forall i=1,\dots, n $$

The permutation $c_{(i)}$ could be expressed with a permutation matrix $$ f_i(x) \geq \sum_{j} b_{ij}c_{j},\quad\forall i\\ \sum_{i} b_{ij} = 1,\quad\forall j\\ \sum_{j} b_{ij} = 1,\quad\forall i\\ b_{ij} \in \{0, 1\},\quad\forall i, j $$

Edit: After testing, my formulation is correct but it is significantly slower than the model in the previous answer.