Equilibrium Prices in Markets Modeled with Mixed Integer Programs
Dual variables give useful prices in markets models with LPs. However, many
markets have important economies of scale such as fixed or start up costs.
These markets can be modeled using mixed integer programs (
MIPs). Ever since Gomory and
Baumol examined the dual of cutting planes in
MIPs in 1960, we have “known” that there are no economically satisfactory
prices for markets modeled with MIPs. In 1990
and 1994, Yale professor Herbert Scarf explained and lamented the problem
in Operations Research and in
the widely circulated Journal of Economic
Perspectives.
We have found a simple way to get prices that support an economic equilibrium.
The key is pricing the discrete variables as well as the continuous ones.
We do this in two stages. First we solve the MIP.
Then, we add linear constraints that force the optimal solution
and drop the integrality constraints. We show that the dual variables on
the added constraints in the resulting LP effectively price the integer variables
and that the dual prices support an economic equilibrium. In particular,
we exhibit equilibrium-supporting prices for the example problem Scarf used
to explain the problem to economists. In addition to their theoretical importance,
our results have immediate practical relevance to electricity auctions where
generators have start up costs and minimum run level constraints.