Skip to main content
Operations Research

Return to Answer

Reworked the answer to handle unbounded regions.
Source Link
prubin ♦
prubin ♦
  • 40.9k
  • 3
  • 40
  • 109

This can be solved with an integer linear program (although I'm not sure that's the best approach). Let $D$ be the smallest rectangle containing all your individual domains. We'll set up a MIP model to cover the gaps in $D.$ Once you have that answer, you can add four unbounded rectangles (all points above $D$, all points below $D$, all points left of $D$ but not above or below, and all points right of $D$ but not above or below) and have a full answer.

To cover $D,$ weWe first create a grid by running horizontal and vertical lines through all corners of your various domains. We don't need the grid to be evenly spaced. We also need to enclose the overall region in a box (hyperrectangle) big enough that all the vertices of the function domains are in the interior of the box. (We will relax the box later.) We need grid lines along the edges of the box.

I'll refer to any rectanglehyperrectangle bounded by consecutive grid lines both vertically and horizontallyin all directions as a "cell". We record the center points of each cell for future use, discarding any that are inside function domains.

Next, for every pair ofwe form all possible hyperrectangles whose vertices are grid points not on the same horizontal or vertical line we create a rectangle where one point is the lower left corner and the other is the upper right corner. Discard any rectanglehyperrectangle that overlaps one of the function domains. This is easy to determine: either the left edge. If, in any dimension, both limits of the rectangle is to the right ofhyperrectangle are on the right edgesame side of the domain (or vice versa),both less than or the top edge ofequal to the rectangle is belowlower range limit for that variable, or both greater than or equal to the bottom edge ofupper range limit), the domain (or vice versa)and the hyperrectangle do not overlap. Otherwise, or they overlapdo. 

Enumerate the surviving rectangleshyperrectangles as $R_1,\dots,R_N.$ Compute the set $S$ of pairs $(i,j),\, i<j$ for which $R_i$ and $R_j$ overlap (using the same logic by which we decided if rectangleshyperrectangles and domains overlapped).

Finally, for each center point $c_i,$ compute the set $C_i = \lbrace j\in 1,\dots,N : c_i\in R_j\rbrace$ of rectangleshyperrectangles containing that point.

Now define binary variables $x_i,\,i=1,\dots,N$ which will indicate whether or not rectanglehyperrectangle $R_i$ is part of our cover. The objective is to minimize $\sum_i x_i,$ the number of rectangles used. To avoid rectangleshyperrectangles intersecting, for each $(i,j)\in S$ we add the constraint $x_i + x_j \le 1,$ preventing us from using both. Finally, to ensure that everything outside the function domains is covered, for each center point $c_i$ we add the constraint $\sum_{j\in C_i} x_j = 1,$ requiring that the center point belong to exactly one selected rectanglehyperrectangle. Since the rectanglehyperrectangle boundaries are grid lines, if the center point of a cell is in a rectanglehyperrectangle, the entire cell is in the rectanglehyperrectangle.

Once we have a solution, we replace the lower (upper) limit of any variable in any selected hyperrectangle with $-\infty$ ($+\infty$) if the edge of the hyperrectangle is on one of the boundaries of the box we imposed at the start.

This can be solved with an integer linear program (although I'm not sure that's the best approach). Let $D$ be the smallest rectangle containing all your individual domains. We'll set up a MIP model to cover the gaps in $D.$ Once you have that answer, you can add four unbounded rectangles (all points above $D$, all points below $D$, all points left of $D$ but not above or below, and all points right of $D$ but not above or below) and have a full answer.

To cover $D,$ we first create a grid by running horizontal and vertical lines through all corners of your various domains. We don't need the grid to be evenly spaced. I'll refer to any rectangle bounded by consecutive grid lines both vertically and horizontally as a "cell". We record the center points of each cell for future use, discarding any that are inside function domains.

Next, for every pair of grid points not on the same horizontal or vertical line we create a rectangle where one point is the lower left corner and the other is the upper right corner. Discard any rectangle that overlaps one of the function domains. This is easy to determine: either the left edge of the rectangle is to the right of the right edge of the domain (or vice versa), or the top edge of the rectangle is below the bottom edge of the domain (or vice versa), or they overlap. Enumerate the surviving rectangles as $R_1,\dots,R_N.$ Compute the set $S$ of pairs $(i,j),\, i<j$ for which $R_i$ and $R_j$ overlap (using the same logic by which we decided if rectangles and domains overlapped).

Finally, for each center point $c_i,$ compute the set $C_i = \lbrace j\in 1,\dots,N : c_i\in R_j\rbrace$ of rectangles containing that point.

