6
$\begingroup$

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

$\endgroup$

2 Answers 2

8
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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$. $\endgroup$
    – RobPratt
    Jul 3 at 15:45
  • 1
    $\begingroup$ @RobPratt. Agree on both counts, which have now been incorporated. Thanks for your comment. $\endgroup$ Jul 3 at 16:04
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.