Allocation of resources in the presence of indivisibilities : Scarf’s problem revisited

Working Paper No. 30/04

Allocation of Resources in the Presence of Indivisibilities: Scarf’s Problem Revisited

by

Mette Bjørndal Kurt Jörnsten

SNF Project No. 7165

Long-run Environmetal and Economic Efficiency in Competitive Power Markets:

Optimal Investments in Distributed Generation, Renewables Network Capacity.

The project is financed by Research Council of Norway

INSTITUTE FOR RESEARCH IN ECONOMICS AND BUSINESS ADMINISTRATION BERGEN, JUNE 2004

ISSN 1503-2140

© Dette eksemplar er fremstilt etter avtale med KOPINOR, Stenergate 1, 0050 Oslo.

Allocation of Resources in the Presence of Indivisibilities:

Scarf’s Problem Revisited

Mette Bjørndal Kurt Jörnsten

[email protected] [email protected]

Department of Finance and Management Science

Norwegian School of Economics and Business Administration (NHH) Helleveien 30

N-5045 Bergen Norway (June 2004)

Abstract

In his article “The Allocation of Resources in the Presence of Indivisibilities,” Scarf points out that the major problem presented to economic theory by the presence of indivisibilities is the impossibility of detecting optimality at the level of the firm, or the economy as a whole, using the creation of profitability based on competitive linear prices. In the absence of such competitive prices, Scarf instead introduces a quantity test. Further development of the quantity test idea has lead to algorithms that are used to solve parametric integer programming problems. However, the quantity test is not a fully acceptable replacement of prices to analyse markets with indivisibilities. Recently, O’Neill et al. have suggested a new scheme that generates discriminatory equilibrium prices in markets with non-convexities. In this paper we elaborate this idea even further and use it to generate non-linear price functions that can be interpreted as a non-linear pricing scheme for markets with non-convexities.

Keywords

Pricing, Economics, Integer Programming Duality

1. Introduction

As pointed out by Scarf (1994), “The major problem presented to economic theory by the presence of indivisibilities in production is the impossibility of detecting optimality at the level of the firm, or for the economy as a whole, using the criterion of profitability based on competitive prices” (p. 111). Scarf illustrates the importance of the existence of competitive prices and their use in the economic evaluation of alternatives by considering a hypothetical economic situation, which is in equilibrium in the purest Walrasian sense. It is assumed that the production possibility set exhibits constant returns to scale, implying that there is a profit of zero at the equilibrium prices. Consumers evaluate personal income at these prices and the

market demand functions are obtained by aggregating individual utility maximising demands.

Since the system is assumed to be in equilibrium, the market is clearing, and thus, supply equals demand for each of the goods and services in the economy.

Due to technological advance, a new manufacturing technology has been presented. This activity also possesses constant returns to scale. The question is whether this new activity is to be used at a positive level or not. In this setting, the answer to this question is simple and straightforward: “If the activity is profitable at the old equilibrium prices, then there is a way to use the activity at a positive level so that with suitable income redistributions, the welfare of every member of society will increase.” Moreover, “if the new activity makes a negative profit at the old equilibrium prices, then there is no way in which it can be used to improve the utility of all consumers, even allowing the most extraordinary scheme for income redistribution” (p. 113).

This shows the strength of the pricing test in evaluating alternatives. However, the existence of the pricing test relies on the assumptions made, i.e. that the production possibility set displays constant or decreasing returns to scale. When we have increasing returns to scale, the pricing test for optimality might fail. It is easy to construct an example showing this, for instance by introducing activities with start up costs. In the failure of a pricing test, Scarf introduces as an alternative, a quantity test for optimality. Although elegant, and based on a theory that has lead to the development of algorithms for parametric integer programming problems, we find it hard to believe that the quantity test suggested by Scarf will have the same impact in economic theory as the pricing test has had in the case where non-convexities do not exist.

Over the time, a number of suggestions have been made to address the problem of finding prices for problems with non-convexities, especially for the case where the non-convexities are modelled using discrete variables. The aim has been to find dual prices and interpretations of dual prices in integer programming problems and mixed integer programming problems.

The seminal work of Gomory and Baumol (1960) is addressing this issue. The ideas in the Gomory and Baumol paper was later used to create a duality theory for integer programming problems, and Wolsey’s article from 1981 gives a good description of this theory, that shows that in the integer programming case, we need to expand our view of prices to price functions in order to achieve interpretable and computable duals. However, these dual price functions

