Start-up Prices and Shadow Prices for Resource Allocation Models with Indivisibilities

Abstract: In the presence of indivisible goods, resource allocation models often result in mixed-integer linear programs (MILP). Unlike linear programming duality however, MILP problems present duality gaps and dual variables (as part of the price system) are not unique and not as conveniently interpreted. These issues have been visited for almost fifty years starting with Gomory and Baumol (1960) and subsequently by a number of other authors. However, finding a price system in resource allocation models with indivisibilities that has attributes of shadow prices has remained a long-standing unresolved problem in economic theory. In this paper, we resolve this issue for binary MILP problems. We provide an important step in allocating charges of indivisible goods, and recover the total costs of inputs. Moreover, we characterize unique (two-sided) shadow prices for resources in binary MILP problems. We also provide an economic interpretation of implied constraints in the form of productivity requirements that must be satisfied for integer programming problems. Key words: resource allocation; mixed-integer linear programming; shadow prices