The average shadow price for MILPs with Integral resource availability and its relationship to the marginal unit shadow price

Abstract

The economic significance of the average shadow price for integer and mixed integer linear programming (MILP) problems has been established by researchers [Kim and Cho, Eur. J. Operat. Res. 37 (1988) 328; Crema Eur. J. Operat. Res. 85 (1995) 625]. In this paper we introduce a valid shadow price (ASPIRA) for integer programs where the righthand side resource availability can only be varied in discrete steps. We also introduce the concept of marginal unit shadow price (MUSP). We show that for integer programs, a sufficient condition for the marginal unit shadow price to equal the average shadow price is that the Law of Diminishing Returns should hold. The polyhedral structures that will guarantee this equivalence have been explored. Identification of the problem classes for which the equivalence holds complements the existing procedure for determining shadow price for such integer programs. The concepts of ASPIRA and MUSP introduced in this paper can play a vital role in resource acquisition plans and in defining efficient market clearing prices in the presence of indivisibilities.