Egzaktno rješavanje problema cjelobrojnog linearnog programiranja

master's thesis

• Title (english): Exact solution of integer linear programming problems
• Author: Nikolina Križaić
• Mentor: Robert Manger (mentor)
• Committee member: Robert Manger (predsjednik povjerenstva)
• Committee member: Eduard Marušić-Paloka (član povjerenstva)
• Committee member: Matej Mihelčić (član povjerenstva)
• Committee member: Dijana Ilišević (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2023-11-30, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

Cjelobrojno linearno programiranje se bavi problemom optimizacije gdje su funkcija cilja i ograničenja linearni, a neke od varijabli odlučivanja su cjelobrojne. Najpoznatije metode za egzaktno rješavanje ovakvih problema su branch-and-bound odnosno cutting-plane metoda. U ovom radu veći je naglasak na metodi branch-and-bound. U prvom poglavlju upoznali smo se osnovnim pojmovima iz teorije grafova koje su nam potrebne za razumijevanje modela pojedinih problema. U drugom, trećem i četvrtom poglavlju upoznali smo se s poznatim problemima cjelobrojnog linearnog programiranja: problemom naprtnjače, problemom dodjeljivanja te problemom trgovačkog putnika. U petom poglavlju opisali smo branch-and-bound algoritam te smo riješili jednostavan problem naprtnjače tom metodom. U šestom i sedmom poglavlju smo se upoznali s teorije grafovaom te smo implementirali rješenje za problem trgovačkog putnika koristeći Gurobi softver.

Abstract (english)

Integer linear programming deals with optimization problems where the objective function and constraints are linear and some decision variables are integers. The most common exact methods for solving such problems include the branch-and-bound method and the cutting plane method. In this work, there is more emphasis on the branch-and-bound method. In the first chapter, we have introduced some to basic concepts from graph theory that we need to understand the models of certain problems. In the second, third and fourth chapters, we have introduced the well-known integer linear programming problems: the knapsack problem, the assignment problem and the traveling salesman problem. In the fifth chapter, we have described the branch-and-bound algorithm and solved a simple knapsack problem with that method. In the sixth and seventh chapters, we have got acquainted with the Gurobi software and implemented a solution to the traveling salesman problem using the Gurobi software.

• Keywords: branch-and-bound metoda; cutting-plane metoda; teorija grafova; teorija grafova
• Keywords (english): branch-and-bound method; cutting plane method; graph theory; Gurobi software
• Language: croatian
• URN:NBN: urn:nbn:hr:217:597108
• Study programme: Title: Mathematical Statistics; Study programme type: university; Study level: graduate; Academic / professional title: sveučilišni magistar matematike (sveučilišni magistar matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2024-02-12 13:01:00