Lifting e generazione di disuguaglianze per il politopo delle matrici “Consecutive Ones”

Sommario
Lo studio sviluppato in questa tesi muove dall’esigenza di dare una for-
mulazione matematica ad alcuni problemi di sequenziamento ottimale
che emergono in diversi ambiti applicativi, quali ad esempio la piani-
ficazione della produzione, l’industria del taglio e la progettazione di
circuiti elettronici. In tali situazioni si presenta spesso l’esigenza di tro-
vare una permutazione ottimale di schemi, quali ad esempio ordini di
un prodotto, schemi di taglio, porte in un circuito elettronico, al fine
di minimizzare un’opportuna funzione obiettivo di costo: tali problemi
vengono denominati pattern sequencing problems.
Nel Capitolo 1 prenderemo in considerazione due importanti esempi
di problemi di sequenziamento: il Minimization of Open Stacks Problem
(MOSP) e il Gate Matrix Layout Problem (GMLP). Il MOSP emerge nel-
l’ambito dell’industria del taglio, nella quale si verifica di dover tagliare
dei grandi pannelli di materiale primo (quali legno, vetro, carta) secondo
degli schemi (pattern) predefiniti. Una volta eseguito il taglio, i vari pez-
zi vengono impilati in pile (stack) che raccolgono tutti gli elementi dello
stesso tipo ricavati dai diversi pannelli. Si noti che, una volta stabilita la
sequenza di taglio, pezzi dello stesso tipo possono essere presenti in pan-
nelli tagliati in momenti diversi. Le pile, per evitare costi di spostamento
in magazzino, vengono posizionate nei pressi della zona di taglio fino al
termine del processo, o almeno fino a che l’ultimo pezzo dello stesso tipo
sia stato ricavato dai pannelli. Spesso lo spazio di lavoro a disposizione
risulta limitato, e di conseguenza sorge la necessità di minimizzare, per
motivi logistici o di sicurezza, o per evitare possibili danni ai pezzi pro-
dotti, il numero di pilesimultaneamente aperte. Oppure, nelcaso incui il
numero di pile utilizzabili abbia un limite superiore stabilito a priori dal
layout degli stabilimenti, si cerca di scegliere una sequenza di schemi di
taglio che minimizzi il tempo totale di presenza delle pile nei pressi delle
macchine, cercando di ridurre l’intervallo di tempo definito dai momenti
in cui il primo e l’ultimo pezzo di un certo tipo vengono prodotti.
Il secondo problema descritto, quello denominato GMLP, è equiva-
lente al MOSP e si presenta nella progettazione di circuiti elettronici
attraverso la tecnologia VLSI (Very Large Scale Integration), la quale
prevede una elevata integrazione di transistor ed altri elementi circuitali
all’interno di un singolo chip. In molti casi, la realizzazione di un circuito
1
2 INDICE
con questa tecnologia prevede di connettere fra loro varie porte (gates) di
struttura predefinita contenenti un certo numero di transistor. Per colle-
gare far di loro i transistor delle porte si utilizzano delle reti (nets) di filo
metallico, disposto perpendicolarmente alle porte stesse in maniera da
creare circuiti logici sulle colonne (le porte) e le righe (le reti) del circui-
to. Anche in questo caso l’obiettivo è quello di minimizzare una funzione
di costo, nello specifico il numero totale di unità di filo metallico utilizza-
te per la effettuare i collegamenti oppure, nel caso in cui tali unità siano
soggette ad upper bound per ogni riga, il numero di reti parallele che si
sovrappongono nella connessione di ogni porta: le reti parallele, infatti,
non possono essere sovrapposte e il loro numero definisce la superficie
necessaria, e quindi il livello di integrazione.
I due problemi presentati possono essere modellati utilizzando varia-
bili decisionali binarie di una matrice, associata alla configurazione scelta
per i vari pattern, e formulati in termini di programmazione lineare inte-
ra. In letteratura, si è osservato come la definizione dei problemi possa
essere messa in relazione con la proprietà dei pattern di ammettere una
permutazione la quale renda consecutivi gli elementi presenti negli sche-
mi: ad esempio, la definizione di una sequenza di schemi di taglio che
permette di produrre ciascun tipo pezzi senza interruzioni fa in modo che
le relative pile rimangano aperte per il minimo intervallo di tempo. In
terminimatricialiciòsitraducenelladefinizionedimatricibinariechego-
dano della cosiddetta “proprietà degli uni consecutivi” (o siano C1P). Una
matrice binaria si dice C1P se esiste una permutazione delle sue colonne
tale che gli uni di ogni riga appaiano consecutivamente. La relazione fra
questa proprietà e la formulazione dei problemi di sequenziamento forni-
sce un’importante motivazione per cercare di dare una caratterizzazione
del vincolo “la matrice X è C1P” in termini di disuguaglianze lineari:
individuare opportune disequazioni che permettano di definire lo spazio
delle matrici binarie che verificano la proprietà degli uni consecutivi per-
mette infatti di ottenere formulazioni stringenti (e quindi potenzialmente
efficienti dal punto di vista computazionale) dell’insieme ammissibile dei
problemi MOSP e GMLP.
A tale scopo forniremo nel Capitolo 2 una serie di richiami ad elemen-
ti di teoria dei grafi che risulteranno utili nel seguito della trattazione: in
particolare si introdurrà il concetto di tripla asteroidale di vertici in un
grafo. La definizione di tripla asteroidale viene sfruttata in letteratura
per fornire la principale caratterizzazione di una classe di grafi detti grafi
intervallo, ovvero i grafi che rappresentano le intersezioni di un insieme
di intervalli nella retta reale. Tali grafi sono correlati alla proprietà degli
uni consecutivi, e questo legame è stato sfruttato da Tucker in [26] per
fornire una caratterizzazione generale delle matrici C1P, la quale fa uso
del concetto di tripla asteroidale escludendone la presenza in grafi bipar-
titi associati in maniera opportuna alle matrici binarie in esame. Nel
Capitolo 2 verranno poi richiamati alcuni fondamentali risultati di geo-
INDICE 3
metria della programmazione lineare, e soprattutto verrà presentato lo
strumento principale di questa tesi: la nozione di lifting di una disugua-
glianza lineare, valida per un insieme 0-1. L’iterazione dell’operazione
di lifting permette di definire un algoritmo di lifting sequenziale il quale,
a partire da disuguaglianze valide per particolari sezioni dell’insieme 0-1
in oggetto, restituisce disuguaglianze valide per l’intero insieme binario.
Infine verranno date delle informazioni riguardo al software PORTA, che
verrà utilizzato per analizzare le disequazioni oggetto della procedura di
lifting definita in questa tesi.
Nel Capitolo 3 si seguirà inizialmente l’esposizione di Tucker in [26],
nella quale si dimostra come, sfruttando la caratterizzazione che lega
matrici C1P a grafi bipartiti privi di triple asteroidali in uno dei due
sottoinsiemi di vertici, sia possibile ottenere un teorema per la caratte-
rizzazione strutturale di tali grafi. Tale teorema strutturale si può poi
convertire nel suo analogo matriciale il quale descrive le matrici C1P vie-
tandone particolari minori, chiamati minori di Tucker. Si passerà poi a
studiare gli aspetti poliedrali dell’inviluppo convesso generato dalle ma-
trici binarie che godono della proprietà degli uni consecutivi, seguendo il
lavoro di Oswald e Reinelt in [19]. Tale approccio permetterà di ottenere
una formulazione per il politopo C1P, ottenendo in particolar modo una
descrizione tramite disuguaglianze definenti faccette. Le disequazioni ot-
tenute in [19] sono state studiate prima da Brentegani in [4] e poi da
Festa in [11] al fine di fornirne una genesi grafica, ossia delle procedure
basate sui grafi associati alle matrici binarie. Anche queste procedure,
che hanno permesso di derivare ulteriori classi di faccette per il politopo
C1P, saranno descritte nel Capitolo 3. In particolare si analizzeranno
due procedure le quali generano le disuguaglianze cercando di escludere
una o molteplici triple asteroidali nel grafo bipartito di partenza.
Nel Capitolo 4 si introduce il primo contributo di questa tesi: traendo
spunto dalle procedure per la definizione di disuguaglianze valide per il
politopo C1P, si individueranno delle caratteristiche comuni fra queste
ultime e l’algoritmo di lifting sequenziale. Si comincerà specializzando il
processo di lifting al caso dell’insieme binario delle matrici C1P: in par-
ticolare si osserverà come il calcolo dei nuovi coefficienti nelle iterazioni
della sequenza possa essere interpretato in maniera grafica. Eseguendo
nei dettagli il lifting sequenziale su di un esempio specifico si cercheran-
no di analizzare le due possibili scelte che determinano le disuguaglianze
risultanti dall’algoritmo, ovvero la disuguaglianza che inizializza la se-
quenza dei lifting, e l’ordine delle variabili secondo il quale eseguire le
varie iterazioni. Ci si concentrerà inizialmente sul primo dei due pro-
blemi, al fine di individuare delle disuguaglianze definenti faccette per
sezioni di partenza: a partire da tali disequazioni le proprietà della pro-
cedura di lifting garantiscono di ottenere delle faccette per il politopo
delle matrici consecutive ones. In particolare, analizzeremo il caso in cui
le disuguaglianze di partenza per il lifting derivano da considerazioni gra-
4 INDICE
fiche su particolari configurazioni di matrici non C1P, scelte in modo che
i coefficienti delle disuguaglianze assumano coefficienti di valore unitario
nella sezione considerata.
In seguito al Capitolo 5, che costituisce il principale contributo origi-
nale della tesi, si passerà ad analizzare, oltre alla configurazione grafica
di partenza, anche la scelta dell’ordinamento con il quale eseguire la
sequenza di lifting sulle variabili della disequazione. Innanzitutto si re-
stringeranno a priori i possibili valori che possono assumere i coefficienti
fissati nelle disuguaglianze dal lifting sequenziale, analizzando gli aspetti
grafici dell’algoritmo sul politopo C1P e il ruolo degli ordinamenti nella
sequenza di lifting. Si giungerà a questo punto al risultato centrale della
tesi: traendo ispirazione dalle caratteristiche comuni fra lifting sequen-
ziale e procedure note per la formulazione di disuguaglianze valide per
le matrici C1P, si dimostrerà come, sotto opportune condizioni, questi
procedimenti sono esattamente equivalenti ad un lifting. A tale scopo,
si classificheranno in maniera generale tutte le possibili configurazioni di
tre cammini che rendono una tripla di nodi colonna asteroidale in un
grafo bipartito, riottenendo fra i casi particolari le generalizzazioni dei
minori di Tucker. Si procederà quindi ad analizzare separatamente per
ogni classe di configurazione iniziale i risultati del lifting sequenziale, stu-
diandone la versione grafica: in questo modo si otterranno le condizioni
da imporre affinché le procedure coincidano con un lifting. L’importanza
teoricaeapplicativadiquestorisultatorisiedenelfattoche, neicasiincui
una tale identificazione è possibile, le procedure erediteranno le proprietà
generali del lifting, e in questo modo si potranno ottenere direttamente
informazioni sulla validità delle disuguaglianze indotte e sulla dimensione
delle facce che esse inducono per il politopo C1P.
Nel Capitolo 6 si verificheranno i risultati ottenuti per lifting e pro-
cedure su una particolare configurazione iniziale, esplicitando gli ordina-
menti utilizzati e controllandone le condizioni. Traendo spunto dall’a-
nalisi eseguita nel corso della trattazione, si cercherà di estendere l’ap-
plicazione del lifting anche a disuguaglianze iniziali di tipo diverso da
quelle correlate a configurazioni non C1P nella maniera sopra accennata
(ad esempio non necessariamente a coefficienti unitari). In particolare,
esamineremo tutte le classi di faccette che descrivono il problema C1P
per la dimensione 4 4. Lo studio in questo caso utilizzerà sia i risultati
dimostrati nella trattazione riguardo alle proprietà delle disuguaglianze
di partenza per il lifting, sia strumenti computazionali come un codice
C++ che generi opportune sezioni iniziali ed il software PORTA per lo
studio delle dimensioni delle facce ottenute.
L’estensione trattata al Capitolo 6 fornirà degli spunti per alcuni
possibili sviluppi futuri, suggeriti al Capitolo 7.