If you make the objective to minimize the sum of the diagonal entries (i.e. the trace), your problem becomes a linear programming problem, solvable with readily available software (I think even Excel).  In many cases the optimal solution will have all diagonal entries $0$.

EDIT: It may help to think of the problem this way.  There are $n$ people, numbered from $1$ to $n$.  Each person $i$ has a nonnegative  amount $\pi_i$ of money, and we want to move all the money around so that everyone ends up with the same amount they started with.   $P_{ij}$ is the fraction of person $i$'s money that goes to person $j$.  Of course this will not be possible if one person has more than half the total amount of money.  Otherwise it will be possible, by the following algorithm.  We arrange the people in order clockwise from richest to poorest around a circular table, and everyone puts their money on the table in front of them (let's say in coins of a given denomination).  The richest persion (#1) takes the amount $\pi_1$ off the table, starting with #2's coins, which come after his own coins.  Each person then continues, taking the correct number of coins starting where the previous one left off.  By induction, for $k$ from $2$ to $n$, when #k's turn comes, all his coins have already been taken.