*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\}. \]

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

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.

ReplyDeleteRob Pratt

Rob,

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

Dear Paul,

ReplyDeletethank 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

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

DeleteDear Paul,

ReplyDeleteThank 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?

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

DeleteIn 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$.

Thank you, Dr. Paul,

DeleteThen 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

The constraints I introduce in my post

Deletedo 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.Dear Paul,

DeleteSee, 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

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

Deletesinglesolution with $x_i=1$ formore than onevalue 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".