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

| Crea un account

Zanette, Arrigo (2009) Three Topics in Mixed Integer Programming. [Tesi di dottorato]

Full text disponibile come:

[img]
Anteprima
Documento PDF
2565Kb

Abstract (inglese)

In chapter entitled "Lexicography and degeneracy: Can a pure cutting plane algorithm work?", we discuss an implementation of the lexicographic version of Gomory's fractional cutting plane method for Integer Linear Programming (ILP) problems and of two heuristics mimicking the latter. In computational testing on a battery of MIPLIB problems we compare the performance of these variants with that of the standard Gomory algorithm, both in the single-cut and in the multi-cut (rounds of cuts) version, and show that they provide a radical improvement over the standard procedure. In particular, we report the exact solution of ILP instances from MIPLIB such as stein15, stein27, and bm23, for which the standard Gomory cutting plane algorithm is not able to close more than a tiny fraction of the integrality gap. We also offer an explanation for this surprising phenomenon.
In chapter entitled "Minimal Infeasible Subsystems and Benders cuts", taking inspiration from general cutting plane methods for MIP, we propose alternative selection criteria for Benders cuts, and analyze them computationally. Our approach is based on the correspondence between minimal infeasible subsystems of an infeasible Linear Program, and the vertices of the so-called alternative polyhedron. The choice of the "most effective" violated Benders cut then corresponds to the selection of a suitable vertex of the alternative polyhedron, hence a clever choice of the dual objective function is crucial--whereas the textbook Benders approach uses a completely random selection policy, at least when the so-called feasibility cuts are generated. Computational results on a testbed of MIPLIB instances are presented. We show that the proposed methods allow for a speedup of 1 to 2 orders of magnitude with respect to a textbook implementation.
In chapter entitled "Fast Approaches to Improve the Robustness of a Railway Timetable", we address the problem of finding a robust train timetable. The Train Timetabling Problem (TTP) consists in finding a train schedule on a railway network that satisfies some operational
constraints and maximizes some profit function which counts for the efficiency of the infrastructure usage. In practical cases, however, the maximization of the objective function is not enough and one calls for a robust solution that is capable of absorbing as much as possible delays/disturbances on the network. We propose and analyze computationally four different methods to improve the robustness of a given TTP solution. The approaches combine Linear Programming (LP) and ad-hoc Stochastic Programming/Robust Optimization techniques. The computational results on real-world instances show that two of the proposed techniques are very fast and provide robust solutions of comparable quality with respect to the standard (but very time consuming) Stochastic Programming approach.

Abstract (italiano)

