Something along the following lines cropped up recently, regarding a discrete optimization model. Suppose that we have a collection of binary variables
xi∈B,i∈1,…,N in an optimization model, where
B={0,1}. The values of the
xi 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
xi=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 (yi∈B,i∈1,…,N) where
yi=1⟺i=argmin{j:xj=1}.
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=∑ni=1iyi solves the first case.
To handle the second case, we can add the following constraints:
yi≤xi∀iyi≥xi−∑j<ixj∀iiyi≤i−∑j<ixj∀i>1Left 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 yi+xj≤1 for j<i. To see that this version is stronger, aggregate these and yi≤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 iyi 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. yi≥xi?
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 x3=1 and x1=x2=0, the unique feasible choice of values for y will be y1=y2=0,y3=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 (x2=1 or x3=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 xi=1 for more than one value of i, the smallest i with xi=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".