In [1] a problem is posted:
Given \(n\) points and a collection of tiles (rectangles) of given size, try to cover all all points with the minimum number of tiles.
There are a number of things to consider:
- Are the tiles of equal size or have they different sizes?
- Can tiles overlap?
- After minimizing the number of tiles, should we minimize the total size of the selected tiles, so we select the smaller tiles when possible.
Data
Let's generate some data, assuming tiles have different sizes:
---- 19 PARAMETER p location of points
x y
p1 17.175 84.327
p2 55.038 30.114
p3 29.221 22.405
p4 34.983 85.627
p5 6.711 50.021
p6 99.812 57.873
p7 99.113 76.225
p8 13.069 63.972
p9 15.952 25.008
p10 66.893 43.536
p11 35.970 35.144
p12 13.149 15.010
p13 58.911 83.089
p14 23.082 66.573
p15 77.586 30.366
p16 11.049 50.238
p17 16.017 87.246
p18 26.511 28.581
p19 59.396 72.272
p20 62.825 46.380
p21 41.331 11.770
p22 31.421 4.655
p23 33.855 18.210
p24 64.573 56.075
p25 76.996 29.781
p26 66.111 75.582
p27 62.745 28.386
p28 8.642 10.251
p29 64.125 54.531
p30 3.152 79.236
---- 19 PARAMETER r size of rectangles
x y
r1 12.183 15.270
r2 25.769 32.506
r3 15.344 11.024
r4 27.554 28.637
r5 21.681 20.761
r6 17.291 17.393
r7 13.915 38.003
r8 21.398 33.502
r9 19.001 13.764
r10 32.466 12.077
 |
Random points
|
Model
To model this problem, we introduce binary variables \(\mathit{select}_j \in \{0,1\}\): \[\mathit{select}_j = \begin{cases} 1 & \text{if tile $j$ is selected}\\ 0 & \text{otherwise}\end{cases}\] and a continuous variable \(\mathit{place}_{j,c}\) indicating the \(x\) and \(y\) coordinates of (selected) tile \(j\). To be precise: it is the left-lower corner of the rectangle. The set \(c\) is simply \(c=\{x,y\}\). In addition we need a variable indicating if a point is covered by a tile:\[\mathit{cov}_{i,j}=\begin{cases} 1 & \text{if point $i$ is covered by tile $j$} \\ 0 &\text{otherwise}\end{cases} \]
The model can look like:
| MIP Model |
|---|
| \[\begin{align}\min &\sum_j \color{darkred}{\mathit{select}}_j \\ & \color{darkred}{\mathit{place}}_{j,c} \le \color{darkblue}p_{i,c}+\color{darkblue}M\cdot(1-\color{darkred}{\mathit{cov}}_{i,j}) && \forall i,j,c \\ &\color{darkred}{\mathit{place}}_{j,c}+\color{darkblue}r_{j,c}\ge\color{darkblue}p_{i,c}-\color{darkblue}M\cdot(1-\color{darkred}{\mathit{cov}}_{i,j}) && \forall i,j,c \\ & \color{darkred}{\mathit{cov}}_{i,j} \le \color{darkred}{\mathit{select}}_j && \forall i,j \\ & \sum_j \color{darkred}{\mathit{cov}}_{i,j} \ge 1 && \forall i \\ & \color{darkred}{\mathit{select}}_j \in \{0,1\} \\ & \color{darkred}{\mathit{cov}}_{i,j} \in \{0,1\} \end{align}\] |
Our points are drawn from \[p_{i,c}\sim U(0,100)\] So it make sense to restrict the placement of tiles to: \[0 \le \mathit{place}_{j,c} \le 100-r_{j,c}\] Using this, a good value for \(M\) is \(M=100\).
Results
---- 55 VARIABLE z.L = 7.000 objective
---- 55 PARAMETER tile placement of tiles
x y w h
r1 53.928 67.819 12.183 15.270
r2 5.652 25.769 32.506
r4 27.484 6.507 27.554 28.637
r5 78.131 55.464 21.681 20.761
r6 5.791 49.181 17.291 17.393
r8 56.188 22.573 21.398 33.502
r10 2.517 75.169 32.466 12.077
 |
