Generiranje stupaca podržanim učenjem za problem rezanja

undergraduate thesis

• Title (english): Reinforcement learning column generation for the cutting stock problem
• Author: Ivo Veverec
• Mentor: Mario Brčić (mentor)
• Committee member: Mario Brčić (predsjednik povjerenstva)
• Committee member: Mihael Kovač (član povjerenstva)
• Committee member: Kristijan Poje (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2023-07-07, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

Problem rezanja klasičan je NP-težak problem iz područja kombinatorne optimizacije koji se često formulira kao cjelobrojni linearni program. Generiranje stupaca iterativna je metoda za efikasno rješavanje velikih linearnih programa. U ovom radu koristit će se graf neuronska mreža kojoj je cilj ubrzati metodu generiranju stupaca primjenjenu na problem rezanja. Graf neuronska mreže trenirat će se dubokim Q-učenjem, jednim od algoritama koji spadaju u podržano učenje.

Abstract (english)

Cutting stock problem is a classic NP-hard combinatorial optimization problem which is commonly formulated as an integer linear program. Column generation is an iterative method for efficient solving of large linear programs. In this thesis a graph neural network will be used to speed up the column generation method applied to the cutting stock problem. The graph neural network will be trained using deep Q-learning, a reinforcement learning algorithm.

• Keywords: kombinatorna optimizacija; problem rezanja; podržano učenje; duboko Q-učenje; linearno programiranje; simpleks metoda; generiranje stupaca
• Keywords (english): combinatorial optimization; cutting stock problem; reinforcement learning; deep Q-learning; linear programming; simplex method; column generation
• Language: croatian
• URN:NBN: urn:nbn:hr:168:068673
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2023-07-13 10:38:40