Logical binary constraints – Part 2 Suppose a company has 5 projects available
to choose from. We define decision variables as follows:
xi=1 if project i is selected, and 0 if not selected. Now consider this requirement. If project 1 is selected, then projects 2
and 3 must also be selected. Think of it as a child invited to a party,
where both parents must be attending. So the mom or dad may attend without the child,
but if the child is going to attend, both parents must be in attendance. So X1 depends on X2, and also on X3. We can combine them to give
2X1≤ X2+X3 or 2×1 – X2 – X3 ≤ 0 That is,
We can decide to have none of them. We can have only project 2, or only project
3. Or both projects 2 and 3 without project 1. And we can have project 1 as long as we have
2 and 3. We can’t have project 1 with only project
2. We can’t have it with only project 3 either. And we can’t have it by itself. Next. If project 1 is selected, then 2 or 3 (or
both) must also be selected. So we can think of this again as the case
where the child can attend the party if at least one of the parents also attends. So x1 depends on x2, or on x3
and we write X1≤ X2+X3 or X1-X2-X3≤ 0 So we can decide to choose none. We can have only project 2, or only project
3. Or both projects 2 and 3 without project 1. And we can have project 1 as long as we have
2 and 3. We can have project 1 with only project 2,
or with only project 3. We just can’t have project 1 by itself.  Next Project 1 cannot be selected if both 2 and
3 are selected. In order words, project 1 is mutually exclusive
with 2 and 3 together. This means that if X2 + X3=2, then X1 has
to equal 0. In other words,
X1 + (X2 + X3) has to be less than or equal to 2. We could select none. We could select only one of the 3 projects
individually. We could select projects 2 and 3 only. Or project 1 with only 2, or with only 3. But we can’t select project 1 if both 2
and 3 also are selected.  Next
If projects 2 and 3 are selected, then project 1 must also be selected. So if X2 + X3=2, then X1=1
But because projects 2 and 3 together are dependent on project 1, then
X1 + 1 ≥ X2 + X3 or X2 + X3 ≤ X1 + 1
or – X1 + X2 + X3 ≤ 1. So we can select none of the 3. Or select only one. Or project 1 with only 2, or with only 3. We can also have all 3. However, we cannot have 2 and 3 without 1. And that concludes this video. Thanks for watching.


Leave a Reply

Your email address will not be published. Required fields are marked *