Thursday, June 25, 2015

Selecting the Least Qualifying Index

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

10 comments:

  1. I confirm that the above formulation does the job. But an "automatic" derivation via conjunctive normal form yields something stronger. In particular, your third set of constraints become instead $y_i + x_j \le 1$ for $j < i$. To see that this version is stronger, aggregate these and $y_i \le 1$ to obtain yours.

    Rob Pratt

    ReplyDelete
    Replies
    1. Rob,

      Thanks for pointing out the alternative, which I agree is stronger (and which I meant to mention, but forgot). The reason I opted for the version I posted is that the stronger version introduces a quadratic number of constraints (and approximately twice as many nonzero coefficients).

      Besides being stronger, the second version constraints may be a bit less susceptible to numerical stability issues when $N$ is large (due to the $i y_i$ term in my version). My thinking when I posted was that if $N$ is big enough to cause numerical issues as a coefficient, the modeler will already be drowning in binary variables. :-)

      Delete
  2. Dear Paul,

    thank you for all your interesting blog posts!

    Could it be that the second constraint should also hold for $i=1$, i.e. $y_i \geq x_i$?

    Udo

    ReplyDelete
    Replies
    1. Udo: OOPS! Yes. Thanks for catching that. I'll fix it now.

      Delete
  3. Dear Paul,

    Thank you for this interesting blog. I construct a counterexample:

    y1 <= x1;
    y2 <= x2;
    y3 <= x3;

    y1 >= x1;
    y2 >= x2 - x1;
    y3 >= x3 - x2 - x1;

    2 * y2 <= 2 - x1;
    3 * y3 <= 3 - x2 - x1;

    x1 + x2 + x3 = 1;
    where x1, x2, x3, y1, y2 and y3 are binary variables.

    We want to limit x1 = 1; But, x3 = 1 also seems to hold for all inequalties?

    ReplyDelete
    Replies
    1. The intent is not to limit the x variables; their values are dictated by the rest of the model. The intent is to have exactly one of the y variables be 1, and have it correspond to the x variable with least index that took value 1 (if any -- if all x are 0, all y should be 0).

      In your example, if $x_3 = 1$ and $x_1 = x_2 = 0$, the unique feasible choice of values for $y$ will be $y_1 = y_2 = 0, \, y_3 = 1$.

      Delete
    2. Thank you, Dr. Paul,

      Then if the rest of the model is:
      1 - x1 + x2 + x3 = 2;

      as well as: x1 + x2 + x3 = 1;

      To satisfy these two constraints, we have two possible solutions:
      x1 = 0, x2 = 1, x3 = 0
      or
      x1 = 0, x2 = 0, x3 = 1

      In other words, either x2 = 1 or x3 = 1.

      Including the other constraints you introduce, we should have x2 = 1, Right?

      But, when I input all these constraints to Lingo (without objective), the solution is x3 = 1? Is anything wrong or I ignore?

      Thanks.
      Yuan

      Delete
    3. The constraints I introduce in my post do not limit $x$ in any way. Without knowing your objective function, I can cannot tell you which solution ($x_2 = 1$ or $x_3 = 1$ you should get. Possibly both are optimal. What I can say is that the extra constraints (and $y$ variables) do not influence which solution you get.

      Delete
    4. Dear Paul,

      See, for an example, the whole model is:
      max = 2 * x1 + x2 + x3
      s.t.
      1 - x1 + x2 + x3 = 2;
      x1 + x2 + x3 = 1;

      where x1, x2 and x3 are binary variables.

      Yes, both x2 = 1 and x3 = 1 are optimal. Actually, the objective function has a determined value: 1, but I think it will not affect this discussion.

      Since there are multiple optimal solutions, including your constraints, we should have y2 = 1? So that x2 is chosen to be 1. However, both (y1 = 0, y2 = 1, y3 =0) and (y1 = 0, y2 = 0, y3 = 1) satisfy these extra constraints.

      How can we gurantee that the variable that has the least index is chosen, among the multiple optimal solutions?

      If these constraints and the y variables will not influence which solution I will get, then what is the purpose to introduce them? How can it change the model or the solution?
      I am a little confused. I really appreciate that.

      Thanks,
      Yuan

      Delete
    5. With the constraint that the x variables sum to 1, there is no purpose to introduce the y variables. What you want to do is totally unrelated to the topic discussed here. The y variables (and constraints) are designed to identify, in a single solution with $x_i=1$ for more than one value of $i$, the smallest $i$ with $x_i=1$.

      In your case, only one of the x variables can be 1, which automatically makes it the one with smallest index. What you want is to solve a multiobjective model that prioritizes, among alternative solutions, the one where the index is smallest. I suggest you do a web search for "multiobjective optimization".

      Delete

Due to intermittent spamming, comments are being moderated. If this is your first time commenting on the blog, please read the Ground Rules for Comments. In particular, if you want to ask an operations research-related question not relevant to this post, consider asking it on Operations Research Stack Exchange.