Return to Answer

Here is a quick description of the linear programming formulation I used to compute some configurations:

Given a $m \times n$ grid $G$, one can describe a configuration with a real vector $x \in \mathbb{R}^{mn}$. Then, for each square featuring a nonempty intersection with $G$, one can write down an indicator vector $a_i \in \mathbb{R}^{mn}$ ($i \in S$), whose components are equal to $1$ if in the square, and $0$ otherwise. Finally, one can write $c \in \mathbb{R}^{mn}$, the indicator of the rectangle whose sum is to be maximized.

The linear program is then $$ \max_{x \in \mathbb{R}^{mn}} c^T x \text{ such that } -1 \le a_i^T x \le 1\ \forall i \in S$$ This type of program can be solved extremely efficiently up to relatively large sizes $mn$ (I am using the ILOG CPLEX solver).

Taking into account the symmetry is straightforward: if you want several components of $x$ to be equal to each other, only keep one of them and adapt the remaining coefficients in $c$ and $a_i$ (i.e. replace them with the sum of the corresponding coefficients).

However, this approach has limitations because there are a lot of vectors $a_i$, and those vectors have sometimes a lot of nonzero components (which has an influence on the efficiency of the solver and crucially on the memory used). I was only able to use it up to around a $45\times 45$ grid.

To obtain solutions for larger sizes, I used the following trick: instead of defining variable $x_{ij}$ for the content of the $(i,j)$ cell in the grid, I define variable $y_{i,j}$ as follows $$ y_{i,j} = \sum_{1\le k\le i, 1\le l \le j} x_{k,l}.$$ Then it can be checked that the sum of the square or rectangle with opposite corners $(a,b)$ and $(c,d)$ is equal to $y_{c,d}+y_{a-1,b-1}-y_{c,b-1}-y_{a-1,d}$. This means each constraint in the corresponding linear program will have at most $4$ nonzeros, which improves a lot the speed and memory requirements of the solver.

By the way, I will put my latest results in the link http://dl.dropbox.com/u/217239/sol_rectangle.html

The current largest solution ($56/15$ for a $3\times 7$ rectangle), is made of fractions with common denominator 120, but this is just a happy coincidence, for nothing forces that in the linear program (and, as remarked by TonyK, enforcing it explicitly would be very costly).

Update I have run an extensive set of runs for rectangle sizes below 20x20 and put the results at the end of the file linked above. The record is still $56/15$, which is attained by many rectangles (notably by the $1 \times 9$ on a $101\times 109$ grid). It seems like even larger grids will be needed to obtain larger sums.

Update2 $1 \times 11$ in a $137 \times 63$ grid gives $101/27$=3.7407407

Here is a quick description of the linear programming formulation I used to compute some configurations:

Given a $m \times n$ grid $G$, one can describe a configuration with a real vector $x \in \mathbb{R}^{mn}$. Then, for each square featuring a nonempty intersection with $G$, one can write down an indicator vector $a_i \in \mathbb{R}^{mn}$ ($i \in S$), whose components are equal to $1$ if in the square, and $0$ otherwise. Finally, one can write $c \in \mathbb{R}^{mn}$, the indicator of the rectangle whose sum is to be maximized.

The linear program is then $$ \max_{x \in \mathbb{R}^{mn}} c^T x \text{ such that } -1 \le a_i^T x \le 1\ \forall i \in S$$ This type of program can be solved extremely efficiently up to relatively large sizes $mn$ (I am using the ILOG CPLEX solver).

Taking into account the symmetry is straightforward: if you want several components of $x$ to be equal to each other, only keep one of them and adapt the remaining coefficients in $c$ and $a_i$ (i.e. replace them with the sum of the corresponding coefficients).

However, this approach has limitations because there are a lot of vectors $a_i$, and those vectors have sometimes a lot of nonzero components (which has an influence on the efficiency of the solver and crucially on the memory used). I was only able to use it up to around a $45\times 45$ grid.

