Kombinatorična dražba in linearna optimizacija

diplomsko delo

Maja Ambrožič (Avtor), Matjaž Konvalinka (Mentor), Timotej Hrga (Komentor)

Povzetek

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.

Ključne besede

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

Podatki

Jezik:	Slovenski jezik
Leto izida:	2024
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UL FRI - Fakulteta za računalništvo in informatiko
Založnik:	[M. Ambrožič]
UDK:	519.1(043.2)
COBISS:	229008899
Št. ogledov:	140
Št. prenosov:	30
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Combinatorial auction and linear programming
Sekundarni povzetek:	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.
Sekundarne ključne besede:	linear optimization;integer programming;combinatorial auction;linear relaxation;branch and bound;computer science;computer and information science;computer science and mathematics;interdisciplinary studies;diploma;
Vrsta dela (COBISS):	Diplomsko delo/naloga
Študijski program:	1000407
Konec prepovedi (OpenAIRE):	1970-01-01
Komentar na gradivo:	Univ. v Ljubljani, Fak. za računalništvo in informatiko
Strani:	1 spletni vir (1 datoteka PDF (35 str.))
ID:	26010926