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

Indice
Sommario 1
1 Introduzione e presentazione del problema 5
1.1 Problemi di sequenziamento . . . . . . . . . . . . . . . . 5
1.1.1 Minimization of Open Stacks Problem (MOSP) . 6
1.1.2 Gate Matrix Layout Problem (GMLP) . . . . . . 7
1.2 Formulazioni e matrici “Consecutive Ones” . . . . . . . . 8
2 Elementi di Programmazione Lineare e strumenti 13
2.1 Cenni sui grafi . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2 Le matrici “Consecutive Ones” . . . . . . . . . . . . . . . 16
2.3 Cenni di geometria della programmazione lineare . . . . 19
2.4 Lifting . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.4.1 Interpretazione geometrica del lifting nello spazio
polare . . . . . . . . . . . . . . . . . . . . . . . . 25
2.4.2 Ordinamenti delle variabili nel lifting sequenziale 28
2.5 PORTA e analisi delle faccette di una sezione . . . . . . 30
3 Aspetti poliedrali e procedure 33
3.1 Teorema di struttura per le matrici C1P . . . . . . . . . 34
3.1.1 Proprietà degli uni consecutivi su un grafo . . . . 34
3.1.2 Minori di Tucker e teorema di struttura . . . . . . 36
3.1.3 Una prima formulazione per il vincolo C1P . . . . 39
3.2 Il politopo degli uni consecutivi . . . . . . . . . . . . . . 41
3.2.1 Proprietà del politopo P
m;n
C1
. . . . . . . . . . . . 41
3.2.2 Formulazione con faccette per il vincolo C1P . . . 43
3.3 Procedure . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4 Lifting e generazione di faccette 57
4.1 Lifting per il politopo C1P . . . . . . . . . . . . . . . . . 58
4.1.1 Specializzazione del lifting sequenziale al politopo
C1P . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.1.2 Esempio: il minore M
IV
. . . . . . . . . . . . . . 60
4.2 Sezioni di partenza per faccette note . . . . . . . . . . . 67
4.2.1 Condizioni algebriche generali . . . . . . . . . . . 68
i

ii INDICE
4.2.2 Esempio: la disuguaglianza VI . . . . . . . . . . 73
5 Lifting e procedure 77
5.1 Proprietà dei coefficienti del lifting . . . . . . . . . . . . 78
5.2 Lifting e configurazioni iniziali . . . . . . . . . . . . . . . 80
5.2.1 Classificazione delle configurazioni non C1P . . . 80
5.2.2 Configurazioni e disuguaglianze di partenza . . . 87
5.3 Configurazioni e sequenze di lifting . . . . . . . . . . . . 90
5.3.1 La configurazione di partenza I
k
. . . . . . . . . . 90
5.3.2 Le configurazioni di partenza III
s;d;l
e IV
s;d;l
. . 98
5.3.3 Le configurazioni di partenza V
u;f;g;l
e VI
u;f;g;l
. . 102
5.3.4 LeconfigurazionidipartenzaVII
l;s;u;f;g
eVIII
l;s;d;u;f;g
106
6 Applicazione ed estensioni del lifting 111
6.1 Sequenze di lifting per la Procedura 4 sul minore M
IV
. . 112
6.2 Le faccette del politopo P
4;4
C1
. . . . . . . . . . . . . . . . 115
7 Conclusioni e sviluppi futuri 127
Riferimenti bibliografici 131
Ringraziamenti 135