are rather complex and other researchers have suggested approximate alternatives. None of these suggestions have so far, to our knowledge, been used successfully to analyze equilibrium prices in markets with non-convexities.

Recently, O’Neill et al. (2001) presented a method for calculating discriminatory prices, IP- prices, based on a reformulation of the non-convex optimization problem. The method is aimed at generating market clearing prices and assumes that the optimal production plan is known. One of the reasons for the renewed interest in obtaining market clearing prices in markets with non-convexities is the deregulation of the electricity markets that has taken place recently. In such markets, the non-convexities arise from start-up and shut-down costs of power plants, as well as minimum output requirements that must be fulfilled in order to run certain plants. In this paper we point out that the IP-prices generated by O’Neill et al. are in fact related to the market clearing non-linear dual price functions that are the basis in integer programming duality.

The paper will be organized as follows. In the next section we present the reformulation rendering IP-prices derived by O’Neill et al. We also state the set of market clearing contracts given by the same authors which together with the IP-prices can be shown to support the equilibrium. We then proceed with a discussion on the relation between O’Neill et al.’s reformulation and the Benders decomposition method. This section also includes some comments on apparent problems that the IP-prices possess and how they can be resolved. We then illustrate our findings using Scarf’s Smokestack, High Tech example, followed by a concluding section.

2. IP-prices and market clearing contracts

In this section, we will present the basic idea of the method suggested by O’Neill et al. (2001) in almost the same setting as is used in their paper. That is, throughout, we will follow the notation used by O’Neill et al., as closely as possible, and then comment on the differences between our approach and theirs.

Assuming that an auctioneer is buying and/or selling a set of goods, with the objective of maximizing the value to the bidders, the auction market can be represented by the mixed integer programming problem (PIP):

Maximize vPIP ⁼

∑

kckxk ⁺

∑

kdkzk

(PIP) Subject to: A₁x A₂z_k b₀

k k

k k k +

∑

≤

∑

k k k k

k x B z b

B ₁ + ₂ ≤ ∀k

≥0

xk ∀k

≥0

zk and integer ∀k

where ,x_k z_k are activities, or column vectors of activities, for participant k in the market, K

k∈ , c_k,d_k are the benefits associated with activities of participant k, A_k1,A_k2,B_k1,B_k2 are matrices of constraint coefficients, b₀ represents the commodities to be auctioned by the auctioneer, and b_k represents the right hand sides of internal constraints of market participant k. The first inequality then represents the market clearing constraint, while the second set of inequalities reflects the restrictions on the operations of each bidder k.

The reformulation that is used by O’Neill et al. is as follows:

Maximize vPIP ⁼

∑

kckxk ⁺

∑

kdkzk

(PLIPz*) Subject to:

∑

_kA_k1x_k +

∑

_kA_k2z_k ≤b₀

k k k k

k x B z b

B ₁ + ₂ ≤ ∀k

≥0

xk ∀k

* k

k z

z = ∀k

where the z_k^* corresponds to the values of the z_k variables in an optimal solution to (PIP).

Note that since the discrete variables in (PIP) have been fixed to their optimal values, the problem stated above is a pure linear programming problem, for which the strong duality theorem holds, and hence, interpretable dual prices exist. The dual to this linear programming problem is:

Minimize _{0 0} ^*_k

k k

k k k

DLIP y b y b w z

v ^{= +}

∑

⁺

∑

(DLIPz*) Subject to: y₀A_k1+y_kB_k1 ≥c_k ∀k

k k k k

k y B w d

A

y_{0 2} + ₂ + ≥ ∀k

0 ≥0 y

≥0

yk ∀k

wk unrestricted ∀k

where, y₀,y_k,w_k are the dual variables for the corresponding primal restrictions in PLIPz*. It is obvious that the optimal objective function values of the three optimization problems stated above are equal, due to the construct and the strong duality theorem.

O’Neill et al. use this to construct a market clearing set of contracts, which according to their definition, is a set of contracts with the following characteristics:

I. Each bidder is in equilibrium, in the sense that given

− the prices y₀^*,y_k^*,w_k^*, i.e. the optimal dual variables to (DLIPz*),

− a payment function defined by the contract, and

− no restrictions on x_k and z_k other than the bidders’ internal constraints,

