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).
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 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.
DeleteDear 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 single solution with $x_i=1$ for more than one value of $i$, the smallest $i$ with $x_i=1$.
DeleteIn 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".