Fabrizio Marinelli - Argomenti

Problema dello zaino con vincoli aggiuntivi

Il problema dello zaino (Knapsack Problem) è uno dei più noti e fondamentali problemi di ottimizzazione discreta:

dati n oggetti, ognuno disponibile in un determinato numero di copie e descritto da un valore e da un peso, quante copie di quali oggetti formano l’insieme di valore massimo e con peso complessivo non superiore ad una soglia data?

In alcuni casi, per esempio nell’ambito del packing bidimensionale, il problema è arricchito da vincoli di cardinalità (non più di k di n oggetti possono essere selezionati), da vincoli di compatibilità (un solo oggetto può essere selezionato da un sottoinsieme dato) e da vincoli di disponibilità aggregata (il massimo numero di copie utilizzabili è relativo ad un insieme di oggetti piuttosto che a un solo oggetto).

Argomenti di Tesi

Progettazione e implementazione di algoritmi di branch-and-bound per il problema dello zaino intero con vincoli di cardinalità, compatibilità e disponibilità aggregata.
Problemi di zaino intero con vincoli aggiuntivi: analisi dello stato dell’arte.

Visualizzazione ottimale di grafi

Svariati ambiti della ricerca e della progettazione ricorrono all’uso dei grafi come strumento formale di rappresentazione, di analisi e, in generale, di knowledge management.

Sebbene la struttura matematica di un grafo possa fornire di per sé utili informazioni sull’oggetto rappresentato, spesso i grafi sono utilizzati come semplici strumenti di visualizzazione. In tale contesto, un aspetto rilevante riguarda la disposizione dei nodi su un piano (graph drawing o graph embedding) che renda la struttura del grafo più chiara possibile.

Le due figure a fianco riportano lo stesso grafo disegnato in due modi diversi: sebbene entrambe rappresentino lo stesso oggetto, il layout inferiore illustra molto più chiaramente la struttura del grafo (che in questo caso è planare).

Argomenti di Tesi

Definizione e sperimentazione di Modelli di Programmazione Matematica per l’embedding di grafi sul piano.
Problemi di graph drawing: analisi dello stato dell’arte.

Problemi di taglio: gestione dei setup

In termini generali, risolvere un problema di taglio significa decidere come ottenere, nel modo più efficiente possibile e per mezzo di operazioni di taglio, una data richiesta di oggetti “piccoli” (parti) da un insieme di oggetti “grandi” (stocks) di dimensione standard. Per una trattazione approfondita del tema, richiedere al docente il modulo didattico “Problemi di taglio: modelli, algoritmi e applicazioni”.

Sebbene la letteratura offra numerosi contributi, sia esatti sia euristici, per la soluzione di specifici problemi di taglio (in una, due o tre dimensioni), lo studio delle attività di taglio all’interno di un processo produttivo più ampio, che include il sequenziamento delle operazioni, la gestione del magazzino e il rispetto delle scadenze, continua a rappresentare un tema di grande interesse, sia teorico sia applicativo.

In generale, le operazioni di taglio vengono rappresentate tramite un insieme di schemi specifici (come illustrato nella figura). Ogni volta che la macchina passa da uno schema di taglio a un altro, è necessario eseguire una corretta predisposizione, detta **operazione di setup**. Per questo motivo, in molte situazioni, è altrettanto importante determinare soluzioni che utilizzino un numero limitato di schemi di taglio quanto ridurre al minimo gli scarti di materiale.

Argomenti di Tesi

studio di modelli alternativi di Programmazione Lineare Intera per la minimizzazione del numero di setup.
progettazione di euristiche sequenziali per la riduzione del numero di setup basate sull’accorpamento della domanda e/o sull’accorpamento delle dimensioni delle parti.
studio di strategie di pretaglio e analisi dell’impatto sulla qualità delle soluzioni.
analisi e definizione di strategie per la soluzione del problema multi-obiettivo relativo alla minimizzazione congiunta di sfrido e numero di setup.

Problemi di ottimizzazione su grafi signed