To obtain solutions for larger sizes, I used the following trick: instead of defining variable $x_{ij}$ for the content of the $(i,j)$ cell in the grid, I define variable $y_{i,j}$ as follows $$ y_{i,j} = \sum_{1\le k\le i, 1\le l \le j} x_{k,l}.$$ Then it can be checked that the sum of the square or rectangle with opposite corners $(a,b)$ and $(c,d)$ is equal to $y_{c,d}+y_{a-1,b-1}-y_{c,b-1}-y_{a-1,d}$. This means each constraint in the corresponding linear program will have at most $4$ nonzeros, which improves a lot the speed and memory requirements of the solver.

By the way, I will put my latest results in the link http://dl.dropbox.com/u/217239/sol_rectangle.html

The current largest solution ($56/15$ for a $3\times 7$ rectangle), is made of fractions with common denominator 120, but this is just a happy coincidence, for nothing forces that in the linear program (and, as remarked by TonyK, enforcing it explicitly would be very costly).

Update I have run an extensive set of runs for rectangle sizes below 20x20 and put the results at the end of the file linked above. The record is still $56/15$, which is attained by many rectangles (notably by the $1 \times 9$ on a $101\times 109$ grid). It seems like even larger grids will be needed to obtain larger sums.

Update2 $1 \times 11$ in a $137 \times 63$ grid gives $101/27$=3.7407407

Update3 $1 \times 12$ in a $155 \times 68$ grid gives $15/4$=3.75

Unfortunately, I can only check $1 \times 13$ up to around $191\times 77$, which still gives 3.75, and I seem to have exhausted my tricks for the moment ...

Here is a quick description of the linear programming formulation I used to compute some configurations:

Given a $m \times n$ grid $G$, one can describe a configuration with a real vector $x \in \mathbb{R}^{mn}$. Then, for each square featuring a nonempty intersection with $G$, one can write down an indicator vector $a_i \in \mathbb{R}^{mn}$ ($i \in S$), whose components are equal to $1$ if in the square, and $0$ otherwise. Finally, one can write $c \in \mathbb{R}^{mn}$, the indicator of the rectangle whose sum is to be maximized.

The linear program is then $$ \max_{x \in \mathbb{R}^{mn}} c^T x \text{ such that } -1 \le a_i^T x \le 1\ \forall i \in S$$ This type of program can be solved extremely efficiently up to relatively large sizes $mn$ (I am using the ILOG CPLEX solver).

Taking into account the symmetry is straightforward: if you want several components of $x$ to be equal to each other, only keep one of them and adapt the remaining coefficients in $c$ and $a_i$ (i.e. replace them with the sum of the corresponding coefficients).

However, this approach has limitations because there are a lot of vectors $a_i$, and those vectors have sometimes a lot of nonzero components (which has an influence on the efficiency of the solver and crucially on the memory used). I was only able to use it up to around a $45\times 45$ grid.

To obtain solutions for larger sizes, I used the following trick: instead of defining variable $x_{ij}$ for the content of the $(i,j)$ cell in the grid, I define variable $y_{i,j}$ as follows $$ y_{i,j} = \sum_{1\le k\le i, 1\le l \le j} x_{k,l}.$$ Then it can be checked that the sum of the square or rectangle with opposite corners $(a,b)$ and $(c,d)$ is equal to $y_{c,d}+y_{a-1,b-1}-y_{c,b-1}-y_{a-1,d}$. This means each constraint in the corresponding linear program will have at most $4$ nonzeros, which improves a lot the speed and memory requirements of the solver.

By the way, I will put my latest results in the link http://dl.dropbox.com/u/217239/sol_rectangle.html

The current largest solution ($56/15$ for a $3\times 7$ rectangle), is made of fractions with common denominator 120, but this is just a happy coincidence, for nothing forces that in the linear program (and, as remarked by TonyK, enforcing it explicitly would be very costly).

