Decomposition Methods and Network Design Problems

Decomposition based approaches are recalled from primal and dual point of view. The possibility of building partially disaggregated reduced master problems is investigated. This extends the idea of aggregated-versus-disaggregated formulation to a gradual choice of alternative level of aggregation. Partial aggregation is applied to the linear multicommodity minimum cost flow problem. The possibility of having only partially aggregated bundles opens a wide range of alternatives with different trade-offs between the number of iterations and the required computation for solving it. This trade-off is explored for several sets of instances and the results are compared with the ones obtained by directly solving the natural node-arc formulation. An iterative solution process to the route assignment problem is proposed, based on the well-known Frank Wolfe algorithm. In order to provide a first feasible solution to the Frank Wolfe algorithm, a linear multicommodity min-cost flow problem is solved to optimality by using the decomposition techniques mentioned above. Solutions of this problem are useful for network orientation and design, especially in relation with public transportation systems as the Personal Rapid Transit. A single-commodity robust network design problem is addressed. In this, an undirected graph with edge costs is given together with a discrete set of balance matrices, representing different supply/demand scenarios. The goal is to determine the minimum cost installation of capacities on the edges such that the flow exchange is feasible for every scenario. A set of new instances that are computationally hard for the natural flow formulation are solved by means of a new heuristic algorithm. Finally, an efficient decomposition-based heuristic approach for a large scale stochastic unit commitment problem is presented. The addressed real-world stochastic problem employs at its core a deterministic unit commitment planning model developed by the California Independent System Operator (ISO).

Application-oriented Mixed Integer Non-Linear Programming

In the most recent years there is a renovate interest for Mixed Integer Non-Linear Programming (MINLP) problems. This can be explained for different reasons: (i) the performance of solvers handling non-linear constraints was largely improved; (ii) the awareness that most of the applications from the real-world can be modeled as an MINLP problem; (iii) the challenging nature of this very general class of problems. It is well-known that MINLP problems are NP-hard because they are the generalization of MILP problems, which are NP-hard themselves. However, MINLPs are, in general, also hard to solve in practice. We address to non-convex MINLPs, i.e. having non-convex continuous relaxations: the presence of non-convexities in the model makes these problems usually even harder to solve. The aim of this Ph.D. thesis is to give a flavor of different possible approaches that one can study to attack MINLP problems with non-convexities, with a special attention to real-world problems. In Part 1 of the thesis we introduce the problem and present three special cases of general MINLPs and the most common methods used to solve them. These techniques play a fundamental role in the resolution of general MINLP problems. Then we describe algorithms addressing general MINLPs. Parts 2 and 3 contain the main contributions of the Ph.D. thesis. In particular, in Part 2 four different methods aimed at solving different classes of MINLP problems are presented. Part 3 of the thesis is devoted to real-world applications: two different problems and approaches to MINLPs are presented, namely Scheduling and Unit Commitment for Hydro-Plants and Water Network Design problems. The results show that each of these different methods has advantages and disadvantages. Thus, typically the method to be adopted to solve a real-world problem should be tailored on the characteristics, structure and size of the problem. Part 4 of the thesis consists of a brief review on tools commonly used for general MINLP problems, constituted an integral part of the development of this Ph.D. thesis (especially the use and development of open-source software). We present the main characteristics of solvers for each special case of MINLP.

Alla ricerca della sostenibilità: lo sviluppo dell'agricoltura dall'Unità d'Italia alla Green Economy

L’elaborato finale presentato per la tesi di Dottorato analizza e riconduce a unitarietà, per quanto possibile, alcune delle attività di ricerca da me svolte durante questi tre anni, il cui filo conduttore è l'impatto ambientale delle attività umane e la promozione dello sviluppo sostenibile. Il mio filone di ricerca è stato improntato, dal punto di vista di politica economica, sull'analisi storica dello sviluppo del settore agricolo dall'Unità d'Italia ai giorni nostri e dei cambiamenti avvenuti in contemporanea nel contesto socio-economico e territoriale nazionale, facendo particolare riferimento alle tematiche legate ai consumi e alla dipendenza energetica ed all'impatto ambientale. Parte della mia ricerca è stata, infatti, incentrata sull'analisi dello sviluppo della Green Economy, in particolare per quanto riguarda il settore agroalimentare e la produzione di fonti di energia rinnovabile. Enfasi viene posta sia sulle politiche implementate a livello comunitario e nazionale, sia sul cambiamento dei consumi, in particolare per quanto riguarda gli acquisti di prodotti biologici. La Green Economy è vista come fattore di sviluppo e opportunità per uscire dall'attuale contesto di crisi economico-finanziaria. Crisi, che è strutturale e di carattere duraturo, affiancata da una crescente problematica ambientale dovuta all'attuale modello produttivo, fortemente dipendente dai combustibili fossili. Difatti la necessità di cambiare paradigma produttivo promuovendo la sostenibilità è visto anche in ottica di mitigazione del cambiamento climatico e dei suoi impatti socio-economici particolare dal punto di vista dei disastri ambientali. Questo punto è analizzato anche in termini di sicurezza internazionale e di emergenza umanitaria, con riferimento al possibile utilizzo da parte delle organizzazioni di intervento nei contesti di emergenza di tecnologie alimentate da energia rinnovabile. Dando così una risposta Green ad una problematica esacerbata dall'impatto dello sviluppo delle attività umane.