Question

    For questions 2 – 8:  

There are three projects.  Binary variablesX₁, X₂, and X₃are defined as follows:

X_i=     1 if project i is selected, and

X_i=     0 if project i is not selected,           for i = 1, 2, 3.

2. Write a constraint to represent: “At least one of the three projects must be selected”.

3. Write a constraint to represent: “Between project 1 and project 2, exactly one is selected”.

4. Write a constraint to represent: “At most two projects of the three can be selected”.

5. Write a constraint to represent: “Project 2 and project 3 must go together.  That is, it is not allowed to select one while deselect the other”.

6. Write a constraint to represent: “The three projects can not be all selected.  There must be at least one that is not selected”.

7. Write a constraint to represent: “If project 2 is selected, then project 1 must be selected; but if project 2 is not selected, then there is no restriction on project 1”.

8. (Bonus question) Write a constraint to represent: “If project 1 is not selected, then project 2 must not be selected; but if project 1 is selected, then there is no restriction on project 2”.

Answer 1

2. If at least one project must be selected then it implies that at least one of X1, X2 or X3 will have a value of 1.

X1+X2+X3 >= 1

3. If X1 = 1 then X2 =0 and if X2=1 then X1=0. Thus their sum is always 1.

X1 + X2 = 1

4. The compliment of selection of at most two of three projects is the selection of all three projects, in which all three will have a value of 1 and thus add up to 3. Hence, if we don't want all three to be selected, we can put a constraint that the sum of all three must be less than 3.

X1 + X2 + X3 < 3

5. We need to make sure that both X2 and X3 have the same value, i.e. either both 0 or both 1.

A constraint which satisfies the criteria is:

X2*(1-X3) + X3*(1-X2) = 0

Let's verify the above constraint. There are 4 cases:

I. Both X2 and X3 are zero. In this case, the above expression is clearly zero.

II. Both are one. In this case also, the above expression is zero.

III. X2 is 1 while X3 is 0.  The expression gives 1 in this case and thus violates our constraint.

IV. X2 is 0 while X3 is 1.  The expression gives 1 in this case and thus violates our constraint.