Ideas for investment algorithm

[tsmbland]

Our investment algorithm often makes decisions that seem illogical in the context of the final system state (e.g. over-capacity or poor choices). The problem is that we appraise each tranche before we know what the final system state is, meaning that we can select assets with low LCOX at the time of appraisal that end up under-utilised or entirely unused in the full system (and hence have a much worse LCOX than first thought). Ideally we want a final state in which all investment decisions appear to "make sense" - no asset/tranche would be better off as a different asset, or better off not existing at all. This is a classic game theory problem.

It may be that reaching a perfect solution is impossible/very difficult, but I think we can do better than what we currently have by making appraisal-time LCOX more accurate, and allowing decisions to be changed retrospectively. I'd suggest the following changes compared to the current approach:

• appraise each asset in the context of the current selection pool. Compared to the current approach, where we only include activity variables for the asset we're currently appraising, we should also include activity variables for all assets the have already been selected, appraising against the full demand profile. This allows newly appraised assets to displace older assets and gives us more accurate LCOX at the time of appraisal. Displacement could happen whenever the currently appraised tranche shares a binding constraint with an already-selected asset (e.g a demand constraint or an activity limit constraint).
• add a reappraisal loop - a second pass over all the tranches in the selection pool to reconsider each decision. For each tranche we reappraise all options against the current selection pool (as above), to get updated LCOX for the original decision and all alternative decisions. We switch our choice if any alternative decision has an LCOX that is better than the original decision (or better by more than epsilon). We can also drop any tranche if doing so does not create unmet demand. This reappraisal loop could be at worst as slow as the first pass (reappraising every tranche), but there are shortcuts (e.g. if one tranche of an asset is not switched, then we don't need to look at further tranches of that asset)
• we can perform the reappraisal loop just once, or perform multiple iterations. If it ever gets to a point where no changes are made, then we've hit convergence (I guess that's a Nash equilibrium, or an approximate equilibrium if epsilon > 0?). It may be that it will never converge (e.g. bouncing between solutions), so better to have a cap on the number of iterations and report whether or not convergence has been reached, or possibly start with a small epsilon and gradually increase.

Pseudocode

Outer loop:
participation loop
loop up to max passes (default = 1):
	reappraisal loop
	if reappraisal loop made no changes
		exit as converged 
	participation loop
exit as pass limit reached (solution is valid but not verified as stable)

Participation loop:
loop while unmet demand
	collect valid tranche options based on caps
	if no valid options
		terminate as infeasible
	appraise each tranche option based on the current selection pool with the tranche added
	add the tranche with the lowest LCOX to the selection pool (ties broken deterministically)
	
