LAUSR

The optimization problem studied in this paper generalizes the standard transportation problem and turns out to be NP-hard under the positive fixed costs of the transmission lines expansion. For a market with a tree-type network, a method for the supply-demand balances transfer to its root node is proposed. The method is based on the Welfare Theorem, and it proceeds from a solution to an auxiliary convex optimization problem with zero fixed costs for the lines expansion. The complexity of the method for the auxiliary problem is proven to be quadratic with respect to the number of nodes. Also, the proposed method is modified to obtain an approximate solution to the original problem and to estimate the welfare loss corresponding to this solution.