In this thesis, we address the problem of combinatorial auctions, where bidders place bids for combinations of goods, instead of only for individual goods. Such auctions allow bidders to express more precise valuations for goods, since some of the items may be more or less valuable together. The calculation of the allocation becomes computationally challenging due to the exponential number of combinations of goods. The thesis presents the problem of linear and integer programming, which form the basis for solving the combinatorial auction problem. The main focus is on the formulation of combinatorial auctions as integer optimization problems and the analysis of different algorithmic approaches to overcome the computational complexity, such as the greedy algorithm and the branch and bound method. Practical examples are also included to enhance understanding of the problem.
|
