j-ti
commented
6 months ago Additional test cherry picked in test/best_matching (while rebasing this branch deleting 73f3084..beb8ea6 )
Closed PaulScheerRLI closed 6 months ago
j-ti
commented
6 months ago Additional test cherry picked in test/best_matching (while rebasing this branch deleting 73f3084..beb8ea6 )
Fixes best matching problems by using a completely new method for finding matches. The new algorithm introduces a new class, the BestCluster which implements necessary functionality and allows for more or less a readable algorithm. It performs slightly faster than the old algorithm in case of using "grid_fee" for disputed values. Using "bid_price" is not optimized yet and therefore can take much longer. The biggest advantage towards the old algorithm is, that the produced matches follow, from my perspective, the mandatory condition of being at least local optima for each ask. This means a single ask could not be placed differently to achieve a higher profit for the ask_actor. This leads to the side condition of clearing prices which are at an equilibrium between clusters, with an offset of the grid fee in between, and some differences due to the discrete nature of single orders and prices.
The basic steps of the algorithm are
Local Matching without restrictions For each known cluster a BestCluster is generated. A BestCluster consists of all Bids of this cluster, e.g. the bids are unique. During local matching without restrictions all asks are used to match these local bids. From this a clearing price and an amount of matched energy arise. If the matched energy at this point is zero, the cluster can be discarded, since coming restrictions wont make it easier to match in this cluster.
Single Loop Needle Work through all asks The algorithm iterates over the clusters and takes the lowest ask of this cluster. This ask is found in every other clusters and profits as well as the disputed value is used to determine the best cluster for the ask to stay in. the ask is deleted from the other clusters, e.g. cluster which are not the best cluster. this continues until every cluster checked its lowest ask. After that a new loop starts with the second lowest ask and so on. Each cluster checks its own asks once or less. Less in the case that another cluster determined the ask should be deleted from this cluster. 2 clusters might check the same ask in case of the first cluster not being the best cluster, therefore deleting the ask from its own cluster, and then the best cluster checking the ask again to determine, the ask should remain in the current cluster. A previous bottleneck of deleting the asks from the panda dataframe was negated by using a cluster dependent index instead. therefore, the dataframe has to be mutated only once at the end. The following picture describes how the algorithm works
Iterative profit optimized matching The last step of the algorithm is iterative and takes care of changed clearing price conditions during the single loop. During the above loop each asks stays in at the moment, optimal cluster. This might not be the optimal cluster at the end of the loop. Therefore, the cheapest asks per cluster get the possibility of changing clusters to a more optimal / profitable cluster. This leads to changes in other clusters which can cascade during runtime, with no upper bound. This means that badly defined dispute values or other problems might lead to a not exit-able while loop. A check for convergence might make sense at this point. The loop exits when no ask can change clusters with making a profit. This happens when connected clusters are closest to an equilibrium-price.
Further Task before merge Coding
Misc
The code was optimized for the case of using "grid_fee" as disputed value, e.g. in case of the same profit, the cluster is chosen which has the lower grid fee. the bid_price dispute might be further optimized and is by far the most time-consuming step. To determine which function is dominant for computational time, the time_it fixture is used. Removing it would make sense before merging.
An optimally solved market can be seen here. The grid fees between cluster are minimal with 0.01. Every Cluster consists of unique prices. Prices are chosen to be identical with the actor name e.g. the actor 0.8 has an order price of 0.8 Cluster 0 has asks prices ending on 0.8 and bid prices ending on .666 Cluster 0has the lowest bids and the highest asks of all clusters Cluster 1 has asks ending on 0.4 and bids ending on .333 Cluster 2 has the lowest asks and the highest bids. The result is that cluster 0 matches 11 energy units, cluster 1 matches 12 and cluster 2 matches 14 energy units. The clearing prices are as similar as the discrete bidding prices allowed with 10.8, 10.6, and 11.4. The asks are not entirly matched in their own cluster
This scenario can be compared with heavy grid fees of 15 between clusters. The result is less matched energy with 10, 12 and 13 for cluster 0, 1 and 2 and clearing prices of 9.8, 10.6, 11.4
handle market maker Right now the market maker is not handled by the best algorithm. My proposal would be Check orders if MarketMaker orders exists. If MarketMaker orders exists, filter orders which dont meet MarketMaker requirements, e.g. buys which are less expensive than the market maker buy, will not be matched. Other way around for sells (Actors won't buy energy from another actor, if the marketmaker sells the energy for a lower price) Reduce MarketMaker amounts to the the amounts of all other orders MarketMaker ask amount is high enough to meet all bids of actors MarketMaker bid amount is high enough to meet all asks of actors. Match orders the same way as described above.
slow bid_price disputes Right now the bid_price dispute is solved lazily, which made it less error prone but also slow. Right now the ask is inserted into the asks, the asks are sorted, the position of the ask is found, read, and returned to look up the corresponding bid_price. Since the insertion should not be permanent, the work is done on a copy. A much more efficient way of doing that would involve.