tag:blogger.com,1999:blog-593563533834706486.post1408897834520371820..comments2024-03-28T10:35:10.453-04:00Comments on Yet Another Math Programming Consultant: Non-convex quadratic models II: rectangular coveringErwin Kalvelagenhttp://www.blogger.com/profile/09496091402502236997noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-593563533834706486.post-57830950178815863022020-03-04T15:04:12.741-05:002020-03-04T15:04:12.741-05:00For the 3D instance, I get 6039 useful boxes.For the 3D instance, I get 6039 useful boxes.Rob Pratthttps://www.blogger.com/profile/16525877394541155854noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-60344544742386690702020-03-04T14:58:58.934-05:002020-03-04T14:58:58.934-05:00This comment has been removed by the author.Rob Pratthttps://www.blogger.com/profile/16525877394541155854noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-58164423963314848142020-03-04T14:43:45.282-05:002020-03-04T14:43:45.282-05:00Yes, I confirm 50,658 rectangles now, including th...Yes, I confirm 50,658 rectangles now, including those with 0 area. I wrote "with a grid point on each boundary" but had not checked this condition.Rob Pratthttps://www.blogger.com/profile/16525877394541155854noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-76378572754122788122020-03-03T14:00:07.649-05:002020-03-03T14:00:07.649-05:00Yes, you can omit any rectangles that do not conta...Yes, you can omit any rectangles that do not contain any points. In that case, I get 1,342,573 nonempty rectangles; I don't understand how to get 50,658. You can also allow side length 0, in which case I get 1,386,723 nonempty but possibly 0 area rectangles.Rob Pratthttps://www.blogger.com/profile/16525877394541155854noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-64480198489556495742020-03-03T13:59:18.873-05:002020-03-03T13:59:18.873-05:00This comment has been removed by the author.Rob Pratthttps://www.blogger.com/profile/16525877394541155854noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-2717819245214224722020-03-03T13:58:37.256-05:002020-03-03T13:58:37.256-05:00This comment has been removed by the author.Rob Pratthttps://www.blogger.com/profile/16525877394541155854noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-81966328388284932832020-03-03T03:07:36.327-05:002020-03-03T03:07:36.327-05:00Great idea. I think the number of rectangle is not...Great idea. I think the number of rectangle is not 100% correct. We miss rectangles with a single point. Also some rectangles may not be of value, because one of the two "y" points (or both) may be outside the "x" window. And vice versa.Erwin Kalvelagenhttps://www.blogger.com/profile/09496091402502236997noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-73797397076332560642020-03-02T14:08:44.308-05:002020-03-02T14:08:44.308-05:00Alternatively, you can model the problem linearly ...Alternatively, you can model the problem linearly as a cardinality-constrained set covering problem, as follows. Let R be the set of all possible rectangles with a grid point on each boundary. Here, |R| = (50 choose 2)^2 = 1,500,625. For r in R, let binary variable U(r) indicate whether rectangle r is used. The objective is to minimize the total area sum {r in R} area(r) * U(r). The cardinality constraint is sum {r in R} U(r) = 5. The cover constraint for each point i is sum {r in R: i in R} U(r) >= 1. This formulation avoids the symmetry issue, and the resulting optimal solution matches yours.Rob Pratthttps://www.blogger.com/profile/16525877394541155854noreply@blogger.com