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:

- we want to store that minimal index in an integer variable (which I will call $z$); or
- 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).

#### Paul Rubin

#### Latest posts by Paul Rubin (see all)

- Greedy Methods Can Be Exact - January 8, 2020
- 1-D Cutting Stock with Overlap - January 7, 2020
- A Value-ordered Java Map - October 18, 2019