Wednesday, June 21, 2017

Minimizing the k-th largest x

Minimizing the largest \(x_i\) is an easy exercise in LP modeling:
\[\bbox[lightcyan,10px,border:3px solid darkblue] { \begin{align} \min\>& z\\ & z \ge x_i \end{align}} \]
This is sometimes called MINIMAX.

What about minimizing the \(k^{\text{th}}\) largest value? Here is one possible MIP formulation:

\[\bbox[lightcyan,10px,border:3px solid darkblue] { \begin{align} \min\>& z\\ & z \ge x_i - \delta_i M\\ & \sum_i \delta_i = k-1\\ & \delta_i \in \{0,1\} \end{align}} \]

I.e., we have \(k-1\) exceptions on the constraint \(z \ge x_i\). The objective will make sure the exceptions are the largest \(x_i\).  We should think long and hard about making the big-M’s as small as possible. If you have no clue about proper bounds on \(x_i\) one could use indicator constraints.

Interestingly, minimizing the sum of the \(k\) largest can be modeled as a pure LP (1) :

\[\bbox[lightcyan,10px,border:3px solid darkblue] { \begin{align} \min\>& \sum_i v_i + k\cdot q\\ & v_i \ge x_i - q\\ &v_i \ge 0 \\ &q \text{ free } \end{align}} \]

You almost would think there is an LP formulation for minimizing the \(k^{\text{th}}\) largest value. I don't see it however.
  1. Comment by Michael Grant in


  1. What is the 'M' in your formulation for the k largest? (Sorry if this is obvious!)

    1. Big-M constraints are an important concept in integer programming. Basically M is a large enough constant to make a constraint non-binding. Any book on LP/MIP will discuss this in length.