Faculty of Engineering and Natural Sciences
Non-negativity of start-up prices and uniqueness of shadow prices in a resource allocation model with indivisibilities
Prof. Suvrajeet Sen
The Ohio State University
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.
Suvrajeet Sen is Professor of Industrial and Systems Engineering at the Ohio State University. Recently, he also served as a program director at NSF where he was responsible for the Operations Research, and the Service Enterprise Engineering programs. At NSF, he also headed the Cyberinfrastructure planning activities of the Engineering Directorate. Prior to joining OSU, he was a Professor at the University of Arizona since 1982.
Professor Sen is a fellow of INFORMS. He has served on the editorial board of several journals, including Operations Research as Area Editor for Optimization, and as Associate Editor in INFORMS Journal on Computing, and Journal of Telecommunications Systems. Professor Sen is the past-Chair of the INFORMS Telecommunications Section and founded the INFORMS Optimization Section.
Professor Sen's research is devoted to the theory and applications of large scale optimization algorithms, especially those arising from modeling risk and uncertainty. Professor Sen's contributions to the study of infrastructures include his work on telecommunications network planning, traffic control in vehicular networks, power generation networks, and others.
July 8, 2008, 14:40, FENS G035