23
Sep

Integer Linear Programming | 0-1 Binary Constraints | Examples – Part 2


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.

Tags: , , , , , , , , , , , , , , , , , , , , , , ,

11 Comments

  • Mohammad Shariq says:

    hi Joshua ,
    Thanks a lot for tutorials , they are very good.
    i have similar problem as above but variables are non binary
    x , y are non negative int variables
    if x > 0 then y =0 ,
    how to formulate this constraint, could you please help

  • Xinyue Wu says:

    Thanks so much Joshua. Reaaaallly appreciate your help!

  • mohammed salim says:

    ู…ุดูƒูˆูˆูˆูˆูˆูˆูˆุฑ ุตุฏูŠู‚ูŠ ู…ุง ู‚ุตุฑุช
    ูƒููŠุช ูˆ ูˆููŠุช

  • ala kasem says:

    Hello Sir, thank you for the video. It is really very interesting. I have a question please concerning the last example. can x1 + x2 +x3 >= 3 be a solution for the example? thank you for answering.

  • Mohammed Al-Bashiri says:

    this is the best video ever. thank you for the amazing video

  • Daphne Foo says:

    Hello! I am came across your video and its really helpful but I just have this question regarding the last example, how did you get X1 + 1 >= X2 + X3?

  • The Seperator says:

    How do you process these conditional constraints into Excel. It doesn't seem to work for me!?

  • Koen Kooi says:

    This is awesome, thanks so much!

  • Giulio Proia says:

    Thanks so much for the videa. ๐Ÿ™‚ I have another question if i want x_1 is selected if and o ly if x_2 or x_3 is selected, what coinstraint have i use?

  • axel thedawg says:

    This was very helpful Joshua. it's been a while since I formulated an IP, ran across a problem at work and struggled a bit on how to manage binary constraints. this totally saved my a$$. Thanks and great work!

  • Tuแบฅn Phแบกm Anh says:

    Thanks so much Joshua! ๐Ÿ™‚

Leave a Reply

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