Nel presente lavoro di tesi descriviamo i nostri contributi su tre argomenti di Mixed Integer Programming (MIP).
Nel capitolo intitolato "Lexicography and degeneracy: Can a pure cutting plane algorithm work?" discutiamo una implementazione della versione lessicografica del metodo dei piani di taglio di Gomory per problemi di Integer Linear Programming (ILP) e due euristiche. Nei test computazionali su una batteria di istanze della libreria MIPLIB confrontiamo la performance dei metodi implementati col l'algoritmo standard di Gomory, sia nella versione a singolo taglio che nella versione multi taglio (round di tagli), e mostriamo che le nostre implementazioni producono un miglioramento radicale sulla procedura standard. In particolare riportiamo la soluzione esatta di istanze ILP come stein15, stein27 e bm23, per le quali l'algoritmo standard di Gomory non è in grado di chiudere se non una piccola frazione del gap di integralità. Inoltre forniamo un'interpretazione di questo sorprendente fenomeno.
Nel capitolo intitolato "Minimal Infeasible Subsystems and Benders cuts", prendendo ispirazione dai metodi cutting plane generalmente usati in MIP, proponiamo nuovi criteri di selezione per i tagli di Benders, e li analizziamo computazionalmente. Il nostro approccio si basa sulla corrispondenza tra sistemi minimamente infeasible di un problema lineare infeasible, e i vertici del così detto poliedro delle alternative. La scelta del taglio di Benders violato "più efficace" corrisponde quindi alla selezione di un vertice opportuno nel poliedro delle alternative, da cui segue che è cruciale una scelta intelligente della funzione obiettivo duale--mentre l'approccio di Benders textbook usa una politica di scelta completamente casuale. Nei test computazionali mostriamo che il metodo proposto consente uno speedup da 1 a 2 ordini di grandezza rispetto all'implementazione textbook.
Nel capitolo intitolato "Fast Approaches to Improve the Robustness of a Railway Timetable", ci occupiamo del problema di trovare una tabella oraria robusta in ambito ferroviario. Il Train Timetabling Problem (TTP) consiste nel trovare uno schedule dei treni di una rete ferroviaria che soddisfi dei vincoli operativi e massimizzi una funzione di profitto che stimi l'efficienza dell'uso dell'infrastruttura. Tuttavia la massimizzazione della funzione obiettivo può non essere sufficiente e si può voler trovare una soluzione robusta, ovvero capace di assorbire il più possibile i ritardi/disturbi sulla rete. A tal fine, proponiamo e analizziamo computazionalmente quattro diversi metodi per migliorare la robustezza di una data soluzione di TTP. Gli approcci combinano Programmazione Lineare e tecniche ad-hoc di Stochastic Programming/Robust Optimization. I risultati computazionali su istanze reali mostrano che due delle tecniche proposte sono molto veloci e forniscono soluzioni robuste di qualità comparabile con un approccio di Stochastic Programming standard ma computazionalmente molto più oneroso.

Statistiche Download - Aggiungi a RefWorks
Tipo di EPrint:Tesi di dottorato
Relatore:Fischetti, Matteo
Dottorato (corsi e scuole):Ciclo 21 > Scuole per il 21simo ciclo > SCIENZE MATEMATICHE > MATEMATICA COMPUTAZIONALE
Data di deposito della tesi:28 Gennaio 2009
Anno di Pubblicazione:Febbraio 2009
Parole chiave (italiano / inglese):Mixed Integer Programming. Cutting planes. Benders cuts. Robust Train Timetabling.
Settori scientifico-disciplinari MIUR:Area 01 - Scienze matematiche e informatiche > MAT/09 Ricerca operativa
Struttura di riferimento:Dipartimenti > Dipartimento di Matematica
Codice ID:1342
Depositato il:28 Gen 2009
Simple Metadata
Full Metadata
EndNote Format

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.

[1] A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Rev., 33:60?100, 1991. Cerca con Google

[2] T. Achterberg, T. Koch, and A. Martin. MIPLIB 2003. Operations Research Letters, 34(4):1–12, 2006. Cerca con Google

[3] E. Amaldi, M. E. Pfetsch, and L.E. Trotter Jr. On the maximum feasible subsystem problem, IISs and IIS-hypergraphs. Mathematical Programming, 95(3):533–554, 2003. Cerca con Google

[4] J. L. Arthur and A. Ravindran. PAGP, a partitioning algorithm for (linear) goal programming problems. ACM Trans. Math. Softw., 6(3):378–386, 1980. Cerca con Google

[5] A. Bachem and W. Kern. Linear Programming Duality. An Introduction to Oriented Matroids. Number 074 in Universitext. Springer, 1992. Cerca con Google

[6] E. Balas. Disjunctive programming: Properties of the convex hull of feasible points. Discrete Applied Mathematics, 89(1-3):3–44, December 1998. Cerca con Google

[7] E. Balas, S. Ceria, and G. Cornuéjols. Mixed 0-1 programming by lift-and-project in a branch-and-cut framework. Management Science, 42:1229–1246, 1996. Cerca con Google

[8] E. Balas, S. Ceria, G. Cornuéjols, and N. Natraj. Gomory cuts revisited. Operations Research Letters, 19:1–9, 1996. Cerca con Google

[9] M. L. Balinski and A. W. Tucker. Duality theory of linear programs: A constructive approach with applications. SIAM Review, 11(3):347–377, July 1969. Cerca con Google

