Kombinatorična dražba in linearna optimizacija

diplomsko delo

Maja Ambrožič (Author), Matjaž Konvalinka (Mentor), Timotej Hrga (Co-mentor)

Abstract

V diplomski nalogi obravnavamo problem kombinatoričnih dražb, pri katerih ponudniki ponujajo sredstva za kombinacije dobrin, namesto samo za posamezne dobrine. Takšne dražbe omogočajo, da ponudniki izrazijo bolj natančna vrednotenja, saj so lahko nekatere dobrine vredne več ali manj v kombinaciji z drugimi. Izračun dodelitve je zaradi eksponentnega števila kombinacij računsko zahteven. V nalogi je predstavljen problem linearnega in celoštevilskega programiranja, ki sta temelj za reševanje problema kombinatoričnih dražb. Poudarek je na formulaciji kombinatorične dražbe kot celoštevilski optimizacijski problem ter analizi različnih algoritmičnih pristopov za premagovanje računske zahtevnosti, kot so požrešni algoritem in metoda razveji in omeji. Prav tako so vključeni praktični primeri za lažje razumevanje problema.

Keywords

linearna optimizacija;celoštevilsko programiranje;kombinatorična dražba;linearna relaksacija;razveji in omeji;računalništvo;matematika;interdisciplinarni študij;univerzitetni študij;diplomske naloge;

Data

Language:	Slovenian
Year of publishing:	2024
Typology:	2.11 - Undergraduate Thesis
Organization:	UL FRI - Faculty of Computer and Information Science
Publisher:	[M. Ambrožič]
UDC:	519.1(043.2)
COBISS:	229008899
Views:	140
Downloads:	30
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Combinatorial auction and linear programming
Secondary abstract:	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.
Secondary keywords:	linear optimization;integer programming;combinatorial auction;linear relaxation;branch and bound;computer science;computer and information science;computer science and mathematics;interdisciplinary studies;diploma;
Type (COBISS):	Bachelor thesis/paper
Study programme:	1000407
Embargo end date (OpenAIRE):	1970-01-01
Thesis comment:	Univ. v Ljubljani, Fak. za računalništvo in informatiko
Pages:	1 spletni vir (1 datoteka PDF (35 str.))
ID:	26010926