# Computing overlap of intervals in an integer programming framework

Suppose I have 2 intervals C1 = [x1, x2] and C2 = [y1, y2], where x1,x2,y1,y2 are variables in an Integer program, I want to compute the overlap of C1 and C2. I am interested in a tight formulation for computing the overlap as an another variable with as few big M constraints as possible. Any references or formulations are deeply appreciated.

• Do you know that $x1 \le y1$? Or could these intervals be completely arbitrary? Do you know upper and lower bounds for x1,x2,y1,y2? – D.W. Dec 11 '17 at 4:41
• @D.W. -:Nope, we do not know whether x1<= y1. These are variables whose values need to be determined by the integer programming solver. – csTheoryBeginner Dec 11 '17 at 15:00

First you need to know whether $x_1\le y_1$ which is just a comparison.
Next, you create new variables $l_1, l_2, r_1, r_2$ for which you know that $l_1\le r_1, l_2 \ge l_1, r_2 \ge r_1$
Now the answer is $\min(\max(l_2 - r_1, 0), r_2 - r_1))$