How to model and solve this problem?
Choose a modelling language, like JuMP, and solve it as a MILP.

An attempt I made with CPLEX solves a random instance ( $n=16$, $max(P)=60000$ ) to optimality almost instantly. 

I've implemented the following

$$ max(z)$$
$$ z = \sum_{i=1}^n\sum_{k=1}^n A(i,k) $$

$$   \sum_{k=1}^n A(i,k) =\sum_{k=1}^n A(k,i)\quad \forall i \in [1,n]$$
$$ A(i,k) + B(i,k) = P(i,k)\quad \forall (i,k) \in [1,n] \times [1,n]$$

$$A\in[0,max(P)-1]^{n\times n}\subset\mathbb{Z}^{n\times n}$$
$$B\in[0,max(P)-1]^{n\times n}\subset\mathbb{Z}^{n\times n}$$