Vai ai contenuti. | Spostati sulla navigazione | Spostati sulla ricerca | Vai al menu | Contatti | Accessibilità

logo del sistema bibliotecario dell'ateneo di padova

Zaccaria, Francesco (2016) Lifting e generazione di disuguaglianze per il politopo delle matrici “Consecutive Ones”. [Magistrali biennali]

Full text disponibile come:

[img]
Preview
PDF
831Kb

Abstract

Lo studio sviluppato in questa tesi muove dall'esigenza di dare una formulazione matematica ad alcuni problemi di sequenziamento ottimale che emergono in diversi ambiti applicativi, quali ad esempio la pianificazione della produzione, l'ndustria del taglio e la progettazione di circuiti elettronici. In tali situazioni si presenta spesso l'esigenza di trovare 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). I due problemi presentati possono essere modellati in termini di programmazione lineare intera. 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 schemi. In termini matriciali ciò si traduce nella definizione di matrici binarie che godano della cosiddetta “proprietà degli uni consecutivi” (o siano C1P). Forniremo nel Capitolo 2 una serie di nozioni di teoria dei grafi: in particolare si introdurrà il concetto di tripla asteroidale di vertici in un grafo. Verranno poi richiamati alcuni risultati di geometria della programmazione lineare, e soprattutto verrà presentato lo strumento principale di questa tesi: la nozione di lifting di una disuguaglianza lineare, valida per un insieme 0-1. Nel Capitolo 3, sfruttando la caratterizzazione che lega matrici C1P a grafi bipartiti privi di triple asteroidali in uno dei due sottoinsiemi di vertici, si illustrerà un teorema di Tucker per la caratterizzazione strutturale di tali grafi. Si passerà a studiare la formulazione per il politopo C1P, ottenendo in particolar modo una descrizione tramite disuguaglianze definenti faccette. In particolare si analizzeranno due procedure le quali generano 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: si individueranno delle caratteristiche comuni fra le procedure per la definizione di disuguaglianze valide per il politopo C1P e l’algoritmo di lifting sequenziale. Eseguendo nei dettagli il lifting sequenziale su di un esempio specifico si cercheranno di analizzare le due possibili scelte che determinano le disuguaglianze risultanti dall’algoritmo, ovvero la disuguaglianza che inizializza la sequenza dei lifting, e l’ordine delle variabili secondo il quale eseguire le varie iterazioni. In seguito al Capitolo 5, che costituisce il principale contributo originale 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. Si giungerà a questo punto al risultato centrale della tesi: si dimostrerà come, sotto opportune condizioni, le procedure note per la formulazione di disuguaglianze valide per le matrici C1P sono esattamente equivalenti ad un lifting sequenziale. 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. L’importanza teorica e applicativa di questo risultato risiede nel fatto che, nei casi in cui una tale identificazione è possibile, le procedure erediteranno le proprietà generali del lifting. Nel Capitolo 6 si verificheranno i risultati ottenuti per lifting e procedure. Si cercherà di estendere l’applicazione 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). 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.

Item Type:Magistrali biennali
Uncontrolled Keywords:lifting, consecutive ones, integer linear programming (ILP), graph theory
Subjects:Area 01 - Scienze matematiche e informatiche > MAT/09 Ricerca operativa
Codice ID:54200
Relatore: De Giovanni, Luigi
Data della tesi:01 July 2016
Biblioteca:Polo di Scienze > Biblioteca di Matematica
Tipo di fruizione per il documento:on-line per i full-text
Tesi sperimentale (Si) o compilativa (No)?:No

Bibliografia

I riferimenti della bibliografia possono essere cercati con Cerca la citazione di AIRE, copiando il titolo dell'articolo (o del libro) e la rivista (se presente) nei campi appositi di "Cerca la Citazione di AIRE".
Le url contenute in alcuni riferimenti sono raggiungibili cliccando sul link alla fine della citazione (Vai!) e tramite Google (Ricerca con Google). Il risultato dipende dalla formattazione della citazione e non da noi.

[1] P. Baptiste, Simple MIP Formulations to Minimize the Maximum Number of Open Stacks, Proceedings of IJCAI'05 - Constraint Modelling Challenge 2005, 9-13 (2005) Cerca con Google

[2] J.A. Bondy, U.S.R. Murty, Graph Theory, Graduate Texts in Cerca con Google

Mathematics, Springer (2008). Cerca con Google

[3] K.S. Booth, G.S. Lueker, Testing for the Consecutive Ones Property, Interval Graphs, and Graph Planarity using PQ-Tree Algorithms, Journal of Computer System Science, 13:335-379 (1976). Cerca con Google

[4] L. Brentegani, Soluzione di problemi di sequenziamento con l'uso di matrici "consecutive ones", Tesi di Laurea Magistrale in Matematica (2011-2012). Cerca con Google

