Solving the logically constrained multiple choice multiple knapsack problem: A real case

In questa tesi viene analizzato un problema di ottimizzazione proposto da alcuni esercizi commerciali che hanno la necessita` di selezionare e disporre i propri ar- ticoli in negozio. Il problema nasce dall’esigenza di massimizzare il profitto com- plessivo atteso dei prodotti in esposizione, trovando per ognuno una locazione sugli scaffali. I prodotti sono suddivisi in dipartimenti, dai quali solo un ele- mento deve essere selezionato ed esposto. In oltre si prevede la possibilita` di esprimere vincoli sulla locazione e compatibilita` dei prodotti. Il problema risul- tante `e una generalizzazione dei gia` noti Multiple-Choice Knapsack Problem e Multiple Knapsack Problem. Dopo una ricerca esaustiva in letteratura si `e ev- into che questo problema non `e ancora stato studiato. Si `e quindi provveduto a formalizzare il problema mediante un modello di programmazione lineare intera. Si propone un algoritmo esatto per la risoluzione del problema basato su column generation e branch and price. Sono stati formulati quattro modelli differenti per la risoluzione del pricing problem su cui si basa il column generation, per individuare quale sia il piu` efficiente. Tre dei quattro modelli proposti hanno performance comparabili, mentre l’ultimo si `e rivelato piu` inefficiente. Dai risul- tati ottenuti si evince che il metodo risolutivo proposto `e adatto a istanze di dimensione medio-bassa.

Procedure di Programmazione Dinamica per Determinare le K Migliori Soluzioni del Knapsack Problem 0-1 e dello Shortest Path Problem

In questa tesi viene trattata la problematica di determinare le migliori K soluzioni per due problemi di ottimizzazione, il Knapsack Problem 0-1 e lo Shortest Path Problem. Tali soluzioni possono essere impiegate all'interno di metodi di column generation per la risoluzione di problemi reali, ad esempio Bin Packing Problems e problemi di scheduling di veicoli ed equipaggi. Sono stati implementati, per verificarne sperimentalmente le prestazioni, nuovi algoritmi di programmazione dinamica, sviluppati nell’ambito di un programma di ricerca. Inizialmente, per entrambi i problemi, è stato descritto un algoritmo che determinasse le migliori K soluzioni per ogni possibile sottoproblema; partendo da uno zaino con capacità nulla, nel caso del Knapsack Problem 0-1, e dalla determinazione di un cammino dal vertice sorgente in se stesso per lo Shortest Path Problem, l’algoritmo determina le migliori soluzioni di sottoproblemi via via sempre più grandi, utilizzando le soluzioni costruite per gli stati precedenti, fino a ottenere le migliori soluzioni del problema globale. Successivamente, è stato definito un algoritmo basato su un approccio di ricorsione backward; in questo caso si utilizza una funzione ricorsiva che, chiamata a partire dallo stato corrispondente al problema globale, viene richiamata solo sugli stati intermedi strettamente necessari, e per ognuno di essi non vengono determinate soluzioni superflue.

Trajectory design of a multiple flyby mission to asteroids

In designing the trajectory for a multiple flyby mission to asteroids the choice of the targets is the most challenging problem. This dissertation faces this problem in the framework of the recently issued medium-size mission call (M5) from ESA: CASTAway. Starting from the preliminary work done in [6], this thesis develops a methodology for sequencing the potential targets in a multiple flyby mission. In order to reduce the computational time, the complete database of known small bodies is firstly pruned on the base of heuristic considerations. Using the assumption of small manoeuvres, a chief orbit concept could be used. Thus, two heuristic thresholds are defined in order to exclude non-promising targets given a chief orbit. The sequencing process takes chief orbit and promising targets as inputs and gives a set of candidate sequences. The results of such a process are analysed in the CASTAway framework and the best feasible sequence studied in details.

LQG control policy design against agent identity privacy problem

This thesis project studies the agent identity privacy problem in the scalar linear quadratic Gaussian (LQG) control system. For the agent identity privacy problem in the LQG control, privacy models and privacy measures have to be established first. It depends on a trajectory of correlated data rather than a single observation. I propose here privacy models and the corresponding privacy measures by taking into account the two characteristics. The agent identity is a binary hypothesis: Agent A or Agent B. An eavesdropper is assumed to make a hypothesis testing on the agent identity based on the intercepted environment state sequence. The privacy risk is measured by the Kullback-Leibler divergence between the probability distributions of state sequences under two hypotheses. By taking into account both the accumulative control reward and privacy risk, an optimization problem of the policy of Agent B is formulated. The optimal deterministic privacy-preserving LQG policy of Agent B is a linear mapping. A sufficient condition is given to guarantee that the optimal deterministic privacy-preserving policy is time-invariant in the asymptotic regime. An independent Gaussian random variable cannot improve the performance of Agent B. The numerical experiments justify the theoretic results and illustrate the reward-privacy trade-off. Based on the privacy model and the LQG control model, I have formulated the mathematical problems for the agent identity privacy problem in LQG. The formulated problems address the two design objectives: to maximize the control reward and to minimize the privacy risk. I have conducted theoretic analysis on the LQG control policy in the agent identity privacy problem and the trade-off between the control reward and the privacy risk.Finally, the theoretic results are justified by numerical experiments. From the numerical results, I expected to have some interesting observations and insights, which are explained in the last chapter.