Miglior algoritmo per ordini di compensazione

Question

Sto costruendo un mercato e voglio creare un meccanismo di corrispondenza per gli ordini dei partecipanti al mercato.

Per esempio ricevo questi ordini:

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

che può essere rappresentato come un List<Orders>, dove Order è una classe con Participant, BuySell, e Amount

Voglio creare una funzione Match, che emette 2 elementi:

1. Un set di unmatche d ordini (List<Order>)
2. Un insieme di ordini abbinati (List<MatchedOrder> dove MatchOrder ha Buyer, Seller, Amount

Il vincolo è quello di ridurre al minimo il numero di ordini (accoppiati e non accoppiati), mentre non lasciando possibile corrispondenza annullata (vale a dire, alla fine, non ci può essere solo acquistare o vendere gli ordini che sono senza pari)

Quindi, nell'esempio sopra il risultato sarebbe:

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

Questo sembra un algoritmo abbastanza complesso da scrivere ma molto comune nella pratica. Qualche suggerimento su dove guardare?

Answer 1

È possibile modellarlo come un problema di flusso in un grafico bipartito. Ogni nodo di vendita sarà sulla sinistra e ogni nodo di acquisto sarà sulla destra. Come questo:

Poi si deve trovare la massima quantità di flusso si può passare da source a sink.

È possibile utilizzare qualsiasi algoritmo di flusso massimo desiderato, ad es. Ford Fulkerson. Per ridurre al minimo il numero di ordini, è possibile utilizzare un algoritmo Massimo flusso/Minimo costo. Ci sono un certo numero di tecniche per farlo, inclusa l'applicazione del ciclo di annullamento dopo aver trovato una normale soluzione MaxFlow.

Dopo aver eseguito l'algoritmo, probabilmente dispone di una rete residua simile al seguente:

Answer 2

1. creare una struttura WithRemainingQuantity con 2 membri: un pointeur o ad un ordine e un numero intero a memorizzare la quantità non corrispondente
2. Considerare 2 List<WithRemainingQuantity>, 1 per gli acquisti Bq, 1 per vendite Sq, entrambi ordinati per quantità decrescenti dell'ordine contenuto.
3. l'algo corrisponde al capo di ciascuna coda fino a quando uno di loro è vuota

Algo (mix di metal e 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() 
} 

Gli ordini senza eguali sono i rimanenti ordini in Bq o Sq (uno di essi se fatalmente vuoto, secondo la clausola while).