A new method for solving a linear two-level decentralized problem

Many solution methods have been presented for solving a linear two-level decentralized planning problem. Unfortunately, existing methods require too much computation time to apply and some methods can not always provide the global optimum. This paper proposed a new method, called a ‘two-level simplex algorithm’, for solving a linear two-level decentralized problem. This method is one of the vertex enumeration approach which exploits the properties that an optimal solution to the linear two-level decentralized problem is an extreme point of a feasible solution set in the upper-level problem and that the feasible solution set is non-convex, closed and connected. In order to enumerate an adjacent vertex satisfying optimality conditions of the lower-level problem with a resource allocation given by the upper-level, the proposed method newly employs dual simplex pivot iterations in the lower-level problem, which successfully provides the adjacent vertices according to a parametric linear programming method. Computation time of the proposed method tends to decrease as the conflict of the objective functions between the upper and lower problems increases, especially when the lower-level problem is decomposable to be solved more efficiently. [In Japanese.]