Selecting the Least Qualifying Index

Written by: Paul Rubin

Primary Source: OR in an OB World


Something along the following lines cropped up recently, regarding a discrete optimization model. Suppose that we have a collection of binary variables $x_i \in B, \, i \in 1,\dots,N$ in an optimization model, where $B=\{0, 1\}$. The values of the $x_i$ will of course be dictated by the combination of the constraints and objective function. Now suppose further that we want to identify the smallest index $i$ for which $x_i = 1$ for use within the model (hence before solving the model). I’ll consider two possibilities:

  1. we want to store that minimal index in an integer variable (which I will call $z$); or
  2. we want to create an alternative set of binary variables ($y_i \in B, \, i \in 1,\dots,N$) where
    \[
    y_{i}=1\iff i=\text{argmin}\left\{ j:x_{j}=1\right\}.
    \]

I’ll focus on the second case, which is a stepping stone to the first case. Once we have $y$ defined as in the second case, $z = \sum_{i=1}^n i y_i$ solves the first case.

To handle the second case, we can add the following constraints: \begin{alignat*}{2}
y_{i} & \le x_{i} & \; & \forall i\\
y_{i} & \ge x_{i}-\sum_{j<i}x_{j} &  & \forall i\\
iy_{i} & \le i-\sum_{j<i}x_{j} &  & \forall i>1
\end{alignat*}Left to the reader as an exercise: to confirm that this works (or, if you find an error, to kindly post it in a comment).

The following two tabs change content below.
I'm an apostate mathematician, retired from a business school after 33 years of teaching mostly (but not exclusively) quantitative methods courses. My academic interests lie in operations research. I also study Tae Kwon Do a bit on the side.

Latest posts by Paul Rubin (see all)