In the Constraint Aggregation method we replace several constraints by a single one

Constraint Aggregation Example

assume 0-1 problem

first convert the inequality constraints into equations, by introducing slack variables x_n+1and x_n+2

where:

• a_1n+1 = 1
• a_1n+2 = 0
• a_2n+1 = 0
• a_2n+2 = 1

and:

• x_n+1is an integer value between 0 and b₁
• x_n+2is an integer value between 0 and b₂

it is clear that the 2 linear constraints:

• (1) Σ_i=1ⁿ⁺² [a_1ix_i] = b₁
• (2) Σ_i=1ⁿ⁺² [a_2ix_i] = b₂

imply the new one:

• (3) Σ_i=1ⁿ⁺² [(a_1i+ ma_2i)x_i] = b₁ + mb₂

the question is how can we choose m such that the implication also holds in the opposite direction, that is, such that the aggregated constraint (3) implies (1) and (2)

aggregate constraint (3) implies:

• (4) Σ_i=1ⁿ⁺² [a_1ix_i] - b₁+ m { Σ_i=1ⁿ⁺² [a_2ix_i] - b₂ } = 0

now observe that the value of Y:

• Y = Σ_i=1ⁿ⁺² [a_1ix_i] - b₁

the following cases must hold about Y:

• Y ≥ -b₁
  • this is because both:
    • Σ_i=1ⁿ⁺² [a_1i] (i.e. summation of coefficients) may equal 0
    • b₁ may be its maximum integer value b₁
• Y ≤ Σ_i=1ⁿ⁺² [a_1i]
  • this is because both:
    • Σ_i=1ⁿ⁺² [a_1i] may be some non-negative value
    • b₁ may be its minimum integer value 0

so we have a bound on Y:

• |Y| ≤ b₁’ = max(b₁, Σ_i=1ⁿ⁺² [a_1i])

now observe value Z:

• Z = Σ_i=1ⁿ⁺² [a_2ix_i] - b₂

then using Y, Z, and equation (4) we get:

• (5) Y + mZ = 0

how can this equality (5) hold?

possible cases:

• if Y = Z = 0
  • obviously (1) and (2) are satisfied
• if Z ≠ 0
  • then |Z| ≥ 1, being an integer
  • then Y must make the left hand side 0 in (5)
  • if, however, we choose m = b₁’ + 1,

thus, with the choice of m = b₁’ + 1, we can achieve that whenever the aggregated constraint (3) is satisfiable, both original constraints (1) and (2) will also be satisfiable. Of course, this is only guaranteed when the variables take their values from the allowed ranges

remark: we can assume that b₁ ≤ Σ_i=1ⁿ [a_1i] since otherwise the original constraint Σ_i=1ⁿ [a_1ix_i] ≤ b₁ would always be satisfied, so we could simply leave it out. With this assumption the choice for the constant m becomes

• m = 1 + Σ_i=1ⁿ [a_1i]