Combination Order Matching

No Thumbnail Available
Journal Title
Journal ISSN
Volume Title
Helsinki University of Technology | Diplomityö
Checking the digitized thesis and permission for publishing
Instructions for the author
Date
1999
Major/Subject
Ohjelmistotekniikka
Mcode
Tik-106
Degree programme
Language
fi
Pages
82
Series
Abstract
Johdannaispörssin yhdistelmätarjous on usean tarjouksen joukko, jota käsitellään jakamattomana kokonaisuutena. Joukon yksittäisillä tarjouksilla ei ole omaa hintaa, vaan yhdistelmätarjouksella on yksi hinta. Tarjouskirja on yhdistelmätarjousten joukko. Kauppojen automaattitäsmäytys, toisensa kohtaavien osto- ja myyntitarjousten etsiminen, voidaan suorittaa kaupan määritelmän täyttävän alijoukon hakuna tarjouskirjasta. Tämä haku on luonteeltaan kombinatorinen optimointitehtävä, jossa pyritään optimoimaan löydetyn kaupan tarjouksien hintojen summaa. Optimointitehtävän ratkaisumenetelmäehdokkaita ovat minimikustannusvirtaus, kokonaislukuohjelmointi ja rajoiteohjelmointi. Tässä työssä kuvataan ongelman ratkaisemista jokaisella näistä algoritmiehdokkaista. Todetaan, että tarjousten täsmäytysongelma on hyvin lähellä yleisesti tunnettuja minimikustannusvirtaus- ja paritusongelmia, jotka ratkeavat polynomisessa ajassa. Täsmäytysongelmassa joudutaan kuitenkin käyttämään hieman erilaisia rajoitteita kuin virtausongelmissa, eikä sille niiden takia voida soveltaa erikoistapauksiin viritettyjä virtausalgoritmeja. Kokonaislukuohjelmointi otetaan lähempään tarkasteluun. Todetaan, että tarjousten täsmäytys on sillä ratkaistavissa ilman tarjousten monimuotoisuuden rajoittamista Suomen kokoisilla markkinoilla.
Description
Supervisor
Nurmi, Otto
Thesis advisor
Kyhälä, Ari
Keywords
kombinatorinen optimointi, virtausalgoritmi, kokonaislukuohjelmointi, johdannaispörssi, combinatorial optimization, integer programming, network flow, derivative exchange
Other note
Citation