k k k k

k x B z b

B ₁ + ₂ ≤ , and z_k ≥0 and integer,

no bidder would be able to increase its net benefit, c_kx_k +d_kz_k minus its payment, over that received if x_k = x_k^* and z_k =z_k^*. Thus, the IP-prices support the equilibrium solution

{

x^*k^,z^*k

}

.

II. The contract T_k then specifies the payment between the contracting parties as follows:

Bidder k

− buys (or sells) x_k =x^*_k and z_k = z^*_k

− pays (or receives) an amount to (from) the auctioneer equal to the following payment function: y₀^*(A_k1x_k + A_k2z_k)+w_k^*z_k

By using linear programming duality theory, O’Neill et al. show that the IP-prices and the contracts T_k is a market clearing set of contracts.

3. Relations with Benders decomposition

One of the methods that can be used to solve mixed integer programming problems is the Benders decomposition procedure (Benders (1962)). In this procedure, which, as opposed to

the reformulation used by O’Neill et al., was constructed in order to generate the optimal solution to the mixed integer programming problem in an iterative way, a number of trial solutions z)_k for the integer variables are tested. By solving the remaining linear programming problems with the integer variables fixed to the suggested values, z)_k, a new master problem is derived, which is solved in order to find out if the currently best solution is the optimal solution, or if there might exist a better solution in which the integer variables are fixed to other values than the ones investigated so far.

The Benders sub-problem for the integer values fixed at z)_k is

Maximize _k

k k k k k

PIP c x d z

v ⁼

∑

⁺

∑

)

(BS) Subject to:

∑

_kA_k¹x_k ^≤b^{0 −}

∑

_kA_k²z)_k

k k k k

k x b B z

B )

2

1 ≤ − ∀k

≥0

xk ∀k

with corresponding dual (DBSz)_k):

Minimize vDLIP ⁼ y₀(b₀ ⁻

∑

kAk₂z)k)⁺

∑

kyk(bk ⁻Bk₂z)k)⁺

∑

kdkz)k

(DBSz)_k) Subject to: y₀A_k1+y_kB_k1 ≥c_k

0

0 0

≥

≥ yk

y

Depending on the feasibility of the Benders sub-problem, either an objective function cut or a feasibility cut is generated, using the optimal dual variable values of (DBSz)_k). Here however, we will only be interested in objective function cuts.

If y₀^i*,y_k^i* are the optimal dual variables at iteration i in (DBSz)_kⁱ), the expression

∑

∑

∑

^{+ − +}

− _{k k k k k}ⁱ _{k k k k k k}

i b A z y b B z d z

y₀^*( _{0 2} ) ^*( ₂ ) yields the coefficients in a Benders cut.

The Benders master problem is then

Maximize

[

⁻

_∑

_k ⁺ k ⁻ k k ⁺

_∑

_k k k

]

i k k k i

o

i y (b A z ) y (b B z ) d z

min ^* _{0 2} ^* ₂

Subject to: z_k ≥0 and integer, and feasible in PIP

It is easy to see the resemblance between the dual of the Benders sub-problem (DBS) and the dual of the reformulated problem (DLIPz*). In fact, the IP-prices are nothing but the prices generated in the dual of the Benders sub-problem (DBS), for the trial solution fixed to the optimal solution, i.e. z_k =z_k^*.

The IP-prices generated in (DLIPz*) however, have some unwanted properties. For some demand realizations the mixed integer program in itself can have the integrality property, hence the problem (PIP) could have been solved as a linear program and the linear programming dual prices will support the equilibrium. In the dual (DLIPz*) this means that we have a set of alternative dual solutions, all of which support the equilibrium. This is fine and is as expected and as wanted. However, for some other demand realizations in which the units are used at full capacity, the dual (DLIPz*) also have alternative dual solutions, but the corresponding mixed integer program (PIP) is not solvable as a linear program and can in fact have a substantial duality gap. In these cases the linear price system is not a true supporting price system for (PIP) and should not be used. These effects are illustrated using Scarf’s example in the next section.

Another, and as we see it, even more problematic property is the fact that the IP-prices can show a rather erratic behaviour for marginal changes in demand. Hogan and Ring (2003) observed this phenomenon and suggested the use of minimum uplift charges as an alternative.

