The best algorithm for netting orders

Question

I am creating a market, and I want to create an appropriate mechanism for orders of market participants.

For example, I receive these orders:

A buys 50 B buys 100 C sells 50 D sells 20 

which can be represented as List<Orders> , where Order is a class with Participant , BuySell and Amount

I want to create a Match function that outputs 2 things:

• A set of unsurpassed orders ( List<Order> )
• Set of Agreed Orders ( List<MatchedOrder> where MatchOrder has Buyer , Seller , Amount

The limitation is to minimize the number of orders (unsurpassed and comparable), without leaving a possible coincidence canceled (i.e. at the end there can only be purchase or sale orders that are unparalleled)

So, in the above example, the result will look like this:

 A buys 50 from C B buys 20 from D B buys 80 (outstanding) 

This seems like a pretty complicated writing algorithm, but very common in practice. Any pointers to where to look?

Answer 1

You can model this as a flow problem in a bipartite graph. Each node sale will be on the left, and each node purchase will be on the right. Like this:

Then you should find the maximum amount of stream that you can transfer from source to sink .

You can use any max flow algorithms you want, for example. Ford Fulkerson . To minimize the number of orders, you can use the Maximum Flow / Min Cost algorithm. There are a number of methods for this, including applying round robin after finding a normal MaxFlow solution.

After running the algorithm, you are likely to have a residual network, such as:

Answer 2

• Create a WithRemainingQuantity structure with two members: pointeur o to order and integer to store an unrivaled value
• Consider 2 List<WithRemainingQuantity> , 1 for Bq purchases, 1 for Sq purchases, which are sorted in descending order quantity.
• Algo matches the title of each queue until one of them is empty.

Algo (a mixture of meta and C ++):

 struct WithRemainingQuantity { Order * o; int remainingQty; // initialised with o->getQty } struct MatchedOrder { Order * orderBuy; Order * orderSell; int matchedQty=0; } List<WithRemainingQuantity> Bq; List<WithRemainingQuantity> Sq; /* populate Bq and Sq and sort by quantities descending, this is what guarantees the minimum of matched. */ List<MatchedOrder> l; while( ! Bq.empty && !Sq.empty) { int matchedQty = std::min(Bq.front().remainingQty, Sq.front().remainingQty) l.push_back( MatchedOrder(orderBuy=Bq.front(), sellOrder=Sq.front(), qtyMatched=matchedQty) ) Bq.remainingQty -= matchedQty Sq.remainingQty -= matchedQty if(Bq.remainingQty==0) Bq.pop_front() if(Sq.remainingQty==0) Sq.pop_front() } 

Unsurpassed orders are the remaining orders in Bq or Sq (one of them, if it is deadly empty, according to the while clause).