How could I do it in Mosel (not in C or C++)?
I have an $n \times n$ Graeco-Latin square but with pairs of integer numbers between $1$ and $n$, instead of letters. I want to maximize the sum of the diagonal elements (both diagonal).
two boxes identical pairs are not repeated in the matrix, and, In each row, if the pair is (x,y) , the element x cannot be repeated, and the same for the element y. The same for columns.
When I say, to maximize the sum of pairs of diagonal matrix, I understand that it's the sum of 2 elements of pair in all diagonal, for example: this is a example if matrix 3x3. (I don't put all elements when I say other I want to say other pair of numbers).
(2,1) other (1,3)
other (2,3) other
(3,3) other (3,2)
so the sum is (2+1)+(2+3)+(3+2)+(1+3)+(2+3)+(3+3) , so I want maximize this sum.
I have a lot constraints but I try this in xpress (application for pc) it doesn't work. This is discrete optimization.
Thank you very much.
Part 1:
Here's some bounds to start out with. If f(n) is the maximum sum of the elements of diagonals for an n x n square. Then for odd n: $$f(n) \geq n(3n+1)$$ Why?: First let it be shown that a square can always be constructed such that the left elements of one diagonal are all n and the right elements of the other diagonal are also all n. Ex. n=5:
$$1,2,3,4,5$$ $$2,3,4,5,1$$ $$3,4,5,1,2$$ $$4,5,1,2,3$$ $$5,1,2,3,4$$
Note that these configurations by nature never produce duplicates of the same pair. Further they satisfy the rule that each row/column have one of each element. Thus the sum for each diagonal is: $$n^2 + n(n+1)/2$$ And the total sum is: $$2(n^2+n(n+1)/2)=3n^2+n=n(3n+1)$$ And for the upper bound: $$f(x) \leq 4n+ \sum_{k=0}^{2\sqrt{n}} (k+1)(2n-k)$$ For any odd square, the center tile is added twice so the maximum sum will have the maximum tile (n, n) in the center. Further, note that there are k+1 tiles that add to 2n-k. Ex. n=9,k=3: $$2n-k=15=(9+6)=(6+9)=(8+7)=(7+8)$$ A square with odd n will have 2n-1 tiles total. And 2n-2 not counting the center. Note that taking all tiles with the maximum floor(2*root(n)) distinct individual sums will mean taking 1 + 2 + ... + floor(2*root(n)) total tiles. Thus we must find an upper limit for a sum such that: $$k(k+1)/2 \geq 2n-1$$ This then implies for $k \geq 2$: $$k \geq 2\sqrt{n}$$ Taking an upper limit that large then implies we will take enough of the maximum tiles to fill the diagonals. So we have: $$f(n) \leq 2(2n) + 2(2n-1) + 3(2n-2) + 4(2n-3) + ...+(2\sqrt{n} + 1)(2n-2\sqrt{n})$$ $$=4n+ \sum_{k=0}^{2\sqrt{n}} (k+1)(2n-k)$$ This bound can be lowered further if calculated algorithmically.
Part 2:
Assumption: Given a greco-latin square of size n, all other greco-latin squares of that size can be generated by the operations of:
Next let us begin with the square described in part 1 above.
Note every row will be of the form: $p_1,...,p_k,p_{k+1},p_k,...,p_1$
Where $p_i$ represents the unordered pair $(i, n - i + 1)$
Ex. for $n=5$: $$(1,5),(2,4),(3,3),(4,2),(5,1)$$ $$(2,1),(3,5),(4,4),(5,3),(1,2)$$ $$(3,2),(4,1),(5,5),(1,4),(2,3)$$ $$(4,3),(5,2),(1,1),(2,5),(3,4)$$ $$(5,4),(1,3),(2,2),(3,1),(4,5)$$ For the first row: $$p_1=(1,5),p_2=(2,4),p_3=(3,3),p_2=(4,2),p_1=(5,1)$$ The middle element of each row has the same elements, and each other pair has its reverse mirrored across from the middle element. Meaning that swapping any two rows can be undone by swapping 2 other rows, and exchanging distinct left or right values.
So with the above assumption in mind, we can generate all greco-latin squares by:
First, we can find the number of permutations in (1.) by some recursion. $$S_k=\{p_1,...,p_k,p_k,...,p_1\}$$ $$||\{P(S_k)\}||=(2k-1)||\{P(S_{k-1})\}||$$ $$||\{P(S_k)\}||=\frac{(2k)!}{k!2^k}$$ $$||\{P(\{p_1,...,p_k,p_{k+1},p_k,...,p_1\})\}||=\frac{(2k)!(k+1)}{k!2^k}$$ At least the above number is how many permutations of columns we actually have to check to cover all "classes" of squares. (A "class" meaning vertical reflections and value swapping of the same square)
And then substitute in the corresponding n with $k=\frac{n-1}{2}$ $$||\{P(\{p_1,...,p_k,p_{k+1},p_k,...,p_1\})\}||=\frac{(n-1)!\frac{n+1}{2}}{\frac{n-1}{2}!(2^{\frac{n-1}{2}})}$$ Further there are n(n-1) choices for each possible row swaps, possible left/right value swaps.
So the final count of squares we need to check is: $$\frac{(n-1)!n^3(n+1)(n-1)^3}{\frac{n-1}{2}!(2^{\frac{n+1}{2}})}$$ Which is still $O(n^n)$ but much better than the $O((2n)^{2n})$ one gets from checking random permutations of pairs $(i, j)$
Ex. For $n=9$: 195,955,200 squares must be checked.