A more thorough analysis of the minimum uplift charges, versus the modified IP-prices, can be found in Bjørndal and Jörnsten (2004).

The reason for the erratic behaviour is that for some demand realizations some of the coefficients in the Benders cuts are negative, whereas for others they are positive. The effect of this is that the total start up charges or uplifts change from being a positive charge to a negative charge with the effect that the product prices y^*₀ varies dramatically and shows an erratic behaviour. The effect of this erratic behaviour is two-folded. First, it creates situations in which a redistribution of costs and benefits are made due to a small change in demand

realization, and second, due to the erratic behaviour of product prices, the market participants can start questioning the market’s efficiency and require changes in the market design.

So, is there a way to generate equilibrium IP-prices that does not possess the unwanted properties mentioned above? Returning to the relation between the dual prices generated by the Benders sub-problem for the complicating variables fixed to their optimal values, and the IP-prices generated by the reformulation (PLIPz*), the question stated above can be rephrased as the following: Does the coefficient in the Benders cut generated when the complicating variables are fixed to their optimal values z* yield a valid inequality for the original problem (PIP)? If this is the case, the generated IP-prices support the equilibrium by a valid inequality that supports the optimal solution. Hence, these IP-prices are in fact prices that are associated with a non-linear non-discriminatory price function. Hence, they will not show the same erratic behaviour as the IP-prices used by O’Neill et al.

Unfortunately, this is not always the case, though for the Scarf example, which is explained in detail in the next section, it is true for the demand levels used in the illustration. However, the following single commodity example, which is a minor extension to the Scarf example, adding a third production technology, with a capacity of 6, fixed cost of 2 and a marginal cost of 7 per unit produced, illustrates this.

Minimize 53z₁ +30z₂ +2z₃ +3q₁+2q₂ +7q₃ Subject to: q₁+q₂ +q₃ ≥ D

0 16z₁−q₁ ≥

0 7z₂ −q₂ ≥

0 6z₃ −q₃ ≥

0 , , _{2 3}

1 q q ≥

q

0 , , _{2 3}

1 z z ≥

z and integer

For demand, D, equal to 55 the optimal solution is z₁=3,

z

₂=1 and z₃=0. For this demand level, the reformulation gives IP-prices of 53 and 23 for z₁ and

z

₂ respectively, and the commodity price is 3. However, for demand equal to 56, the optimal solution is z₁=3,

z

₂=1

and z₃=1, with q₃=1. Here, the reformulation (PIPz*) gives a commodity price of 7, and IP prices -11, -5 and 2 respectively, for z₁, z₂, and z₃. This illustrates that a marginal change in demand realization and optimal solution can yield dramatic changes in commodity prices and IP-prices. The example above also illustrates what may happen if you have a so called

“hockey-stick” bidder in an electricity market, and where the market design is such that the market price is set by the active producer having the highest marginal cost (Oren (2003)).

How can we avoid this? The difference between the two demand levels in the example is that for demand D = 55 the IP-prices yield coefficients for the integer variables that are part of a valid inequality for (PIP) whereas for D = 56 this is not the case. This is obvious for D = 56 since adding an extra production facility of type 1 or type 2 gives another feasible solution but the constraint −11z₁−5z₂ +2z₃ ≥−36 is not satisfied for z₁ =4, z₂ =1 and z₃ =0, which of course is a feasible solution to the problem, with a lot of excess capacity. So is there some way to generate IP-prices that are supported by a valid inequality?

Returning to the Benders decomposition analogy, the Benders decomposition procedure was developed in order to create a solution method for mixed integer programming problems. If this is the purpose, it is clear that only the integer variables create complications, since if the optimal values of these variables were known, an easy linear programming problem is all that remains to be solved. However, when the purpose is to generate equilibrium supporting market clearing prices, some of the continuous variables may create complications due to the structure of the problem. In the example above, it is the production variable q₃ that should be regarded as complicating. If we in the reformulation for the demands D = 55 and D = 56, fix the four variables z₁,z₂,z₃ and q₃ to their optimal values and solve the reformulated problem, the IP prices generated will be 53, 23, 2, and 4 respectively, and the commodity price will be equal to 3 for both demand realizations.

Also, the inequality 53z₁+23z₂ +2z₃ +4q₃ ≥182 is a valid inequality for the problem with D = 55, and the inequality 53z₁+23z₂ +2z₃ +4q₃ ≥188 is a valid inequality for D = 56.

