ETD

Digital archive of theses discussed at the University of Pisa

 

Thesis etd-05072019-091549


Thesis type
Tesi di laurea magistrale
Author
CACCIOLA, MATTEO
URN
etd-05072019-091549
Thesis title
A Lagrangian approach to a problem with probailistic constraints
Department
MATEMATICA
Course of study
MATEMATICA
Supervisors
relatore Prof. Frangioni, Antonio
controrelatore Galli, Laura
Keywords
  • Optimization
  • Lagrangian relaxation
  • Indusrty 4.0
  • Probailistic constraints
Graduation session start date
07/06/2019
Availability
Full
Summary
Nel lavoro vengono sviluppati approcci algoritmici per un modello di Programmazione Non Lineare Mista Intera (MINLP) non-convesso altamente sfidante per un problema di routing con vincoli probabilistici su reti wireless relativo ad un'applicazione IoT, che non può essere risolto all'ottimo con gli strumenti general-purpose attualmente disponibili. Per tale modello viene proposto un innovativo approccio Lagrangiano in grado di calcolare valutazioni inferiori sul valore ottimo del problema in questione mediante la soluzione di problemi non-convessi mono-dimensionali, che vengono dimostrati essere unimodali e quindi risolti efficientemente con tecniche del secondo ordine. Le valutazioni inferiori così ottenute sono sfruttate anche per la costruzione di euristiche Lagrangiane, che in alcuni casi si sono mostrate più efficaci delle migliori euristiche attualmente disponibili. Le metodologie sviluppate permetteranno in futuro l'implementazione di un algoritmo di enumerazione implicita (Branch and Bound) che potrebbe permettere di determinare soluzioni ottime per il problema.
File