How do constraints become redundant in a Big-M conjunction?

Question

The following Big-M conjunction appears on page 14:3 of The Path&Cycle Formulation for the Hotspot Problem in Air Traffic Management: \begin{align*} \text{(i)} \quad t_{(g, \; s)} - t_{(f, \; s+1)} &\geq -M(1 - y^s_{fg}) \nonumber \\ \text{(ii)} \quad t_{(f, \; s)} - t_{(g, \; s+1)} &\geq -M(1 - y^s_{gf}) \nonumber \\ \text{(iii)} \quad t_{(g, \; s+1)} - t_{(f, \; s)} &\geq -M(1 - x^s_{fg}) \label{eq:5}\\ \text{(iv)} \quad t_{(f, \; s+1)} - t_{(g, \; s)} &\geq -M(1 - x^s_{fg})\nonumber \\ \text{where} \quad y^s_{fg}, \; y^s_{gf}, \; x^s_{fg} &\in \{0, \; 1\} \nonumber \end{align*}

Here $f$ and $g$ are a pair of flights that will visit sector $s$ at some point.

• If flight $f$ enters $s$ before $g$, binary quantity $y^s_{fg}=1$
• If flight $g$ enters $s$ before $f$, binary quantity $y^s_{gf}=1$
• If flight $f$ shares $s$ with $g$, binary quantity $x^s_{fg}=1$
• In a valid flight schedule, only one of these binary quantities can be 1.

The entry time of flight $f$ into sector $s$ is given by $t_{(f, \; s)}$. The entry time for the flight's next sector is written as $t_{(f, \; s + 1)}$.

If $y^s_{fg}=1$, then $t_{(g, \; s)} - t_{(f, \; s+1)} \geq 0$. With a sufficiently large $M$, wouldn't the inequality hold for (ii), (iii), and (iv) as well, however? Is this what is meant with redundant constraints (p. 14:4)? What do these constraints then accomplish?

Answer 1

If $y^s_{fg}=1$, then $y^s_{gf}=0=x^s_{fg}$. So the right-hand sides of (ii), (iii) and (iv) become $-M$ (think $-\infty$ here), which means any values of the left-hand side variables will satisfy them. So, in this case, constraints (ii)-(iv) have no influence on the solution. If, say, $y^s_{gf}=1$ and $y^s_{fg}=0=x^s_{fg}$, then (ii) becomes relevant and (i), (iii) and (iv) have no influence on the solution. This is what the authors mean by "redundant". Note that none of the constraints is redundant overall; they are just redundant in certain portions of the solution space.