The upfront payment of 4q₃ that producer 3 gets for producing q₃ can be viewed as a mean that the auctioneer or market maker takes in order to avoid that the customers are questioning

the market design or market efficiency caused by the non-convexities. It may be used to avoid that a “hockey-stick” bidder can create a total redistribution among the participants in the market. Alternatively, we can regard this upfront payment as a subsidy that is used to make up for the erratic effect caused by the non-convexities upon the commodity prices. We will not expand on this here, but the topic is developed further in a companion paper (Bjørndal and Jørnsten (2004)).

To conclude, when using the reformulation idea for pricing in general mixed integer programming problems, it might be necessary to classify not only the integer variables as complicating, but in addition, some of the continuous variables can create pricing complications. It can also be true that only a part of the integer variables are pricing complicating variables, together with some of the continuous variables. Note that, as in standard linear programming, where complete decentralization cannot be achieved with prices only due to constant marginal costs, the same result is valid for linear mixed integer programs with modified IP-prices or non-linear price functions.

4. Scarf’s example

To illustrate the generation of the nonlinear price functions, we use Scarf’s original example (Scarf (1994)). The example consists of two technologies, Smokestack and High Tech, with the following production characteristics:

Smokestack High Tech

Capacity 16 7

Construction Cost 53 30

Marginal Cost 3 2

Average Cost 6.3125 6.2857

We can formulate Scarf’s allocation problem as a mixed integer programming problem (P) as follows:

Minimize 53z₁+30z₂ +3q₁ +2q₂ (P) Subject to: q₁+q₂ ≥D

0 16z₁−q₁ ≥

0 7z₂ −q₂ ≥

0 , ₂

1 q ≥

q

0 , ₂

1 z ≥

z and integer

Parameter D is the demand, while the construction variables for Smokestack and High Tech are z₁ and z₂ respectively. Variables q₁ and q₂ denote the level of production. Note, that for fixed integer values of z₁ and z₂, the remaining problem in the continuous variables have the integrality property. Hence, Scarf’s allocation problem is in fact a pure integer programming problem. The reason for this is the special form of the constraint matrix for this example.

Using O’Neill et al.’s reformulation of the problem, we get (P1):

Minimize 53z₁+30z₂ +3q₁ +2q₂ (P1) Subject to: q₁+q₂ ≥D

0 16z₁−q₁ ≥

0 7z₂−q₂ ≥

* 1

1 z

z =

* 2

2 z

z = 0 , ₂

1 q ≥

q

0 , ₂

1 z ≥

z and integer

where z₁^* and z^*₂ are the optimal integer solutions for the specified demand D. In the range 55 to 70, the following discriminatory prices are generated:

Smokestack High Tech

Commodity Price Start up price Capacity price Start up price Capacity price

3 53 0 23 -1

The start up prices of 53 and 23 are the dual variables associated with the two constraints

* 1

1 z

z = and z₂ = z^*₂, respectively. Likewise, the commodity price is the dual variable of the market clearing requirement, while the capacity prices are the duals of the capacity constraints.

The constraint 53z₁+23z₂ ≥L_i is a valid inequality for the integer programming problem (P), where L_i denotes the right hand side constant for demand i; i = 55,…,70. The L_is for problem (P) with i = 55,…,70 are 182, 184, 191, 191, 198, 198, 205, 205, 207, 212, 214, 221,

221, 228, 228 and 230. To prove this, we just have to solve the mixed integer programming problem

Minimize 53z₁+23z₂ Subject to: q₁+q₂ ≥D

0 16z₁−q₁ ≥

0 7z₂ −q₂ ≥

0 , ₂

1 q ≥

q

0 , ₂

1 z ≥

z and integer

which for D = 55,….,70 has the optimal objective function values listed above.

Note that O’Neill et al. present alternative dual solutions for the demand values 55, 56, 58, 60, 62, 63, 64, 65, 67, 69 and 70, which are caused by the fact that the revised problem (P1) has alternative optimal dual solutions for these values of demand. The reason for this is that for these demand values, the capacities for the used technologies are fully utilized. These alternative dual solutions are however not compatible with prices for the integer programming problem (P) except for demands 56, 63 and 70, for which the linear programming relaxation is integer valued. For these three demand values a linear price of 6.2857 and capacity prices of 3.2857 and 4.2857 supports the equilibrium. For all other demand values, the existence of alternative dual solutions is just a mirage created by the way problem (P1) is constructed. This can be easily seen by solving the linear programming relaxation of (P) for these demand values, which show that there is a substantial duality gap, hence the alternative dual solutions does not yield competitive prices for the integer programming allocation problem.