[10] F. Barber, S. Cicerone, D. Delling, G. Di Stefano, M. Fischetti, L. Kroon, D. Salvagnin, P. Tormos, C. Weber, and A. Zanette. New frameworks for the interaction between robust and online timetable planning, and for monitoring the status quo of the system. Technical Report ARRIVAL-D3.4, ARRIVAL Project, 2008. Cerca con Google

[11] E. M. L. Beale. Survey of integer programming. OR, 16(2):219–228, jun 1965. Cerca con Google

[12] J.F. Benders. Partitioning procedures for solving mixed- variables programming problems. Numerische Mathematik, 4:238–252, Dec. 1962. Cerca con Google

[13] L. Bertacco. Exact and Heuristic Methods for Mixed Integer Linear Programs. PhD thesis, University of Padova, 2005. Cerca con Google

[14] John R. Birge and Francois Louveaux. Introduction to Stochastic Programming (Springer Series in Operations Research and Financial Engineering). Springer, 1st ed. 1997. corr. 2nd printing edition, 2000. Cerca con Google

[15] I. Borg and P.J.F. Groenen. Modern Multidimensional Scaling: Theory and Applications. Springer, 2005. Cerca con Google

[16] A. Caprara, M. Fischetti, and A. N. Letchford. On the separation of maximally violated mod-k cuts. In Proceedings of the 7th International IPCO Conference on Integer Programming and Combinatorial Optimization, pages 87–98, London, UK, 1999. Springer-Verlag. Cerca con Google

[17] A. Caprara, M. Fischetti, and P. Toth. Modeling and solving the train timetabling problem. Operations Research, 50(5):851–861, 2002. Cerca con Google

[18] A. Caprara, M. Monaci, P. Toth, and P.L. Guida. A lagrangian heuristic algorithm for a real-world train timetabling problem. Discrete Applied Mathematics, 154(5):738–753, 2006. Cerca con Google

[19] V. Chvátal. Edmonds polytopes and a hierarchy of combinatorial problems. Discrete Mathematics, 4:305–337, 1973. Cerca con Google

[20] Serafino Cicerone, Gianlorenzo D’Angelo, Gabriele Di Stefano, Daniele Frigioni, and Alfredo Navarra. On the interaction between robust timetable planning and delay management. Technical Report ARRIVAL-TR-0116, ARRIVAL project, 2007. Cerca con Google

[21] Charles E. Clark. Importance sampling in Monte Carlo analyses. Operations Research, 9(5):603–620, 1961. Cerca con Google

[22] W. Cook, S. Dash, R. Fukasawa, and M. Goycoolea. Numerically safe gomory mixed-integer cuts. 2008. Cerca con Google

[23] G. Cornuéjols. Valid inequalities for mixed integer linear programs. Math. Program., 112(1):3– 4, 2007. Cerca con Google

[24] G. Cornuéjols, L. Liberti, and G. Nannicini. Improved strategies for branching on general disjunctions. Optimization Online, 2008. Cerca con Google

[25] Balas E. and A. Saxena. Optimizing over the split closure. Mathematical Programming, DOI 10.1007/s10107-006-0049-5, 2006. Cerca con Google

[26] M. Fischetti and Lodi A. Optimizing over the first Chvátal closure. Mathematical Programming B, 110(1):3–20, 2007. Cerca con Google

[27] M. Fischetti, A. Lodi, and A. Tramontani. Experiments with disjunctive cuts. Technical report, November 2007. In preparation. Cerca con Google

[28] M. Fischetti and M. Monaci. Light robustness. Technical Report ARRIVAL-TR- 0119, ARRIVAL Project, 2008. Cerca con Google

[29] M. R. Garey and D. S. Johnson. Computers and Intractability, A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York, 1979. Cerca con Google

[30] R.S. Garfinkel and G.L. Nemhauser. Integer Programming. New York: John Wiley and Sons, 1972. Cerca con Google