Update I have run an extensive set of runs for rectangle sizes below 20x20 and put the results at the end of the file linked above. The record is still $56/15$, which is attained by many rectangles (notably by the $1 \times 9$ on a $101\times 109$ grid). It seems like even larger grids will be needed to obtain larger sums.

Here is a quick description of the linear programming formulation I used to compute some configurations:

Given a $m \times n$ grid $G$, one can describe a configuration with a real vector $x \in \mathbb{R}^{mn}$. Then, for each square featuring a nonempty intersection with $G$, one can write down an indicator vector $a_i \in \mathbb{R}^{mn}$ ($i \in S$), whose components are equal to $1$ if in the square, and $0$ otherwise. Finally, one can write $c \in \mathbb{R}^{mn}$, the indicator of the rectangle whose sum is to be maximized.

The linear program is then $$ \max_{x \in \mathbb{R}^{mn}} c^T x \text{ such that } -1 \le a_i^T x \le 1\ \forall i \in S$$ This type of program can be solved extremely efficiently up to relatively large sizes $mn$ (I am using the ILOG CPLEX solver).

Taking into account the symmetry is straightforward: if you want several components of $x$ to be equal to each other, only keep one of them and adapt the remaining coefficients in $c$ and $a_i$ (i.e. replace them with the sum of the corresponding coefficients).

However, this approach has limitations because there are a lot of vectors $a_i$, and those vectors have sometimes a lot of nonzero components (which has an influence on the efficiency of the solver and crucially on the memory used). I was only able to use it up to around a $45\times 45$ grid.

To obtain solutions for larger sizes, I used the following trick: instead of defining variable $x_{ij}$ for the content of the $(i,j)$ cell in the grid, I define variable $y_{i,j}$ as follows $$ y_{i,j} = \sum_{1\le k\le i, 1\le l \le j} x_{k,l}.$$ Then it can be checked that the sum of the square or rectangle with opposite corners $(a,b)$ and $(c,d)$ is equal to $y_{c,d}+y_{a-1,b-1}-y_{c,b-1}-y_{a-1,d}$. This means each constraint in the corresponding linear program will have at most $4$ nonzeros, which improves a lot the speed and memory requirements of the solver.

By the way, I will put my latest results in the link http://dl.dropbox.com/u/217239/sol_rectangle.html

The current largest solution ($56/15$ for a $3\times 7$ rectangle), is made of fractions with common denominator 120, but this is just a happy coincidence, for nothing forces that in the linear program (and, as remarked by TonyK, enforcing it explicitly would be very costly).

Update I have run an extensive set of runs for rectangle sizes below 20x20 and put the results at the end of the file linked above. The record is still $56/15$, which is attained by many rectangles (notably by the $1 \times 9$ on a $101\times 109$ grid). It seems like even larger grids will be needed to obtain larger sums.

Update2 $1 \times 11$ in a $137 \times 63$ grid gives $101/27$=3.7407407

Here is a quick description of the linear programming formulation I used to compute some configurations:

Given a $m \times n$ grid $G$, one can describe a configuration with a real vector $x \in \mathbb{R}^{mn}$. Then, for each square featuring a nonempty intersection with $G$, one can write down an indicator vector $a_i \in \mathbb{R}^{mn}$ ($i \in S$), whose components are equal to $1$ if in the square, and $0$ otherwise. Finally, one can write $c \in \mathbb{R}^{mn}$, the indicator of the rectangle whose sum is to be maximized.

The linear program is then $$ \max_{x \in \mathbb{R}^{mn}} c^T x \text{ such that } -1 \le a_i^T x \le 1\ \forall i \in S$$ This type of program can be solved extremely efficiently up to relatively large sizes $mn$ (I am using the ILOG CPLEX solver).