Knowing that the inequalities are valid inequalities for problem (P), that when added to the problem (P), generates the optimal objective function value and the correct commodity price of 3, points out a way to generate a non-linear price function that supports the optimal resource allocation and hence, provides a set of competitive non-linear prices. A non-linear price-function can be derived using cutting planes. As opposed to when cutting plane approaches are used to generate the integer valued optimal solution, we only need to find out how the supporting inequality, 53z₁+23z₂ ≥L_i, can be generated from the problem’s original inequalities, hence, we know exactly what we are looking for. Also, the resulting linear

program with these inequalities appended, does not need to be integer valued, since we are only interested in generating the commodity price and the non-linear price function that supports the start up charges.

In order to derive the price functions for Scarf’s example, we first add the three original constraints. This gives us a capacity constraint (CAP) that says that in order to be able to fulfil the demand we need to have enough production capacity installed. The constraint (CAP) is thus

(CAP) 16z₁ +7z₂ ≥D

Multiplying the constraint (CAP) with 1/7 and rounding the fractional values up to the nearest integer, yields the valid inequality:

(VI1) 3z1 +z2 ≥

⎡ ⎤

^D7

Multiplying (CAP) with 32, adding 6 times (VI1), dividing the result by 10, and performing the rounding up operation, yields the inequality

(VI2) 53z₁ +23z₂ ≥ ^{⎡ ⎤}⎥⎥⎤

⎢⎢⎡ ⁺

10 6

32 7

D D

This gives us a non-discriminatory non-linear price-function

(I)

⎥⎥

⎥

⎤

⎢⎢

⎢

=⎡³² ₁₀^{+6⎢⎢⎡ 7 ⎥⎥⎤} )

