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

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

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.

• Your $f_n(x) \ge c_n$ should instead be $f_n(x) \ge c_1$, right? Also, it seems like you can avoid $\epsilon$ by instead imposing $b_{k,i}=1 \implies f_i(x) \ge c_k$. Jul 3 at 15:45
• @RobPratt. Agree on both counts, which have now been incorporated. Thanks for your comment. Jul 3 at 16:04

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.