I want to solve the Fixed Charge Transportation Problem, although there is only a fixed cost for opening the route, no cost proportional to the edge weight. Each edge will have a maximum possible weight defined from the beginning.
The fixed cost d is 1 for every i,j and, at first, any solution, not only the one with minimal cost is acceptable, as it is possible to take cells forming a rectangle (in the matrix formulation) and redistribute quantities until one of them becomes zero, minimizing the cost. Getting the minimum cost is a hard problem in general and I may go without it.
What is the fastest algorithm to find a solution given that any cost is acceptable?
You can solve the original problem via mixed integer linear programming as follows. For each arc $(i,j)\in A$, let $u_{i,j}$ be the capacity of that arc, let nonnegative variable $x_{i,j}$ be the flow across that arc, and let binary variable $y_{i,j}$ indicate whether that arc is used. The problem is to minimize $\sum_{(i,j)\in A} y_{i,j}$ subject to \begin{align} \sum_{(i,j)\in A} x_{i,j} &= s_i &&\text{for all $i$}\\ \sum_{(i,j)\in A} x_{i,j} &= d_j &&\text{for all $j$}\\ x_{i,j} &\le u_{i,j} y_{i,j} &&\text{for all $(i,j)$} \end{align} To find a feasible solution, you can fix $y\equiv 1$ and solve the resulting transportation problem, using either a linear programming solver or some specialized network algorithm. You can then post-process to set $y_{i,j}=1$ if $x_{i,j}>0$.