[31] A. M. GEOFFRION. Lagrangian relaxation and its uses in integer programming. Mathematical Programming Study, 2:82–114, 1974. Cerca con Google

[32] Arthur M. Geoffrion. Generalized benders decomposition. Journal of Optimization Theory and Applications, 10:237–260, 1972. Cerca con Google

[33] Alex Orden George B. Dantzig and Philip Wolfe. The generalized simplex method for minimizing a linear form under linear inequality restraints. Pacific J. Math., 5(2):183–195, 1955. Cerca con Google

[34] J. Gleeson and J. Ryan. Identifying minimally infeasible subsystems of inequalities. ORSA Journal on Computing, 2(1):61–63, 1990. Cerca con Google

[35] R. E. Gomory. Outline of an algorithm for integer solutions to linear programs. Bulletin of the American Society, 64:275–278, 1958. Cerca con Google

[36] R. E. Gomory. An algorithm for the mixed integer problem. Technical Report RM-2597, The RAND Cooperation, 1960. Cerca con Google

[37] R. E. Gomory. An algorithm for integer solutions to linear programming. In R. L. Graves and P.Wolfe, editors, Recent Advances in Mathematical Programming, pages 269–302, New York, 1963. McGraw-Hill. Cerca con Google

[38] R. E. Gomory. Early integer programming. Operations Research, 50:78–81, Jan. - Feb. 2002. Cerca con Google

[39] Mads Hofman, Line Madsen, Julie Jespersen Groth, Jens Clausen, and Jesper Larsen. Robustness and recovery in train scheduling - a case study from DSB Stog a/s". In Riko Jacob and Matthias Müller-Hannemann, editors, ATMOS 2006 - 6th Workshop on Algorithmic Methods and Models for Optimization of Railways. Internationales Begegnungs- und Forschungszentrum fur Informatik (IBFI), Schloss Dagstuhl, Germany, 2006. Cerca con Google

[40] ILOG Inc. ILOG CPLEX 10.1 User’s Manual, 2007. Cerca con Google

[41] N. Karmarkar. A new polynomial-time algorithm for linear programming. Combinatorica, 4:373–395, 1984. Cerca con Google

[42] L. Khachian. A polynomial algorithm for linear programming. Doklady Akad Nauk USSR, 244(5):1093–1096, 1979. Cerca con Google

[43] L.G. Kroon, R. Dekker, and M.J.C.M. Vromans. Cyclic railway timetabling: a stochastic optimization approach. In Algorithmic Methods for Railway Optimization, Lecture Notes in Computer Science, pages 41–66. Springer Berlin / Heidelberg, 2007. Cerca con Google

[44] Adam N. Letchford and Andrea Lodi. Strengthening chvátal-gomory cuts and gomory fractional cuts. Operations Research Letters, 30:74–82, 2002. Cerca con Google

[45] C. Liebchen and L. W.P. Peeters. On cyclic timetabling and cycles in graphs. Technical Report 761-2002, TU Berlin, Mathematical Institute, 2002. Cerca con Google

[46] C. Liebchen and S.Stiller. Delay resistant timetabling. Technical Report ARRIVAL-TR-0056, ARRIVAL Project, 2006. Cerca con Google

[47] Christian Liebchen, Marco Lübbecke, Rolf H. Möhring, and Sebastian Stiller. Recoverable robustness. Technical Report ARRIVAL-TR-0066, ARRIVAL-Project, 2007. Cerca con Google

[48] Christian Liebchen, Michael Schachtebeck, Anita Schöbel, Sebastian Stiller, and André Prigge. Computing delay resistant railway timetables. Technical Report ARRIVAL-TR-0071, ARRIVAL Project, October 2007. Cerca con Google

[49] Jeff Linderoth, Alexander Shapiro, and Stephen Wright. The empirical behavior of sampling methods for stochastic programming. Annals of Operations Research, 142(1):215–241, February 2006. Cerca con Google

