Average shadow prices in integer linear programming

Abstract

A substitute for the concept of shadow prices in integer linear programming (ILP) is proposed, defined and calculated in this thesis. Some relating properties are also examined. We had to apart from the conventional marginal approach to develop the concept of shadow prices in ILP. The approach taken here is base on management decisions from the point of view of the system``s manager. The existence and the uniqueness that have not been achieved till now from other studies on pricing in ILP, are guaranteed for the shadow prices defined in this thesis. These prices give some important decision criteria for management decisions on buying or selling a resource just like the shadow prices in linear programming. A version of complementary slackness theorem in ILP has been achieved from these prices. The mathematically represented definition of these shadow prices is proved to be also applicable to those in convex programming. An easy and general procedure, independent of the specific algorithms used, is devised for obtaining the bounds for these shadow prices, and an iterative method for computing the precise values which is finitely terminated and efficient in a sense is suggested. A definition of equilibrium prices in ILP is also proposed from the shadow prices obtained. Some stability or continuity properties of the shadow prices are achieved under some restrictive assumptions.