Solving of auctions using branch-and-bound method
| Thesis title: | Řešení aukcí pomocí metody větvení a mezí |
|---|---|
| Author: | Milnerová, Karolína |
| Thesis type: | Bakalářská práce |
| Supervisor: | Fiala, Petr |
| Opponents: | Kobzareva, Maria |
| Thesis language: | Česky |
| Abstract: | V dnešní době si pod pojmem aukce lidé představí dražební místnost a účastníky, kteří navyšují své nabídky, aby získali předměty, které chtěji. Toto je ale pouze jedna z mnoha aukcí, které existují. Cílem této bakalářské práce je seznámit čtenáře s aukcemi, protože jsou dnes velice vyhledávaným řešením pro nákup či prodej zboží. Větší pozornost je kladena na kombinatorické aukce, kde jsou nabízeny tzv. balíčky (kombinace objektů) a kupující mohou vyjádřit své preference ke každému balíčku. Větší část práce je zaměřena na výpočet těchto aukcí. Vzhledem k tomu, že existuje spousta algoritmů, které řeší kombinatorické aukce, bylo téma zúženo pouze na metodu větvení a mezí a její modifikace. Díky tomu jsou vybrány čtyři základní algoritmy -- metoda větvení a mezí, Balasova metoda, Sandholmův IDA* algoritmus a CABOB algoritmus. Jsou použity dva softwary pro řešení příkladů, které reprezentují dva ze zmíněných algoritmů. |
| Keywords: | software CRAB; software Lingo; metoda větvení a mezí; kombinatorická aukce |
| Thesis title: | Solving of auctions using branch-and-bound method |
|---|---|
| Author: | Milnerová, Karolína |
| Thesis type: | Bachelor thesis |
| Supervisor: | Fiala, Petr |
| Opponents: | Kobzareva, Maria |
| Thesis language: | Česky |
| Abstract: | Nowadays, when someone hears the term auction, he imagine is an auction room and participants up their bids to get the items which they want. This is only one of many auctions that exist. The aim of this Bachelor's Thesis is inform the readers with auctions, because they are now very popular solution for buying or selling goods. More attention is paid to the combinatorial auctions where are offered so called bundles (combination of objects) and buyers can express their preference for each bundle. The greater part of work is focused on solving these auctions. In the view of the fact that exist a lot of algorithms that solve combinatorial auctions, the topic was narrowed only to the branch-and-bound method and its modifications. Thanks to this, the four basic algorithms were chosen -- branch-and-bound method, Balas' Method, Sandholm IDA* algorithm and CABOB algorithm. Two solvers are used for solving examples, that represent two of aforementioned algorithms. |
| Keywords: | software CRAB; software Lingo; branch-and-bound method; combinatorial auction |
Information about study
| Study programme: | Kvantitativní metody v ekonomice/Matematické metody v ekonomii |
|---|---|
| Type of study programme: | Bakalářský studijní program |
| Assigned degree: | Bc. |
| Institutions assigning academic degree: | Vysoká škola ekonomická v Praze |
| Faculty: | Faculty of Informatics and Statistics |
| Department: | Department of Econometrics |
Information on submission and defense
| Date of assignment: | 2. 10. 2013 |
|---|---|
| Date of submission: | 1. 5. 2014 |
| Date of defense: | 25. 6. 2014 |
| Identifier in the InSIS system: | https://insis.vse.cz/zp/44387/podrobnosti |