| Points are covered by tiles |
No overlap
We can add no-overlap constraints [2] to the model soo that no pair of tiles can overlap. Just to be sure, I'll allow tiles to go outside the area \([0,100]\times [0,100]\). Of course, that also has an impact on the value for \(M\). The new solution looks like:
 |
With no-overlap constraints
|
Same-sized tiles
If all tiles are identical, we just have a special case of our original problem. It may make sense to add an ordering constraint: \[\mathit{select}_j \le \mathit{select}_{j-1}\] We can also consider additional symmetry-breaking constraints, such as \[\mathit{place}_{j,x} \ge \mathit{place}_{j,x-1}\] It requires some experimentation if these constraints pay off in performance.
 |
All tiles have the same size
|
In this example all the times are \((20 \times 20)\). Below is a larger example with \(n=50\) points and \((10 \times 10)\) tiles.
 |
Larger example
|
Set-covering formulation for equal-sized tiles
If the problem has all equal-sized tiles, we can employ a very different algorithm. For this we need to generate candidate locations in advance. One way to generate those is as follows:
- \(k:=0\)
- For each point with coordinates \((x_1,y_1)\):
- For each point with coordinates \((x_2,y_2)\) such that \(x_1 \le x_2 \le x_1+w\) and \(y_1-h\le y_2\le y_1+h\):
- Form the candidate rectangle \((x_1,y_2)-(x_1+w,y_2+h)\)
- \(k := k+1\)
- Store as \(\mathit{loc}_{k,c}=(x_1,y_2)\)
- Find all points \(i\) inside the candidate rectangle, and store this inside a mapping \(\mathit{contain}_{k,i}\)
Now we can solve the set-covering problem [3]:
| Set-covering Model |
|---|
|
\[\begin{align}\min & \sum_j \color{darkred}{\mathit{select}}_j \\ & \sum_j \color{darkblue}{\mathit{contain}}_{j,i} \cdot \color{darkred}{\mathit{select}}_j \ge 1 && \forall i \\ & \color{darkred}{\mathit{select}}_j \in \{0,1\}\end{align}\]
|
where \[\mathit{contain}_{j,i} = \begin{cases} 1 & \text{if candidate rectangle $j$ contains point $i$}\\ 0 & \text{otherwise}\end{cases}\]
This model solves very fast.
A multi-criteria version
Instead of just minimizing the number of tiles, we can subsequently minimize the total area covered by the tiles. I.e. use smaller tiles if possible. This is essentially a multi-objective problem. We used here a lexicographic approach (i.e. do two solves in sequence). In our experiment, we reduced the total size of the selected tiles from 3672.5809 to 3004.0812.
 |
