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$
$\endgroup$
2
-
$\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$– csTheoryBeginnerCommented Dec 11, 2017 at 15:00
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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