Taking into account the symmetry is straightforward: if you want several components of $x$ to be equal to each other, only keep one of them and adapt the remaining coefficients in $c$ and $a_i$ (i.e. replace them with the sum of the corresponding coefficients).

However, this approach has limitations because there are a lot of vectors $a_i$, and those vectors have sometimes a lot of nonzero components (which has an influence on the efficiency of the solver and crucially on the memory used). I was only able to use it up to around a $45\times 45$ grid.

To obtain solutions for larger sizes, I used the following trick: instead of defining variable $x_{ij}$ for the content of the $(i,j)$ cell in the grid, I define variable $y_{i,j}$ as follows $$ y_{i,j} = \sum_{1\le k\le i, 1\le l \le j} x_{k,l}.$$ Then it can be checked that the sum of the square or rectangle with opposite corners $(a,b)$ and $(c,d)$ is equal to $y_{c,d}+y_{a-1,b-1}-y_{c,b-1}-y_{a-1,d}$. This means each constraint in the corresponding linear program will have at most $4$ nonzeros, which improves a lot the speed and memory requirements of the solver.

By the way, I will put my latest results in the link http://dl.dropbox.com/u/217239/sol_rectangle.html

The current largest solution ($56/15$ for a $3\times 7$ rectangle), is made of fractions with common denominator 120, but this is just a happy coincidence, for nothing forces that in the linear program (and, as remarked by TonyK, enforcing it explicitly would be very costly).

Here is a quick description of the linear programming formulation I used to compute some configurations:

Given a $m \times n$ grid $G$, one can describe a configuration with a real vector $x \in \mathbb{R}^{mn}$. Then, for each square featuring a nonempty intersection with $G$, one can write down an indicator vector $a_i \in \mathbb{R}^{mn}$ ($i \in S$), whose components are equal to $1$ if in the square, and $0$ otherwise. Finally, one can write $c \in \mathbb{R}^{mn}$, the indicator of the rectangle whose sum is to be maximized.

The linear program is then $$ \max_{x \in \mathbb{R}^{mn}} c^T x \text{ such that } -1 \le a_i^T x \le 1\ \forall i \in S$$ This type of program can be solved extremely efficiently up to relatively large sizes $mn$ (I am using the ILOG CPLEX solver).

Taking into account the symmetry is straightforward: if you want several components of $x$ to be equal to each other, only keep one of them and adapt the remaining coefficients in $c$ and $a_i$ (i.e. replace them with the sum of the corresponding coefficients).

However, this approach has limitations because there are a lot of vectors $a_i$, and those vectors have sometimes a lot of nonzero components (which has an influence on the efficiency of the solver and crucially on the memory used). I was only able to use it up to around a $45\times 45$ grid.

To obtain solutions for larger sizes, I used the following trick: instead of defining variable $x_{ij}$ for the content of the $(i,j)$ cell in the grid, I define variable $y_{i,j}$ as follows $$ y_{i,j} = \sum_{1\le k\le i, 1\le l \le j} x_{k,l}.$$ Then it can be checked that the sum of the square or rectangle with opposite corners $(a,b)$ and $(c,d)$ is equal to $y_{c,d}+y_{a-1,b-1}-y_{c,b-1}-y_{a-1,d}$. This means each constraint in the corresponding linear program will have at most $4$ nonzeros, which improves a lot the speed and memory requirements of the solver.

By the way, I will put my latest results in the link http://dl.dropbox.com/u/217239/sol_rectangle.html

The current largest solution ($56/15$ for a $3\times 7$ rectangle), is made of fractions with common denominator 120, but this is just a happy coincidence, for nothing forces that in the linear program (and, as remarked by TonyK, enforcing it explicitly would be very costly).

Update I have run an extensive set of runs for rectangle sizes below 20x20 and put the results at the end of the file linked above. The record is still $56/15$, which is attained by many rectangles (notably by the $1 \times 9$ on a $101\times 109$ grid). It seems like even larger grids will be needed to obtain larger sums.