Now define binary variables $x_i,\,i=1,\dots,N$ which will indicate whether or not rectangle $R_i$ is part of our cover. The objective is to minimize $\sum_i x_i,$ the number of rectangles used. To avoid rectangles intersecting, for each $(i,j)\in S$ we add the constraint $x_i + x_j \le 1,$ preventing us from using both. Finally, to ensure that everything outside the function domains is covered, for each center point $c_i$ we add the constraint $\sum_{j\in C_i} x_j = 1,$ requiring that the center point belong to exactly one selected rectangle. Since the rectangle boundaries are grid lines, if the center point of a cell is in a rectangle, the entire cell is in the rectangle.

This can be solved with an integer linear program (although I'm not sure that's the best approach). We first create a grid by running horizontal and vertical lines through all corners of your various domains. We don't need the grid to be evenly spaced. We also need to enclose the overall region in a box (hyperrectangle) big enough that all the vertices of the function domains are in the interior of the box. (We will relax the box later.) We need grid lines along the edges of the box.

I'll refer to any hyperrectangle bounded by consecutive grid lines in all directions as a "cell". We record the center points of each cell for future use, discarding any that are inside function domains.

Next, we form all possible hyperrectangles whose vertices are grid points. Discard any hyperrectangle that overlaps one of the function domains. This is easy to determine. If, in any dimension, both limits of the hyperrectangle are on the same side of the domain (both less than or equal to the lower range limit for that variable, or both greater than or equal to the upper range limit), the domain and the hyperrectangle do not overlap. Otherwise, they do. 

Enumerate the surviving hyperrectangles as $R_1,\dots,R_N.$ Compute the set $S$ of pairs $(i,j),\, i<j$ for which $R_i$ and $R_j$ overlap (using the same logic by which we decided if hyperrectangles and domains overlapped).

Finally, for each center point $c_i,$ compute the set $C_i = \lbrace j\in 1,\dots,N : c_i\in R_j\rbrace$ of hyperrectangles containing that point.

Now define binary variables $x_i,\,i=1,\dots,N$ which will indicate whether or not hyperrectangle $R_i$ is part of our cover. The objective is to minimize $\sum_i x_i,$ the number of rectangles used. To avoid hyperrectangles intersecting, for each $(i,j)\in S$ we add the constraint $x_i + x_j \le 1,$ preventing us from using both. Finally, to ensure that everything outside the function domains is covered, for each center point $c_i$ we add the constraint $\sum_{j\in C_i} x_j = 1,$ requiring that the center point belong to exactly one selected hyperrectangle. Since the hyperrectangle boundaries are grid lines, if the center point of a cell is in a hyperrectangle, the entire cell is in the hyperrectangle.

Once we have a solution, we replace the lower (upper) limit of any variable in any selected hyperrectangle with $-\infty$ ($+\infty$) if the edge of the hyperrectangle is on one of the boundaries of the box we imposed at the start.

Source Link
prubin ♦
prubin ♦
  • 40.9k
  • 3
  • 40
  • 109

This can be solved with an integer linear program (although I'm not sure that's the best approach). Let $D$ be the smallest rectangle containing all your individual domains. We'll set up a MIP model to cover the gaps in $D.$ Once you have that answer, you can add four unbounded rectangles (all points above $D$, all points below $D$, all points left of $D$ but not above or below, and all points right of $D$ but not above or below) and have a full answer.

To cover $D,$ we first create a grid by running horizontal and vertical lines through all corners of your various domains. We don't need the grid to be evenly spaced. I'll refer to any rectangle bounded by consecutive grid lines both vertically and horizontally as a "cell". We record the center points of each cell for future use, discarding any that are inside function domains.

Next, for every pair of grid points not on the same horizontal or vertical line we create a rectangle where one point is the lower left corner and the other is the upper right corner. Discard any rectangle that overlaps one of the function domains. This is easy to determine: either the left edge of the rectangle is to the right of the right edge of the domain (or vice versa), or the top edge of the rectangle is below the bottom edge of the domain (or vice versa), or they overlap. Enumerate the surviving rectangles as $R_1,\dots,R_N.$ Compute the set $S$ of pairs $(i,j),\, i<j$ for which $R_i$ and $R_j$ overlap (using the same logic by which we decided if rectangles and domains overlapped).

Finally, for each center point $c_i,$ compute the set $C_i = \lbrace j\in 1,\dots,N : c_i\in R_j\rbrace$ of rectangles containing that point.

Now define binary variables $x_i,\,i=1,\dots,N$ which will indicate whether or not rectangle $R_i$ is part of our cover. The objective is to minimize $\sum_i x_i,$ the number of rectangles used. To avoid rectangles intersecting, for each $(i,j)\in S$ we add the constraint $x_i + x_j \le 1,$ preventing us from using both. Finally, to ensure that everything outside the function domains is covered, for each center point $c_i$ we add the constraint $\sum_{j\in C_i} x_j = 1,$ requiring that the center point belong to exactly one selected rectangle. Since the rectangle boundaries are grid lines, if the center point of a cell is in a rectangle, the entire cell is in the rectangle.