Consider the four binary variables  and the constraints

and

The two feasible sets of Eqs. (15.22) and (15.23) may look different but they are, in fact, the same. If we interpret the variables as the decision to start an activity, we are expressing the fact that we may start activity 0 only if all activities 1, 2, and 3 are started. If even one of the preconditions is not met, and the corresponding variable is set to 0, then the variable x0 must be set to 0 as well.Since the two formulations are equivalent, common sense would suggest that having to do with one constraint is better than dealing with three of them. This intuition is wrong, and many MILP packages automatically transform the aggregate constraint (15.22) into the three disaggregated constraints (15.23). To see why, observe that the aggregated constraint is just the sum of the three constraints. Generally, when we add inequality constraints, we relax the feasible set.
For instance, a point x satisfying the individual inequalities

will certainly satisfy the aggregate inequality

but the converse is not true (the sum of negative numbers is negative, but we may get a negative number by summing a small positive one and a large negative one).
In the present case, the integrality restriction has the effect that we do not really relax the constraints by aggregating them, in terms of integer feasible points; however, this will happen in the continuous LP relaxation. The result is that the integrality gap will increase.

Data From Equation  (15.22)

Data From Equation (15.23)

Transcribed Image Text:

20, 1, 2, 3 {0, 1}