Mixed-integer programming models and methods for bilevel fair network optimization and energy cogeneration planning

This thesis addresses two relevant mixed-integer optimization problems, with application in telecommunications and energy systems, using mathematical programming techniques. The first part focuses on a bilevel multi-commodity flow problem subject to max-min fair flow allocation, which arises in telecommunication networks with elastic demands. The problem is motivated by routing in internet protocol (IP) networks, where there are no prescribed demands to be satisfied, since the network provides a best-effort service. The network operator aims at maximizing a utility function (total throughput), by selecting the routing paths, while the bandwidth is allocated fairly by the distributed transport protocol. Accordingly, we define the maximum-throughput Unsplittable Flow Problem subject to Max-Min Fair flow allocation (UFP-MMF) as the bilevel problem where, at the upper level, the routing paths maximizing the total throughput are sought, while, at the lower level, the flow is allocated to each origin-destination pair maximizing a fairness measure. After recalling some background concepts, we discuss the motivation, summarize related work and investigate theoretical properties of UFP-MMF, including complexity results and its price of fairness. Then, we discuss how the bilevel problem can be cast as a single-level mixed-integer programming problem exploiting the concept of bottleneck arcs. The single-level problem turns out to be very challenging due to the origin-destination paths that have to be elementary and to the second-level optimality conditions related to the bottleneck arcs. We develop two MIP-based approaches: a branch-and-cut algorithm based on an arc formulation, where subtour are prevented separating generalized cutset inequalities, and a branch-and-price algorithm based on a path formulation. We also propose an efficient local search heuristic that provides close-to-optimal solutions in a short computing time on a set of realistic instances. Finally, we discuss relaxations of UFP-MMF, involving alternative fairness criteria, that provide tight dual bounds. The second part of the thesis studies an operational planning problem arising in energy cogeneration systems with thermal storage. The goal is to determine the operational schedule of a set of (co)generation units (i.e., on/off status and production level), over a given time horizon, in order to minimize the operating costs while satisfying users demands. After a brief survey on previous and related work, we discuss mixed-integer programming formulations, focusing on some basic variants of the problem. For the variant with constant production upper and lower bounds, a polynomial dynamic programming algorithm is described. To account for uncertainties in the demand forecast, we propose a formulation based on gamma-robustness. Finally, we tackle some real-world instances of the problem, solved as a MINLP or as a MILP, exploiting a piecewise-linear approximation. The linearized formulation can typically be solved within reasonable time up to horizons of a few weeks. When yearly economic incentives have to be taken into account, we also propose a MILP-based rolling-horizon heuristic that can be applied to larger-scale problems provided by an Italian energy company.

In questa tesi studiamo due problemi di ottimizzazione lineare misto-intera, con applicazioni nei sistemi di telecomunicazione e di generazione di energia, con tecniche di programmazione matematica. La prima parte della tesi si concentra su un problema bilivello di flussi multi-commodity soggetto a vincoli di equità, motivato dall'instradamento in reti internet con servizio best-effort. L'obiettivo dell'operatore di rete è massimizzare una funzione di utilità (e.g., il throughput sulla rete), selezionando i cammini di instradamento, mentre è il protocollo di trasporto distribuito che alloca i singoli flussi. Definiamo quindi il problema bilivello di flusso massimo soggetto a vincoli di equità (maximum-throughput Unsplittable Flow Problem subject to Max-Min Fair flow allocation, UFP-MMF), in cui al livello superiore si vogliono determinare i cammini di instradamento che massimizzino il throughput totale, mentre al secondo livello il flusso è allocato alle coppie origine-destinazione secondo il criterio di Max-Min Fairness. Dopo aver motivato e studiato il problema dal punto di vista teorico, proponiamo due metodi basati su programmazione matematica misto-intera, ed un metodo di ricerca locale che permette di trovare buone soluzioni con tempi di calcolo ridotti. La seconda parte della tesi studia un problema di scheduling operazionale in sistemi di cogenerazione di energia con sistemi di accumulo termico, dove si vuole determinare le operazioni di un insieme di unità (co)generative in modo da soddisfare le domande di energia elettrica e termica degli utenti e minimizzare i costi. Ci concentriamo su formulazioni di programmazione lineare e nonlineare misto-intera, e su alcune varianti di base del problema, per cui esistono algoritmi polinomiali. Discutiamo inoltre alcuni casi reali, in cui occorre risolvere problemi a più lungo termine, per tenere conto di vincoli annuali.