Decomposition techniques and decentralization in linear programming

In this paper, some aspects of decomposition techniques for block-angular linear programs are analyzed. In particular, we show how the decentralization of the optimal decisions cannot be performed with the classical coordination schemes. A new decentralized algorithm with mixed allocations is then introduced: a subgradient algorithm approximates the dual solution and is substituted by a fixed-point algorithm in a second step where the subproblems may exchange information directly without need of a coordination level.