\[\begin{align}& {\color{darkred}x}_{lo} := \min_i {\color{darkblue}p}_{i,x} \\ & {\color{darkred}x}_{up} := \max_i {\color{darkblue}p}_{i,x} \\ & {\color{darkred}y}_{lo} := \min_i {\color{darkblue}p}_{i,y} \\ &{\color{darkred}y}_{up} := \max_i {\color{darkblue}p}_{i,y} \\ & {\color{darkred}{\mathit{area}}} := ({\color{darkred}x}_{up}-{\color{darkred}x}_{lo}) \cdot ({\color{darkred}y}_{up}-{\color{darkred}y}_{lo}) \end{align}\]
We don't need an optimization model for this. A much more interesting problem is: find the smallest enclosing axis-aligned rectangle for \(k\lt n\) points, where the algorithm or model can choose the subset of \(k\) points. An algorithm for this is [1]. Here, of course, we try to solve this using an optimization model.
Data
I use a small dataset here with \(n=100\) data points.
Dataset
---- 37 PARAMETER p points x y point1 4.973 9.639 point2 8.739 8.443 point3 1.912 4.945 point4 2.346 3.810 point5 6.009 1.515 point6 5.077 4.633 point7 3.591 1.526 point8 3.664 8.260 point9 0.239 0.593 point10 2.848 1.140 point11 8.905 3.743 point12 2.341 1.477 point13 0.191 0.784 point14 9.280 5.550 point15 6.164 3.605 point16 5.214 4.320 point17 7.499 8.174 point18 0.160 3.729 point19 6.971 7.669 point20 8.875 8.117 point21 7.897 8.036 point22 0.166 3.932 point23 9.601 7.215 point24 8.147 8.375 point25 7.745 5.283 point26 6.557 3.924 point27 4.851 4.026 point28 4.346 1.935 point29 1.290 4.876 point30 7.912 6.856 point31 3.026 0.001 point32 4.463 8.148 point33 2.080 3.360 point34 2.816 1.565 point35 6.203 8.599 point36 6.153 3.857 point37 7.633 7.315 point38 0.798 0.829 point39 0.192 2.454 point40 3.341 3.038 point41 8.349 3.863 point42 0.531 5.056 point43 1.919 2.345 point44 9.347 7.861 point45 9.435 1.718 point46 1.817 2.026 point47 5.323 5.065 point48 2.108 6.382 point49 2.959 5.533 point50 0.342 8.075 point51 3.551 9.887 point52 8.136 7.153 point53 2.435 5.417 point54 5.019 1.108 point55 1.686 2.869 point56 8.416 8.060 point57 5.631 1.570 point58 2.715 0.339 point59 7.184 7.050 point60 1.577 7.522 point61 9.554 7.855 point62 2.566 0.880 point63 7.997 2.193 point64 9.556 8.034 point65 4.599 2.022 point66 8.957 5.241 point67 8.720 9.062 point68 3.519 3.229 point69 9.245 6.341 point70 4.141 2.687 point71 2.817 7.412 point72 6.571 4.559 point73 3.806 4.961 point74 8.999 5.323 point75 0.602 3.960 point76 4.302 9.600 point77 2.717 8.777 point78 1.872 4.952 point79 3.734 4.279 point80 9.519 5.120 point81 4.618 4.190 point82 0.915 9.232 point83 9.528 6.382 point84 5.353 8.983 point85 0.462 4.249 point86 8.164 4.834 point87 8.054 3.067 point88 8.594 7.318 point89 5.609 3.905 point90 2.741 4.446 point91 9.810 2.776 point92 7.988 9.737 point93 5.810 7.965 point94 8.287 7.178 point95 4.339 2.033 point96 2.708 6.648 point97 1.108 8.467 point98 2.175 2.350 point99 8.997 8.511 point100 8.928 2.236
Nonconvex optimization model
We can design an optimization model around two concepts:
- Select \(k\) out of \(n\) data points
- Draw a rectangle around these points
Then minimize the size (i.e. area) of the rectangle.
A complete optimization model for the \(k\) out of \(n\) minimum rectangle problem can look like:
| High-level model |
|---|
| \[\begin{align} \min\> &{\color{darkred}{\mathit{area}}} = \prod_c ({\color{darkred}{\mathit{rect}}}_{c,up}-{\color{darkred}{\mathit{rect}}}_{c,lo}) \\ & {\color{darkred}\delta}_i = 1 \implies {\color{darkblue}p}_{i,c} \in [{\color{darkred}{\mathit{rect}}}_{c,lo},{\color{darkred}{\mathit{rect}}}_{c,up}] \\ & \sum_i{\color{darkred}\delta}_i = {\color{darkblue}k} \\ & {\color{darkred}\delta}_i \in \{0,1\} \\ & c \in \{x,y\} \end{align}\] |
The objective is quadratic and non-convex, so we need to use a global solver.
The indicator constraint can be rewritten as big-M constraints: \[\begin{align} &{\color{darkred}{\mathit{rect}}}_{c,lo} \le {\color{darkblue}p}_{i,c} {\color{darkred}\delta}_i + {\color{darkblue}M}(1-{\color{darkred}\delta}_i) \\ & {\color{darkred}{\mathit{rect}}}_{c,up} \ge {\color{darkblue}p}_{i,c} {\color{darkred}\delta}_i \end{align}\] Note that we know that \[{\color{darkblue}p}_{i,c} \in [0,{\color{darkblue}M}], {\color{darkblue}M}=10\] Obviously, \[{\color{darkred}{\mathit{rect}}}_{c,lo},{\color{darkred}{\mathit{rect}}}_{c,up} \in [0,{\color{darkblue}M}]\] If we want we can tighten this slightly: \[\begin{align}&{\color{darkred}{\mathit{rect}}}_{c,lo},{\color{darkred}{\mathit{rect}}}_{c,up} \in [\min_i {\color{darkblue}p}_{i,c},\max_i {\color{darkblue}p}_{i,c}]\end{align}\] It is always a very good idea to bound all decision variables carefully in non-convex models.
Some solvers may benefit from an extra linear constraint: \[{\color{darkred}{\mathit{rect}}}_{c,lo} \le {\color{darkred}{\mathit{rect}}}_{c,up}\]
Note that all constraints are linear.
ChatGPT suggested to explicitly allow more than \(k\) points in the rectangle by changing the equality constraint into an inequality. We already allow more points in the rectangle. In the picture below, we could have some blue points inside the rectangle. As long as this does not affect optimality, that is fine. I am not sure why that proposed change is a good idea.
Solution
---- 101 VARIABLE rect2.L contain k points min max x 7.184 9.601 y 4.834 8.511 ---- 101 VARIABLE delta.L point is selected point2 1.000, point14 1.000, point17 1.000, point20 1.000, point21 1.000, point23 1.000, point24 1.000 point25 1.000, point30 1.000, point37 1.000, point44 1.000, point52 1.000, point56 1.000, point59 1.000 point61 1.000, point64 1.000, point66 1.000, point69 1.000, point74 1.000, point80 1.000, point83 1.000 point86 1.000, point88 1.000, point94 1.000, point99 1.000 ---- 101 VARIABLE area.L = 8.887 size of rectangle
Looking at the distribution of the data points, the location of the rectangle seems to make sense: there is a bit of a cluster of points there in the right upper corner.
-------------------------------------------------------------------------------
Time (s) Nodes explored Nodes remaining Best possible Best found Relative Gap
-------------------------------------------------------------------------------
0 1 1 +0.000e+00 +2.341e+01 --
6 13 11 +4.392e+00 +8.887e+00 +5.058e-01
11 66 4 +8.829e+00 +8.887e+00 +6.559e-03
11 76 0 +8.886e+00 +8.887e+00 +1.000e-04
-------------------------------------------------------------------------------
Termination Status : Global minimum
Best Feasible Point: +8.887291e+00
Best Possible Point: +8.886402e+00
Relative Gap: +1.000000e-04
Conclusion
This is a small, simple model that allows us to find global, proven solutions.
References
- Timothy M. Chan and Sariel Har-Peled, Smallest k-Enclosing Rectangle Revisited, 2019, https://arxiv.org/abs/1903.06785.
No comments:
Post a Comment