[5] T. Christof, A. Loebel, Software and Data: PORTA POlyhedron Cerca con Google

Representation Transformation Algorithm, disponibile presso Cerca con Google

http://comopt.ifi.uni-heidelberg.de/software/PORTA/, Heidelberg Vai! Cerca con Google

University, Discrete and Combinatorial Optimization. Cerca con Google

[6] M. Conforti, G. Cornuéjols, G. Zambelli, Integer rogramming, Cerca con Google

Springer (2014). Cerca con Google

[7] L. De Giovanni, G. Massi, F. Pezzella. M.E. Pfetsch, G. Rinaldi, Cerca con Google

P. Ventura, A heuristic and an exact method for the gate matrix Cerca con Google

connection cost minimization problem, International Transaction in Operational Research, 20:627-643 (2013). Cerca con Google

[8] L. De Giovanni, L. Brentegani, Procedure per la formulazione di disuguaglianze valide per il politopo degli uni consecutivi, Report tecnico, Università di Padova (2013). Cerca con Google

[9] L. De Giovanni, Notes on procedures to identify valid inequalities for the C1P polytope, Report tecnico, Università di Padova (2014). Cerca con Google

[10] M. Di Summa, Note di Teoria dei Grafi, Dispense, Università di Padova Cerca con Google

[11] M. Festa, Considerazioni sul politopo delle matrici "consecutive ones" e applicazioni a problemi di sequenziamento, Tesi di Laurea Magistrale in Matematica (2012-2013). Cerca con Google

[12] D.R. Fulkerson, O.A. Gross, Incidence matrices and interval graphs, Pacific Journal of Mathematics, Vol. 15, No. 3 (1965). Cerca con Google

[13] Z. Gu, G.L. Nemhauser, M.W.P. Savelsbergh, Sequence Indipendent Lifting in Mixed Integer Programming, Georgia Institute of Technology, School of Industrial and Systems Engineering. Cerca con Google

[14] V. Klee, What are the intersection graphs of arcs in a circle?, Amer. Math. Monthly, (1969), 76:810-813. Cerca con Google

[15] C.E. Lekkerkerker, J.Ch. Boland, Representation of finite graph by a set of intervals on the real line, Fund. Math., 51:45-64 (1962). Cerca con Google

[16] A. Linhares, H.H. Yanasse, Connections between cutting-pattern sequencing, VLSI design, and flexible machines, Computers and Operation Research, 29:1759-1772 (2002). Cerca con Google

[17] G. Nemhauser, L. Wolsey, Integer and Combinatorial Optimization, John Wiley and Sons, (1988). Cerca con Google

[18] D. Osmani, Matrices with the consecutive ones property, interval graphs and their applications, Master Thesis, University of Cerca con Google

Kaiserslautern (2001). Cerca con Google

[19] M. Oswald, G. Reinelt, Polyhedral Aspects of the Consecutive Ones Problem, COCOON, Computing and Combinatorics, Proceedings of the 5th Conference on Computing and Combinatorics (2000), 1858:373-382. Cerca con Google

[20] M. Oswald, G. Reinelt, Computing Optimal Consecutive Ones Matrices, The Sharpest Cut, The Impact of Manfred Padberg and His Work, Optimization, 173-184 (2004). Cerca con Google

[21] Polar Duality, Polyhedra and Polytopes, Dispense, Penn Engineering School of Engineering and Applied Science, University of Pennsylvania Cerca con Google

[22] F.S. Roberts, Representations of Indifference Relations, PhD thesis, Stanford University (1968). Cerca con Google

[23] F.S. Roberts, Indifference Graphs, Proof Techniques in Graph Theory, Proceedings of the Second Ann Arbor Graph Conference, Academic Press, New York (1969). Cerca con Google

[24] H. Ryser, Combinatorial configurations, SIAM Journal on Applied Mathematics, 17:593 (1969). Cerca con Google

[25] A. Tucker, Matrix characterizations of circular-arc graphs, Pacific Journal of Mathematics, 38:2 (1971). Cerca con Google

[26] A. Tucker, A structure theorem for the consecutive 1's property, Journal of Combinatorial Theory Series B, 12:153-162 (1972). Cerca con Google

[27] L'enciclopedia libera Wikipedia, Very large scale integration, Cerca con Google

http://it.wikipedia.org/wiki/Very_large_scale_integration Vai! Cerca con Google

(2016). Cerca con Google

[28] G. Zarpellon, Generazione di disuguaglianze valide per il politopo delle matrici "consecutive ones", Tesi di Laurea Magistrale in Matematica (2013-2014). Cerca con Google

[29] E. Zemel, Lifting the facets of zero-one polytopes, Mathematical Programming, 15:268-277 (1978). Cerca con Google

Solo per lo Staff dell Archivio: Modifica questo record