[50] W. L. Loh. On latin hypercube sampling. The Annals of Statistics, 24(5), 1996. Cerca con Google

[51] R. Lougee-Heimer. The common optimization interface for operations research: Promoting open-source software in the operations research community. IBM J. Res. Dev., 47(1):57–66, 2003. Cerca con Google

[52] A. Lodi M. Fischetti. Optimizing over the first Chvàtal closure. In M. Juenger and V. Kaibel, editors, Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science 3509, pages 12–22. Springer-Verlag Berlin Heidelberg, 2005. Cerca con Google

[53] T.L. Magnanti and R.T. Wong. Accelerating Benders decomposition: algorithmic enhancement and model selection criteria. Operations Research, 29:464–484, 1981. Cerca con Google

[54] H. Marchand, A. Martin, R. Weismantel, and L. Wolsey. Cutting planes in integer and mixed integer programming. Discrete Applied Mathematics, 123(1-3):397–446, November 2002. Cerca con Google

[55] H. Marchand and L.A. Wolsey. Aggregation and mixed integer rounding to solve mips. Papers 9839, Catholique de Louvain - Center for Operations Research and Economics, 1998. Cerca con Google

[56] F. Margot. Testing cut generators for mixed-integer linear programming. Optima, 77, 2008. Cerca con Google

[57] R. R. Meyer. On the existence of optimal solutions to integer and mixed integer programming problems. Mathematical Programming, 7:223–235, 1974. Cerca con Google

[58] P. Miliotis. Integer programming approaches to the travelling salesman problem. Mathematical Programming, 10:367–378, 1976. Cerca con Google

[59] P. Miliotis. Using cutting planes to solve the symmetric travelling salesman problem. Mathematical Programming, 15:177–178, 1978. Cerca con Google

[60] K. Nachtigall. Periodic network optimization and fixed interval timetables. Habilitation Thesis, Deutsches Zentrum für Luft-und Raumfahrt, Braunschweig, 1999. Cerca con Google

[61] G. Nemhauser and L. Wolsey. Integer and combinatorial optimization. Wiley, 1988. Cerca con Google

[62] L. W. P. Peeters. Cyclic Railway Timetable Optimization. PhD thesis, Erasmus University Rotterdam, 2003. Cerca con Google

[63] C. Poojari and J. Beasley. Improving Benders decomposition using a genetic algorithm. Technical report, 2006. Submitted to INFORMS Journal on Computing. Cerca con Google

[64] W. Rei, J. F. Cordeau, M. Gendreau, and P. Soriano. Accelerating Benders decomposition by local branching. Technical report, January 2006. To appear in INFORMS Journal on Computing, January 2006. Cerca con Google

[65] A. Ruszczynski and A. Shapiro, editors. Stochastic Programming (Hanbooks in Operations Research and Management Series). Elsevier Publishing Company, 2003. Cerca con Google

[66] A. Schrijver. Theory of linear and integer programming. John Wiley & Sons, Inc., New York, NY, USA, 1986. Cerca con Google

[67] P. Serafini and W. Ukovich. A mathematical model for periodic scheduling problems. SIJDM: SIAM Journal on Discrete Mathematics, 2, 1989. Cerca con Google

[68] A. Shapiro. Monte carlo sampling approach to stochastic programming. In ESAIM: Proceedings, volume 13, pages 65–73, December 2003. Cerca con Google

[69] M. Tamiz, D. F. Jones, and E. El-Darzi. A review of goal programming and its applications. Annals of Operations Research, (1):39–53, 1995. Cerca con Google

[70] T. Terlaky. Book review: Computational techniques of the simplex method. Computational Optimization and Applications, 26(2):209–210, November 2003. Cerca con Google

[71] B. Verweij, S. Ahmed, A. J. Kleywegt, G. Nemhauser, and A. Shapiro. The sample average approximation method applied to stochastic routing problems: A computational study. Computational and Applied Optimization, 24, 2003. Cerca con Google

Download statistics

Solo per lo Staff dell Archivio: Modifica questo record