1
$\begingroup$

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.

$\endgroup$
  • $\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. Dec 11 '17 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$ – csTheoryBeginner Dec 11 '17 at 15:00
3
$\begingroup$

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/

$\endgroup$
  • $\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$ – csTheoryBeginner Dec 11 '17 at 15:27
  • $\begingroup$ I understand. Formulations on the blog are generic enough to be applied "mechanically" without optimizations for specific case. $\endgroup$ – user1543037 Dec 11 '17 at 17:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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