20.500.12556/RUL-167614 Kombinatorična dražba in linearna optimizacija Combinatorial auction and linear programming 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. 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. linearna optimizacija celoštevilsko programiranje kombinatorična dražba linearna relaksacija razveji in omeji linear optimization integer programming combinatorial auction linear relaxation branch and bound true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2025-03-04 11:25:00 2025-03-04 11:25:07 2025-03-14 11:03:58 0000-00-00 00:00:00 2025 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 37548 229008899 Ambrozic_Maja_-_Kombinatoricna_drazba_in_linearna_optimizacija.pdf Ambrozic_Maja_-_Kombinatoricna_drazba_in_linearna_optimizacija.pdf 1 6644502AA9D627CD16465000BBF5268D 17b6d912128469959348fbfc2d885e903f154d6a2b72b1728fdeeb86c66e3fbe 043fb98d-f8e2-11ef-b232-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=200287 Fakulteta za računalništvo in informatiko 0 0 0