| Multi-objective model results |
Obviously, this additional step makes only sense if the tiles have different sizes.
GAMS Models
As requested, here are some of the source files.
Model for tiles with different sizes.
|
set
i 'points to cover' /p1*p30/
j 'rectangles' /r1*r10/
c 'coordinates' /x,y/
;
parameter
A 'side of area' / 100 /
M 'big-M'
p(i,c) 'location of points'
r(j,c) 'size of rectangles'
;
p(i,c) = uniform(0,A);
r(j,c) = uniform(10,40);
M = A;
display p,r;
binary variable select(j) 'select tile';
positive variable place(j,c) 'placement of tile';
place.up(j,c) = A-r(j,c);
variable z 'objective';
binary variable cov(i,j);
equations
obj
cover1
cover2
cover3
cover4
;
obj.. z =e= sum(j, select(j));
cover1(i,j,c).. place(j,c) =l=
p(i,c)+M*(1-cov(i,j));
cover2(i,j,c).. place(j,c)+r(j,c) =g=
p(i,c)-M*(1-cov(i,j));
cover3(i,j).. cov(i,j) =l= select(j);
cover4(i).. sum(j,cov(i,j)) =g= 1;
model m1 /all/;
option optcr=0,
threads=8;
solve m1
minimizing z using mip;
select.l(j) = round(select.l(j));
parameter tile(j,*) 'placement of tiles';
tile(j,c) = place.l(j,c)*select.l(j);
tile(j,'w')$select.l(j) = r(j,'x');
tile(j,'h')$select.l(j) = r(j,'y');
display z.l,tile;
|
Set-covering model for equal-sized tiles.
|
set
i 'points to cover' /p1*p50/
j 'candidate rectangles' /r1*r1000/
contain(j,i) 'points contained in
rectangle j'
c 'coordinates' /x,y/
;
parameter
A 'side of area' / 100 /
p(i,c) 'location of points'
r(c) 'size of rectangles' /x 10, y 10/
loc(j,c) 'locations of candidate rectangles'
;
p(i,c) = uniform(0,A);
display p,r;
*------------------------------------------------------------
* generate candidate rectangle locations
*------------------------------------------------------------
alias (i,ii,iii);
scalar k / 0 /;
loop(i,
loop(ii$(p(ii,'x')
>= p(i,'x') and p(ii,'x') <= p(i,'x')+r('x') and
abs(p(ii,'y')-p(i,'y')) <= r('y')),
k = k + 1;
loop(j$(ord(j)=k),
loc(j,'x') = p(i,'x');
loc(j,'y') = p(ii,'y')-r('y');
contain(j,iii) = p(iii,'x') >= loc(j,'x') and p(iii,'x') <= loc(j,'x')+r('x') and
p(iii,'y') >= loc(j,'y') and p(iii,'y') <= loc(j,'y')+r('y')
);
);
);
*------------------------------------------------------------
* set covering model
*------------------------------------------------------------
binary variable select(j) 'select tile';
variable z 'objective';
equations
obj
cover(i)
;
obj.. z =e= sum(j, select(j));
cover(i).. sum(contain(j,i),select(j)) =g= 1;
model m1 /all/;
option optcr=0;
solve m1
minimizing z using mip;
*------------------------------------------------------------
* reporting
*------------------------------------------------------------
parameter tile(j,*) 'placement of tiles';
tile(j,c) = loc(j,c)*select.l(j);
tile(j,'w')$select.l(j) = r('x');
tile(j,'h')$select.l(j) = r('y');
display z.l,tile;
|
The R code to plot the results looks like:
library(ggplot2)
pt <- read.table(text="p x y
p1 17.175 84.327
p2 55.038 30.114
p3 29.221 22.405
p4 34.983 85.627
p5 6.711 50.021
p6 99.812 57.873
p7 99.113 76.225
p8 13.069 63.972
p9 15.952 25.008
p10 66.893 43.536
p11 35.970 35.144
p12 13.149 15.010
p13 58.911 83.089
p14 23.082 66.573
p15 77.586 30.366
p16 11.049 50.238
p17 16.017 87.246
p18 26.511 28.581
p19 59.396 72.272
p20 62.825 46.380
p21 41.331 11.770
p22 31.421 4.655
p23 33.855 18.210
p24 64.573 56.075
p25 76.996 29.781
p26 66.111 75.582
p27 62.745 28.386
p28 8.642 10.251
p29 64.125 54.531
p30 3.152 79.236
",header=T)
r <- read.table(text="r x y w h
r1 53.928 67.819 12.183 15.270
r2 15.562 2.638 25.769 32.506
r4 50.032 27.438 27.554 28.637
r5 7.540 4.247 21.681 20.761
r6 5.791 49.181 17.291 17.393
r7 85.897 38.222 13.915 38.003
r10 2.517 75.169 32.466 12.077
",header=T)
ggplot(pt, aes(x=x , y=y)) + geom_point() +
geom_rect(data=r, aes(xmin=x,xmax=x+w,ymin=y,ymax=y+h,color=r,fill=r,alpha=0.1))+
guides(alpha=FALSE)
Conclusion
The small MIP model presented above can be used as a basis for alternative, related problems. For equal-sized tiles, a faster set-covering model is shown.
References
No comments:
Post a Comment