0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you for the answer, Johan. Could you elaborate on how to implement such constraint in mixed-integer programming, or provide a link to a relevant example? $\endgroup$ – user10203644 Aug 10 '18 at 14:41
  • $\begingroup$ 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. $\endgroup$ – Johan Löfberg Aug 10 '18 at 20:29

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.