In a Latin square consists of natural numbers 1,2, ..., 5 with each number appearing in each row, column and diagonal exactly once, what is the minimal sum of the lower triangle below the main diagonal?
Since there are $4$ columns (rows) in the lower triangle, each number can appear there at most 3 times while there are 10 entries to fill, a lower bound is $3\times(1+2+3)+4=22$.
What is the generalization of this problem to the $n\times n$ Latin square?
Latin squares do not normally have any conditions on diagonals. Which diagonals do you mean? If you want distinct entries on each the two main diagonals, I get a minimum sum of 26 for $n=5$:
You can solve this problem via integer linear programming as follows. For $i,j,k \in \{1,\dots,n\}$, let binary decision variable $x_{i,j,k}$ indicate whether cell $(i,j)$ takes value $k$. The problem is to minimize $\sum_{i=1}^n \sum_{j=1}^{i-1} \sum_{k=1}^n k\ x_{i,j,k}$ subject to the following constraints (with dual variables in parentheses): \begin{align} \sum_{j=1}^n x_{i,j,k} &= 1 &&\text{for $i,k \in \{1,\dots,n\}$} &&\text{($r_{i,k}$ free)}\\ \sum_{i=1}^n x_{i,j,k} &= 1 &&\text{for $j,k \in \{1,\dots,n\}$} &&\text{($c_{j,k}$ free)}\\ \sum_{k=1}^n x_{i,j,k} &= 1 &&\text{for $i,j \in \{1,\dots,n\}$} &&\text{($v_{i,j}$ free)}\\ \sum_{i=1}^n x_{i,i,k} &= 1 &&\text{for $k \in \{1,\dots,n\}$} &&\text{($d_{k}$ free)}\\ \sum_{i=1}^n x_{i,n-i+1,k} &= 1 &&\text{for $k \in \{1,\dots,n\}$} &&\text{($a_{k}$ free)}\\ x_{i,j,k} &\in \{0,1\} &&\text{for $i,j,k \in \{1,\dots,n\}$} \end{align} As with all integer linear programming problems, you can get a lower bound and short certificate of that bound by relaxing integrality and solving the resulting linear programming (LP) problem. The certificate consists of optimal dual variables associated with the constraints, and these are a natural by-product of most LP solvers. The idea is that you multiply both sides of each constraint by its corresponding dual variable and add everything up across constraints to get an inequality of the form $z \ge c$, where $z$ is the objective function and $c$ is a constant. For $n=5$, the LP lower bound turns out to be 24, attained by a solution that yields the following grid, where entry $(i,j)$ has value $\sum_{k=1}^n k\ x_{i,j,k}$:
The corresponding dual variable values are: $$r = \begin{pmatrix} -0.5 &0.0 &0.0 &-0.2 &-1.7 \\ -0.7 &0.0 &0.1 & 0.0 &-1.3 \\ -0.9 &0.0 &0.4 & 0.5 &-0.7 \\ -1.3 &0.0 &0.6 & 1.0 & 0.0 \\ -1.5 &0.0 &0.7 & 1.2 & 0.4 \\ \end{pmatrix} \\ c = \begin{pmatrix} -0.3 &0.0 &0.6 &1.2 &2.9 \\ -0.1 &0.0 &0.5 &1.0 &2.5 \\ 0.0 &-0.3 &0.0 &0.2 &1.5 \\ 0.5 &0.0 &0.0 &0.0 &1.2 \\ 0.7 &0.0 &-0.1 &-0.2 &0.8 \\ \end{pmatrix} \\ v = \begin{pmatrix} -0.3 &-0.8 &0.0 &0.0 &0.0 \\ 2.0 &-0.3 &-0.2 &0.0 &0.0 \\ 2.0 &2.0 &0.0 &-0.5 &-0.3 \\ 1.8 &2.0 &2.3 &-0.3 &-0.8 \\ 1.6 &1.8 &2.3 &2.0 &-0.3\\ \end{pmatrix} \\ d = \begin{pmatrix} 1.1 \\ 0.3 \\ -0.3 \\ -0.7 \\ -0.9 \\ \end{pmatrix} \\ a = \begin{pmatrix} -0.2 \\ 0.0 \\ -0.1 \\ 0.0 \\ 0.1 \\ \end{pmatrix} $$ There are also reduced costs (duals on the lower bound constraints $-x_{i,j,k} \le 0$) as follows: $$ \begin{matrix} i &j &k & \\ 1 & 2 & 1 & 1.4 \\ 1 & 2 & 2 & 0.8 \\ 1 & 2 & 3 & 0.3 \\ 1 & 3 & 1 & 0.5 \\ 1 & 3 & 2 & 0.3 \\ 1 & 3 & 5 & 0.2 \\ 1 & 4 & 4 & 0.2 \\ 1 & 4 & 5 & 0.5 \\ 1 & 5 & 3 & 0.2 \\ 1 & 5 & 4 & 0.4 \\ 1 & 5 & 5 & 0.8 \\ 2 & 1 & 3 & 0.3 \\ 2 & 1 & 4 & 0.8 \\ 2 & 1 & 5 & 1.4 \\ 2 & 3 & 1 & 0.9 \\ 2 & 3 & 2 & 0.5 \\ 2 & 3 & 3 & 0.1 \\ 2 & 4 & 1 & 0.4 \\ 2 & 5 & 4 & 0.2 \\ 2 & 5 & 5 & 0.5 \\ 3 & 1 & 1 & 0.2 \\ 3 & 1 & 4 & 0.3 \\ 3 & 1 & 5 & 0.8 \\ 3 & 2 & 3 & 0.1 \\ 3 & 2 & 4 & 0.5 \\ 3 & 2 & 5 & 1.2 \\ 3 & 4 & 1 & 0.9 \\ 3 & 4 & 2 & 0.5 \\ 3 & 4 & 3 & 0.1 \\ 3 & 5 & 1 & 0.5 \\ 3 & 5 & 2 & 0.3 \\ 3 & 5 & 5 & 0.2 \\ 4 & 1 & 1 & 0.8 \\ 4 & 1 & 2 & 0.2 \\ 4 & 1 & 5 & 0.3 \\ 4 & 2 & 1 & 0.6 \\ 4 & 2 & 5 & 0.4 \\ 4 & 3 & 3 & 0.1 \\ 4 & 3 & 4 & 0.5 \\ 4 & 3 & 5 & 1.2 \\ 4 & 5 & 1 & 1.4 \\ 4 & 5 & 2 & 0.8 \\ 4 & 5 & 3 & 0.3 \\ 5 & 1 & 1 & 1.4 \\ 5 & 1 & 2 & 0.4 \\ 5 & 1 & 3 & 0.2 \\ 5 & 2 & 1 & 0.8 \\ 5 & 2 & 2 & 0.2 \\ 5 & 2 & 5 & 0.3 \\ 5 & 3 & 1 & 0.2 \\ 5 & 3 & 4 & 0.3 \\ 5 & 3 & 5 & 0.8 \\ 5 & 4 & 3 & 0.3 \\ 5 & 4 & 4 & 0.8 \\ 5 & 4 & 5 & 1.4 \\ \end{matrix} $$ To use these to derive the lower bound of 24 on the optimal objective, multiply both sides of each constraint by these values. For example, $r_{1,1}=-0.5$, so multiply both sides of $\sum_{j=1}^5 x_{1,j,1} = 1$ by $-0.5$ to get $-0.5 \sum_{j=1}^5 x_{1,j,1} = -0.5$. Do the same for each nonzero dual. For the reduced costs, multiply $-x_{1,2,1} \le 0$ by $1.4$ to get $-1.4x_{1,2,1} \le 0$. Do the same for each nonzero reduced cost. Adding all these up yields $\sum_{i,j,k} k\ x_{i,j,k} \ge 24$.