(

CAPj

CAPj

CAPj

F

where CAP_jdenotes the coefficient of z_j in the constraint (CAP). This non-linear function is optimal for the demand values 56, 58, 60, 63, 65, 67 and 70, since for these instances, the original problem (P) with the inequality (VI2) appended, gives the optimal objective function value and a dual variable value of 1 for the constraint, together with the correct commodity price 3, and capacity charges 0 and -1, respectively.

For the remaining demand values, a non-linear function that is a little bit more complicated is needed. This function is generated by noting that if we add the two last generated constraints (VI1) and (VI2), and divide the result by 8, we get the valid inequality:

(VI3) 7z₁ +3z₂ ≥

⎡ ⎤

⎥⎥

⎥⎥

⎥

⎤

⎢⎢

⎢⎢

⎢

⎡ ⎥⎥⎤

⎢⎢⎡

⎥⎥+

⎢⎢ ⎤

⎡ ⁺ 8

10 7

6

32^D 7^D D

Moreover, the constraint

(VI4) 2z₁ +1z₂ ≥ ⎥⎥⎤

⎢⎢⎡ 8 D

can be derived from the capacity constraint by dividing by 8 and rounding up to the nearest integer. These two constraints are enough to support the equilibrium prices for the remaining demand levels. In this case the non-discriminatory non-linear price-function gets the form

(II) 2

8 7 7

) (

10 6

32 7

+

⎥⎥

⎥⎥

⎥

⎥

⎤

⎢⎢

⎢⎢

⎢

⎢

⎡ ⎥

⎥

⎢ ⎤

⎢ +⎡

⎥⎥

⎥

⎤

⎢⎢

⎢

⎡

=

⎥⎥⎤

⎢⎢⎡

+ j

CAP

j

CAP CAP

F

CAPj j

⎥⎥

⎢ ⎤

⎢

⎡ 8 CAPj

Hence, for the Scarf example with demand levels ranging from 55 to 70, the supporting market equilibrium prices are given by the linear commodity price of 3, independent of the demand level in this interval, and the start up charge is given by one of the two non-linear price-functions, giving us a non-linear pricing mechanism that supports the equilibrium.

The tables below present the results for Scarf’s example:

Demand Number of Number of Production Production Total Cost Smokestack High Tech in Smokestack in High Tech

55 3 1 48 7 347 56 0 8 0 56 352 57 1 6 15 42 362 58 1 6 16 42 365 59 2 4 31 28 375 60 3 4 32 28 378 61 3 2 47 14 388 62 3 2 48 14 391 63 0 9 0 63 396 64 4 0 64 0 404 65 1 7 16 49 409 66 2 5 31 35 419 67 2 5 32 35 422 68 3 3 47 21 432 69 3 3 48 21 435 70 0 10 0 70 440

Demand Commodity Total Uplift Total Supporting Nonlinear Price Cost Commodity Cost Price Function

55 3 182 165 II 56 3 184 168 I 57 3 191 171 II 58 3 191 174 I and II 59 3 198 177 II 60 3 198 180 I and II 61 3 205 183 II 62 3 205 186 II 63 3 207 189 I 64 3 212 192 II 65 3 214 195 I and II 66 3 221 198 II 67 3 221 201 I and II 68 3 228 204 II 69 3 228 207 II 70 3 230 210 I

5. Conclusions and issues for future research

In this paper, we have shown that the IP-prices, generated by the use of the reformulation of O’Neill et al. (2001), can give information that can be used to generate a supporting valid inequality to the resource allocation optimization problem. In general, this is not true, but an alternative reformulation can then be used to achieving this. Knowing the coefficients of a supporting valid inequality means that we know that there exists a non-discriminatory non- linear price-function that, together with the affine capacity and product prices, yields

equilibrium prices in markets with non-convexities. Also, knowing the coefficients of the supporting valid inequality makes it easier to construct the non-linear price-function as compared with the case where these coefficients are unknown. The results can be used to motivate the use of the IP-prices suggested by O’Neill et al., or a modified version of IP- prices, knowing that although they seem to be discriminatory they can also be viewed as a compact representation of the supporting non-linear price-function and hence, are in fact non- discriminatory. If this knowledge should be used to redesign the contract suggested by O’Neill et al., or just to motivate it, remains to be investigated.

Other research questions that should be addressed are how elastic demand can be incorporated in markets with non-convexities. If and how the uplift charges should be collected among the customers, and how this cost allocation should influence the design of market clearing contracts, are other issues. Another question is whether it is satisfactory just to have a theoretical foundation for the use of modified IP-prices, or if procedures that actually generate a corresponding non-discriminatory price-function need to be further investigated. Finally, the incentives for the market participants in markets with both linear commodity charges and uplift payments have to be studied.

References

Alcaly, R.E., Klevorick, A.K., 1966. A Note on the Dual Prices of Integer Programs, Econometrica 34 (1) 206-214.

Benders, J.F., 1962. Partitioning Procedures for Solving Mixed-Variables Programming Problems, Numerische Mathematik 4 238-252.

Bjørndal M., Jørnsten K., 2004. Equilibrium Prices Supported by Dual Price Functions in Markets with Non-Convexities, Working Paper, Department of Finance and Management Science, Norwegian School of Economics and Business Administration.

Gomory, R.E., Baumol, W.J., 1960. Integer Programming and Pricing, Econometrica 28 (3) 521-550.

Hogan, W.W., Ring B.J., 2003. On Minimum-Uplift Pricing for Electricity Markets, Working Paper, John F. Kennedy School of Government, Harvard University.

O’Neill, R.P., Sotkiewicz, P.M., Hobbs, B.F., Rothkopf M.H., Stewart, Jr., W.R., 2001.

Equilibrium in Markets with Nonconvexities, Working Paper 2001 (Forthcoming in European Journal of Operational Research).

Oren, S., 2003. Paper presented at The Arne Ryde Symposium on the Nordic Electricity Market.

Scarf, H.E., 1990. Mathematical Programming and Economic Theory, Operations Research 38 (3) 377-385.

Scarf, H.E., 1994. The Allocation of Resources in the Presence of Indivisibilities, Journal of Economic Perspectives 8 (4) 111-128.

Sturmfels, B., 2003. Algebraic Recipes for Integer Programming, Proceedings of Symposia in Applied Mathematics.

Williams, H.P., 1996. Duality in Mathematics and Linear and Integer Programming, Journal of Optimization Theory and Applications 90 (2) 257-278.

Wolsey, L.A., 1981. Integer Programming Duality: Price Functions and Sensitivity Analysis, Mathematical Programming 20 173-195.