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.

  • $\begingroup$ 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? $\endgroup$
    – D.W.
    Commented Dec 11, 2017 at 4:41
  • $\begingroup$ @D.W. -:Nope, we do not know whether x1<= y1. These are variables whose values need to be determined by the integer programming solver. $\endgroup$ Commented Dec 11, 2017 at 15:00

1 Answer 1


By overlap I understand its length (no its coordinates) since you didn't specify how to handle no overlap case.

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))$

How you build these constraints it is up to you. You can use approaches similar to https://blog.adamfurmanek.pl/2015/09/12/ilp-part-4/ and https://blog.adamfurmanek.pl/2015/09/19/ilp-part-5/

  • $\begingroup$ -: Thanks, it was an interesting read. You are right that it is the length of overlap I was interested in. Unfortunately however, to use the conditions you mentioned via the formulation in the webpage seem to be using far more disjunctions than in the formulation I currently have. My representation requires 6 M constraints with M (analogous to K in the web page), and 7 {0,1} variables. I suspect there could be a better formulation. I will however, upvote your answer. $\endgroup$ Commented Dec 11, 2017 at 15:27
  • $\begingroup$ I understand. Formulations on the blog are generic enough to be applied "mechanically" without optimizations for specific case. $\endgroup$ Commented Dec 11, 2017 at 17:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.