Un grafo signed è un grafo non orientato i cui archi sono etichettati con +1 (arco positivo) e -1 (arco negativo). Il segno di un insieme C di archi (per esempio un cammino o un ciclo) è dato dal prodotto dei segni degli archi in C. Un grafo signed è bilanciato se non ha cicli negativi. Dato un grafo signed, il problema MBIS consiste nell’individuare un sottografo indotto bilanciato di ordine massimo (cioè con il massimo numero di nodi).

Un’euristica per il problema MBIS generalizza l’algoritmo greedy per il problema di massimo insieme stabile e si basa su una trasformazione del grafo (negative cycle contraction rule) che riduce progressivamente la lunghezza dei cicli negativi. Per approfondire l’argomento consultare il seguente articolo

Applicazioni

Social Networking: una network di individui può essere rappresentata da un grafo signed in cui i nodi rappresentano gli individui stessi e un arco positivo (negativo) rappresenta una relazione di amicizia (ostilità). E’ generalmente riconosciuto che cicli positivi indicano situazioni sociali stabili, mentre cicli negativi indicano situazioni di instabilità. Una soluzione del problema MBIS fornisce una misura della coesione sociale del gruppo.

Portfolio Analysis: i nodi di un grafo signed rappresentano i titoli azionari e un arco positivo (negativo) indica una correlazione diretta (inversa) tra i titoli. Si è osservato che il comportamento del portfolio è tanto più prevedibile quanto più grande è la dimensione del massimo sottografo indotto bilanciato.

Sistemi biologici e dinamici: un grafo interazione (anche detto grafo di influenza) è uno strumento importante per analizzare le relazioni causa-effetto della trasmissione del segnale, o in generale del flusso di informazioni, in reti cellulari, sistemi dinamici, trasduttori di segnali o GRN - Gene Regulatory Networks. Un grafo interazione è un grafo signed diretto in cui gli archi indicano una relazione causale diretta tra gli agenti direttamente coinvolti (i nodi incidenti all’arco). Per esempio, in un GRN un arco positivo (negativo) tra la molecola A e la molecola B indica che la molecola A attiva (inibisce) la molecola B.

Programmazione matematica: L’individuazione di una struttura speciale nella matrice dei coefficienti di un modello di Programmazione Lineare Intera è talvolta determinante per la soluzione del programma in tempi ragionevoli. Una delle strutture più note è quella relativa alle matrici totalmente unimodulari (TU). Dato che nella maggior parte dei casi la matrice non è TU, si è interessati a determinare la sottomatrice TU di ordine massimo. Un sottoinsieme di matrici TU sono le matrici network. Il problema MBIS coincide con il problema di determinare la sottomatrice network di ordine massimo.

Casi particolari: Infine, il problema MBIS generalizza i problemi di massimo sottografo bipartito (con applicazioni in VLSI design, sequenziamento del DNA e biologia computazionale) e massimo insieme stabile (presente come sottoproblema o rilassamento di svariati problemi di programmazione matematica). In questo senso il bilanciamento è un concetto che estende quello di indipendenza ai casi in cui la relazione tra oggetti è sia di compatibilità che di incompatibilità.

Argomenti di Tesi

studio poliedrale del modello di PLI proposto da Figueiredo et al. (vedi tesi di dottorato) e definizione di modelli alternativi.
progettazione di una euristica di ricerca locale basata sulla negative cycle contraction rule.
progettazione di una euristica basata su operazioni di max-cut.
estensione della negative cycle contraction ad altri problemi di ottimizzazione su grafi signed.
analisi di politiche alternative di selezione degli archi ai quali applicare la negative cycle contraction rule.

Altri argomenti

Progettazione di algoritmi metaeuristici per la turnazione del personale
Ottimizzazione della schedulazione del taglio in un sistema cnc
Processi di taglio nell'industria manifatturiera: analisi dei vincoli tecnologici e organizzativi
Analisi preliminare e progettazione di un repository per algoritmi di ottimizzazione
Modelli di simulazione a eventi discreti per problemi di scheduling in ambito manifatturiero
Modelli di programmazione matematica per un problema di scheduling su singola macchina
Algoritmi di generazione di colonne per problemi di scheduling e routing
Progettazione e implementazione di un traduttore di equazioni semantiche nell’ambito dell’analisi statica del software (conoscenza c/c++)
Definizione di un modello di programmazione con vincoli per un problema di platforming (uso di eclipse)