# Constrained Minimization Problem derived from a Directed Graph

I'm looking for a solution the following graph problem for data analysis purposes.

Basically, I have a directed graph of $N$ nodes where I know the following:

• The sum of the weights of the out-edges for each node ($O_i = \Sigma_{j=1}^N e_{i,j}$ where $i$ is a node and $e_{i,j}$ represents the weight of an edge directed from node $i$ to node $j$)
• The sum of the weights of the in-edges for each node ($I_i = \Sigma_{j=1}^N e_{j,i}$ where $i$ is a node and $e_{i,j}$ represents the weight of an edge directed from node $j$ to node $i$).
• Following from the above, $\Sigma O_i = \Sigma I_i$
• No nodes have edges with themselves ($e_{i,i} = 0$)
• All $e_{i,j}$ are positive

Represented as a weighted adjacency matrix, I know the column sums and row sums but not the value of the edges themselves. I've realized that there is not a unique solution to this problem. However, I'm hoping that I can at least arrive at a solution to this problem that minimizes the sum of the edge weights or maximizes the number of 0 edge weights or something along those lines (Basically, out of infinite choices, I'd like the most 'simple' graph).

I've thought about representing it as:

Min $\Sigma e_{i,j}$ s.t. $O_i = \Sigma_{j=1}^N e_{i,j}$, $I_i = \Sigma_{j=1}^N e_{j,i}$ and $e_{i,j} \ge 0$

I'm primarily using this for data analysis in Scipy and Numpy. However, using their constrained minimization techniques, I'll end up with approximately $2N^2-N$ constraints which I'm worried will be unfeasible for large data sets. Is there an analytic solution to this that I'm missing? Any way to simplify the minimization so I don't need that many constraints?

I can suggest a solution that gives a graph with $2N-1$ or less edges.
1) Take any pair of vertices $v_i$ and $v_j$ with $O_i>0$ and $I_j>0$ and create a directed edge $(v_i, v_j)$ between them.
2) Let the weight of the edge be $min(O_i, I_j)$. If $O_i < I_j$ then $v_i$ should have no other out-edges and $v_j$ should have additional in-edges with total weight $I_j-O_i$. Let now $O_i=0$ and $I_j=I_j-O_i$ (residual total weights of the out-edges for $v_i$ and of in-edges for $v_j$).
Do similarly for the case $O_i > I_j$.
Now you have a graph with $2N-1$ edges at most. It can be not the most 'simple' graph but at least it's quite simple/sparse. (A possible simple and obvious optimization is to try to pair vertices with $O_i = I_j$ every time.)