Timeline for 1 rectangle <= 4 squares
Current License: CC BY-SA 2.5
24 events
when toggle format | what | by | license | comment | |
---|---|---|---|---|---|
Mar 7, 2010 at 22:35 | history | edited | TonyK | CC BY-SA 2.5 |
added 11 characters in body
|
Mar 3, 2010 at 21:49 | history | edited | TonyK | CC BY-SA 2.5 |
added 35 characters in body
|
Mar 3, 2010 at 14:00 | history | edited | TonyK | CC BY-SA 2.5 |
added 40 characters in body; added 2 characters in body
|
Mar 2, 2010 at 22:35 | history | edited | TonyK | CC BY-SA 2.5 |
added 14 characters in body; Post Made Community Wiki
|
Mar 2, 2010 at 21:49 | history | edited | TonyK | CC BY-SA 2.5 |
added 85 characters in body
|
Mar 2, 2010 at 21:39 | history | edited | TonyK | CC BY-SA 2.5 |
deleted 2890 characters in body; edited body
|
Mar 2, 2010 at 18:09 | comment | added | TonyK | I've just had a look at some linear programming pages, and it seems that searching for integer solutions is slower, not faster. Oh well. | |
Mar 2, 2010 at 17:30 | history | edited | TonyK | CC BY-SA 2.5 |
added 10 characters in body; edited body; added 20 characters in body
|
Mar 2, 2010 at 17:18 | comment | added | TonyK | FG, is your software able to look for integer solutions? If so, you can set the square constraint to |sum| <= 15,and the central 3x7 rectangle to 56. Then the solution will be much nicer, and probably faster to find. (What software are you using?) | |
Mar 2, 2010 at 15:35 | comment | added | Yaakov Baruch | this thread beats a lot of good novels! | |
Mar 2, 2010 at 15:27 | comment | added | F_G | OK, I have now a new model that is much easier to solver (uses sparser constraints) - I can confirm that 2x7 leads indeed to 67/18. And 3x7 leads to 56/15. More coming later today ... | |
Mar 2, 2010 at 14:26 | comment | added | F_G | The problem with my 1x8 test is that the solution I get does not seem to be easy to round nicely like the previous ones (some factors are obvious, like 7, but others seem inconsistent). Anyway, I put it here: dl.dropbox.com/u/217239/sol_rectangle.html I am using the symmetry. | |
Mar 2, 2010 at 13:46 | comment | added | TonyK | Also, FG, have you built the symmetry into your model? So that you only need 23x23 variables for a 45x45 grid? | |
Mar 2, 2010 at 13:16 | comment | added | TonyK | That's exactly what I'm doing, Yaakov. But it's terribly slow. FG has a much better method -- one minute, instead of a day or two! Can you say a bit more about it, FG? And perhaps you could post your solution for the 8x1 rectangle. | |
Mar 2, 2010 at 13:06 | history | edited | TonyK | CC BY-SA 2.5 |
added 83 characters in body
|
Mar 2, 2010 at 11:40 | comment | added | Yaakov Baruch | Once you have a consistent and non-improvable set of bounds, you can collapse one interval to a point within, one rectangle at a time, then refresh the set of bounds and repeat the procedure until all intervals have shrunk to a point. Unfortunately, I don't know if one can also collapse the 3 (or 1) symmetric images of the chosen rectangle without a refresh in between. | |
Mar 2, 2010 at 11:35 | comment | added | F_G | TonyK, I can confirm 26/7 is possible for a 1x8 rectangle within a 39x46 grid. Maybe we can discuss how we obtain those grids ? I use a linear programming formulation (a variable for every cell, a constraint for every square), which is quick (optimally solved in less than a minute) but runs out of memory around the 45x45 size (too many squares - it should be possible to remove some redundancies). | |
Mar 2, 2010 at 10:33 | history | edited | TonyK | CC BY-SA 2.5 |
added 9 characters in body
|
Mar 2, 2010 at 10:01 | history | edited | TonyK | CC BY-SA 2.5 |
added 520 characters in body; added 9 characters in body
|
Mar 2, 2010 at 7:52 | comment | added | TonyK | Yes, LK, the upper bounds are proved. (But the program uses floating-point arithmetic. For a proper computer-assisted proof, I suppose it would need to use rationals.) | |
Mar 2, 2010 at 7:51 | history | edited | TonyK | CC BY-SA 2.5 |
added 1245 characters in body
|
Mar 2, 2010 at 3:17 | comment | added | F_G | As far as I can check, 25/7 can also be obtained on a smaller 23x29 grid ; 31x36 seems optimal for 85/23. | |
Mar 2, 2010 at 2:08 | comment | added | F_G | TonyK, this is great ! I thought for a while that 3.5 could not be beaten, but I was looking at wrong (central rectangle/grid) size combinations (mostly too small grids). | |
Mar 1, 2010 at 23:10 | history | answered | TonyK | CC BY-SA 2.5 |