Title Lagrangeova relaksacija u mrežnoj optimizaciji Author Lana Čaldarević Mentor Marko Vrdoljak (mentor)Committee member Marko Vrdoljak (predsjednik povjerenstva)Committee member Franka Miriam Bruckler (član povjerenstva)Committee member Boris Muha (član povjerenstva)Committee member Ozren Perše (član povjerenstva)Granter University of Zagreb Defense date and country 2017-07-17, Croatia Scientific / art field, NATURAL SCIENCES Abstract Lagrangeova relaksacija je fleksibilan pristup rješenju koji omogućuje otkrivanje skrivene mrežne strukture optimizacijskih problema relaksiranjem "kompliciranih" uvjeta. Ovakav pristup omogućuje nam da "rastavimo" model uklanjanjem uvjeta i prebacivanjem tih uvjeta u funkciju cilja sa pridruženim Lagrangeovim multiplikatorom. U ovom radu razradili smo teoriju Lagrangeove relaksacije u linearnom programiranju, opisali smo pristup rješenju te obradili niz problema u kojima Lagrangeova relaksacija efektivno otkriva skrivenu strukturu mreže: problem toka na mreži sa dodatnim uvjetima, problem trgovačkog putnika, problem usmjeravanja vozila, problem dizajniranja mreže i problem rasporeda operatera u dvije smjene. Osnovna teorije Lagrangeove relaksacije je rezultat slabe dualnosti koji govori da je za bilo koju vrijednost Lagrangeovog multiplikatora optimalna vrijednost relaksirane zadaće uvijek ocjena odozdo za vrijednost funkcije cilja originalne zadaće. Kako bismo dobili najbolju moguću ocjenu odozdo, moramo odabrati Lagrangeov multiplikator takav da je optimalna vrijednost Lagrangeove relaksirane zadaće što veća moguća. Tu zadaću zvali smo Lagrangeova dualna zadaća koja se može riješiti na više načina. Metoda subgradijenata, kojom smo se mi bavili, je jedna od najpopularnijih tehnika za rješavanje Lagrangeove dualne zadaće. Za primjene je najznačajniji rezultat jake dualnosti koji govori da se optimalne vrijednosti Lagrangeove dualne zadaće i polazne zadaće podudaraju. Obično odabiremo one uvjete koje relaksiranjem daju Lagrangeovu relaksiranu zadaću koje je puno lakše za riješiti nego originalnu zadaću. Stoga, kod primjene Lagrangeove relaksacije, umjesto da rješavamo jednu "kompliciranu" zadaću, rješavamo više "jednostavnijih" zadaća. Često ti "komplicirani" uvjeti povezuju inače neovisne zadaće, u tim slučajevima, Lagrangeova relaksacija nam dopušta da problem razdvojimo na manje probleme, koje je lakše riješiti. Pokazali smo kako interpretirati problem Lagrangeovih multiplikatora kao "konveksifikaciju" originalnog optimizacijskog problema. Također smo pokazali da kod primjene na probleme cjelobrojnog programiranja, Lagrangeova relaksacije uvijek daje barem jednako dobru ocjenu odozdo kao i relaksirani problem linearnog programiranja u kojem zanemarujemo uvjet cjelobrojnosti. Konačno, pokazali smo da kada Lagrangeova relaksirana zadaća zadovoljava svojstvo cjelobrojnosti (ima cjelobrojna rješenja za svaki izbor Lagrangeovog multiplikatora) te se ocjene odozdo podudaraju. U ovim slučajevima, iako Langrangeov pristup pruža jednake ocjene odozdo kao i relaksirani problem linearnog programiranja, ipak ima kvalitetu bržeg rješavanja problema.
Abstract (english) Lagrangian relaxation is a flexible approach to solutions that enables the detection of hidden network structures of optimization problems by relaxing ”complicated” conditions. This approach allows us to ”break down” the model by removing the conditions and placing them into a target function which we need to optimize with the associated Lagrangian multiplier. In this paper, we elaborated the theory behind Lagrangian relaxation, described solution approaches and looked at several examples in which Lagrangian relaxation effectively reveals the hidden network structure: networks with side constraints, traveling salesman problem, vehicle routing, network design and two-duty operator scheduling. The basic rule of application and the theory of Lagrangian relaxation is weak duality, which says that for any value of Lagrangian multiplier, the optimal value of the relaxed problem is always a lower bound for the value of the target function of original problem which we need to optimize. In order to get the best possible lower bound, we have to choose Lagrangian multiplier such that optimal value of Lagrangian relaxed problem is as large as possible. We call this problem Lagrangian multiplier problem or Lagrangian dual problem and we can solve it in several ways. The subgradient method, that we described in this paper, is one of the most popular techniques for solving Lagrangian dual problem. The most significant result in applications is strong duality which says that the optimal values of Lagrangian dual problem and original problem are equal. Usually, we choose those conditions whose relaxation gives Lagrangian relaxed problem that is much easier to solve than the original problem. Therefore, Lagrangian relaxation allows us to separate the problem into smaller ones, which are easier to solve. We have also shown how to interpret Lagrangian multiplier problem as a convexification of the original optimization problem and we have shown that when applying to the integer programming problems, Lagrangian relaxation always gives at least as large bound as the relaxed linear programming problem. Finally, we demonstrated that when Lagrangian relaxation problem satisfies the integrity property (it has an integer solution for all values of Lagrangian multipliers), solving the Lagrangian multiplier problem is equal to solving the relaxed linear programming problem of the original problem. In these cases, though Lagrangian approach provides the same lower bound as the relaxed linear programming problem, it still has the ability to solve the problem faster.
Keywords
Lagrangeova relaksacija
problem toka na mreži sa dodatnim uvjetima
problem trgovačkog putnika
problem usmjeravanja vozila
problem dizajniranja mreže
problem rasporeda operatera u dvije smjene
Keywords (english)
Lagrangian relaxation
networks with side constraints
traveling salesman problem
vehicle routing
network design
two-duty operator scheduling
Language croatian URN:NBN urn:nbn:hr:217:364957 Study programme Title: Applied Mathematics Type of resource Text File origin Born digital Access conditions Open access Terms of use Created on 2017-12-21 13:38:06
