Aggregated vs. Disaggregated Constraints

In an integer program, a logical link of the form 'if y=0 then every x_i=0' can be written either as a single aggregated big-M constraint or as one disaggregated constraint per variable. The two formulations are equivalent as integer programs but the disaggregated form yields a strictly tighter LP relaxation. This lesson defines both forms, shows why disaggregation cuts off fractional points, and compares the LP-relaxation optimal values produced by each.

Step 1 of 157%

Tutorial

Two Ways to Write a Linking Constraint

Many integer programs need to enforce the implication

"if $y=0$ , then $x_1 = x_2 = \cdots = x_n = 0$ ,"

where $y \in \{0,1\}$ is an on/off switch and each continuous variable $x_i$ has upper bound $u_i$ . There are two standard ways to model this.

The aggregated form bundles all $n$ variables into a single big- $M$ constraint:

x_1 + x_2 + \cdots + x_n \;\leq\; M\, y,

where $M$ is an upper bound on $\sum_i x_i$ . The smallest valid choice is $M = u_1 + u_2 + \cdots + u_n$ .

The disaggregated form writes one linking constraint per variable:

x_i \;\leq\; u_i\, y \qquad \text{for } i = 1, 2, \ldots, n.

When $y \in \{0,1\}$ , both forms enforce the same logic: $y=0$ kills every $x_i$ , and $y=1$ allows each $x_i$ to range up to $u_i$ . The two formulations therefore describe the same integer program.

Example. For $x_1, x_2, x_3 \in [0,4]$ and $y \in \{0,1\}$ :

Aggregated: $x_1 + x_2 + x_3 \leq 12\, y.$
Disaggregated: $x_1 \leq 4y,\;\; x_2 \leq 4y,\;\; x_3 \leq 4y.$

Both express the same on/off behavior under integrality of $y$ .