[Help-glpk] clearing prices in markets with nonconvexities

[Robbie Morrison]

Hello all

Some background first.  A common problem in
microeconomics is to determine the clearing in
a commodity market.  If the problem can be
formulated as a linear program, the optimal
solution provides the clearing quantity and the
dual provides the marginal cost and hence the
clearing price.  The method can be extended to
a set of interacting markets under general
equilibrium.

If the underlying structure is mixed-integer (with
the integer variables normally binary) then the
situation is a little more complex.  O'Neill etal
(2002) discuss this solution process in this case:

  "Our method for calculating equilibrium prices
   is straightforward. First, we solve a MIP to
   find the optimal allocation. Next, we remove
   the integrality constraints and insert equality
   constraints (cuts) that force the integer
   variables to assume their optimal values in the
   resulting linear program (LP). We then solve
   the LP to find the associated dual prices on
   the market clearing conditions and added
   equality constraints. These dual (or shadow)
   prices then can be used as prices to support
   a competitive equilibrium. (p271)

I need to implement the addition steps -- namely
the process which adds the cuts and re-solves the
modified problem.

be done on the solver-side.  A new API could be
My first reaction was that this could and should
added, perhaps named:

  'glp_cut_and_price'

Otherwise I guess I can do it on the client side
by traversing the problem and adding additional
constraints to fix the binary variables at their
current values.  I imagine that this is a
straightforward exercise.

Any comments, suggestions, and recommendations
gratefully received.

Finally, O'Neill etal (2002) run through the
history of this particular issue of determining
prices under mixed-integer clearing.

REFERENCES

  O'Neill, Richard P, Paul M Sotkiewicz, Benjamin
      F Hobbs, Michael H Rothkopf, and William R
      Stewart Jr.  2002.  Efficient
      market-clearing prices in markets with
      nonconvexities.  European Journal of
      Operational Research.  v164 no1
      p269-285.  doi:10.1016/j.ejor.2003.12.011

      preprint:
http://www.hks.harvard.edu/hepg/Papers/Oneill.et.al_Efficient.Market.Prices_12-9-02.pdf

---
Robbie Morrison
PhD student -- policy-oriented energy system simulation
Technical University of Berlin (TU-Berlin), Germany
University email (redirected) : address@hidden
Webmail (preferred)           : address@hidden
[from Webmail client]