(A) study on the general duality in mathematical programming

Abstract

The general duality theory in mathematical programming has widened the concept of prices from the traditional linear prices or multipliers to the nonlinear price functions. The resulting major advantages can be stated in two respects. The first advantage is the reduction of the duality gap resulting from the release of the linear restriction on the optimal dual solutions. The second advantage of the general duality lies in the rich economic interpretations of the optimal price functions for the economic problems with nonconvexities. This thesis treats this general duality theory both from the viewpoints of solution methods and the concept of prices. Consequently we have two distinct purposes of this thesis, one for solution methods and the other for a new concept of price function. Motivated from the recent developments of the decomposition methods using the general duality and price functions, we have tried to identify the relations between the primal decompositions and the dual decompositions. Unlike other studies of the same interest we have excluded the masterproblems and concentrated only on the subproblems. We have identified significant relations between the primal subproblems and dual subproblems even where there may exist a positive Lagrangean duality gap. We call these relations the epsilon-symmetric relations between the two decomposition methods. To test the validity of our results we have selected a special class of mixed integer programs and the results have been encouraging. The study on the concept of a price function in this thesis generalizes the concept of average shadow prices, first developed for integer programming, to general mathematical programming. We have defined the average shadow price for a given activity and the concept of average price function. We have identified some relating properties of them and discussed rich economic interpretations involved. Furthermore we have suggested some practical procedures of obtaining the uppe...