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,…,Nxi∈B,i∈1,…,N in an optimization model, where
B={0,1}B={0,1}. The values of the
xixi 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
ii for which
xi=1xi=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 zz); or
- we want to create an alternative set of binary variables (yi∈B,i∈1,…,Nyi∈B,i∈1,…,N) where
yi=1⟺i=argmin{j:xj=1}.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
yy defined as in the second case,
z=∑ni=1iyiz=∑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>1yi≤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≤1yi+xj≤1 for j<ij<i. To see that this version is stronger, aggregate these and yi≤1yi≤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 NN is large (due to the iyiiyi term in my version). My thinking when I posted was that if NN 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=1i=1, i.e. yi≥xiyi≥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=1x3=1 and x1=x2=0x1=x2=0, the unique feasible choice of values for yy will be y1=y2=0,y3=1y1=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 xx in any way. Without knowing your objective function, I can cannot tell you which solution (x2=1x2=1 or x3=1x3=1 you should get. Possibly both are optimal. What I can say is that the extra constraints (and yy 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=1xi=1 for more than one value of ii, the smallest ii with xi=1xi=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".