Reappraisal loop: 
drop any assets that are entirely unused (i.e. have been entirely displaced)
loop over all remaining assets in the selection pool with >=1 tranche (sorted from worst LCOX to best)
	loop n tranches for that asset (n = tranche count at the start of this asset's turn)	
		remove one tranche of that asset from the selection pool
		if no unmet demand
			mark that a change was made			
			continue (the tranche stays out)
		collect valid tranche options based on caps (including the original decision)
		appraise each tranche option based on the current state with the tranche added
		add the tranche with the lowest LCOX to the selection pool (favouring the current asset unless any other is better by more than epsilon)
		if the best tranche is from the current asset (i.e. decision not changed)
			break (all remaining tranches in this asset would keep too)
		if the best tranche is from a different asset
			mark that a change was made
			continue

Complexity

Participation loop:
- min: O(1)
- max: O(n_tranches * n_options)

Reappraisal loop:
- min: O(n_assets * n_options)
- max: O(n_tranches * n_options)

Total run:
- min: O(n_tranches * n_options)
- max: O(max_passes * n_tranches * n_options)

The current algorithm is O(n_tranches * n_options), so with a low max_passes this is a constant-factor slowdown. If we absolutely want convergence (so set max_passes very high to allow this), then the worst-case slowdown might be a lot worse, but it's difficult to predict.

[ahawkes]

Looks promising @tsmbland! Could end up with bang-bang iteration in the re-appraisal loop?

The improvement to run mini dispatch (for appraisal) with all currently-selected assets will probably improve behaviour already. Maybe implement that, while we think further about re-appraisal?

And write it in a way such that adding the re-appraisal loop is easy...?

I reckon there is no perfect solution here - only Cournot game does what we're after - but is slow and moves away from the fundamental MUSE concept of discrete decision making with differing objectives...

[tsmbland]

The way we have it set up at the moment is that an agent owns a share of demand, and is able to choose between processes to serve that. Moving away from that now - whether its right or wrong - would be a big shift. (though you're right, and it has been noted before).

Ok, but if we're treating agents as players who are able to decide how best to meet their share of the demand, then I don't see why a large optimisation over all options and the total share of demand isn't appropriate? As you've said before, global optimisation will optimise the overall LCOX, but can result in individual assets with poor LCOX, which I understand, but if agents are the players then surely overall LCOX is what they are interested in?

Now, if agents instead represent a collection of players (i.e. firms) each of which has their own incentive (e.g. minimise their own individual LCOX), then asset or tranche-level LCOX seems more important and we come to the kind of game theory conversations we're been having.

I think it's important to raise the distinction and be specific about what we're actually trying to model, even if it's a big shift.

I think the behaviour you describe is roughly what we're after. High CAPEX low OPEX techs take the baseload (high utilisation) and low CAPEX high OPEX take the leftovers. This is how the model is behaving right now, except that it's installing too much capacity of the baseload thing, so utilisation of the wind (in your example) decreases over time (seemingly because a bit too much capacity is added in each year). I am thinking (hoping!) that if the mini dispatch (and thus remaining demand) is estimated using all choices up to that round, the total capacity ultimately installed might not drift upwards (and utilisation downwards) like that. Am I missing something? It's possible this upward drift is caused by something else...

Short answer: I don't think this is a silver bullet, but it probably can't hurt and may help in some cases.

Long answer:

I can easily see how under-utilisation can occur when a high CAPEX/low OPEX tech is selected in later rounds, and then displaces a low CAPEX/high OPEX that was selected before (the latter ending up under-utilised). I don't think the proposal will help with this (without iteration), because in this case it's the early selection rounds that are problematic, and we're not adding any context there (no good knowing what's already been selected if nothing has been yet). I think iteration is the only way here: given that high CAPEX/low OPEX techs are selected later, part of the earlier-selected low CAPEX/high OPEX capacity may no longer be needed as it will always be displaced.

What you're describing is a bit different: high CAPEX/low OPEX techs ending up under-utilised. These cannot be displaced by low CAPEX/high OPEX techs, so I think these could only end up under-utilised if it installs excess capacity compared to overall demand. I think there is a phenomenon, identified previously, where considering each tranche in isolation may not allow for maximally efficient utilisation of activity limits, which can make it think that it needs more than it does. In this case I think considering each tranche in the context of those selected previously probably will help. I just need to work through the nuances (e.g. allowing new tranches to displace old tranches can make new tranches seem feasible even when they add nothing to overall supply - therefore maybe marginal LCOX is a better measure...)

[ahawkes]

Yes, we could have a longer discussion about the principle behind this approach, which would be worthwhile later. But I think it worth getting this version of things working (as best as possible) first - i.e. we are doing the game-theory-like approach where a bunch of competing players are looking at demand and choosing technologies. The players are really technologies here. And we are assuming they don't have access to information on the Cournot solution. Agree its very specific and does not cater for different siutations...but does cater for one.

I can imagine a different objective - optimise LCOX for one agent serving all demand with access to specified processes - which is the global optimisation you're talking about that includes CAPEX etc - could be something we add.

[ahawkes]

@tsmbland implementing the "all my demand" LCOX approach is useful of course. It could be a new objective. We could come up with different names for these objectives. I think that one would be nash_price_taker (i.e. isn't it the same as the nash equilibrium where all processes are price takers anyway). And the current tranche approach is sort of a dumb version of Cournot. Thinking out loud...

[tsmbland]

@ahawkes Could you upload a model that isn't behaving properly with the current approach (excess capacity)?

[ahawkes]

simple_modified.zip

Check utilisation of wind power towards the end of the simulation...