Materiale per il corso di Ottimizzazione Discreta

• 1 - Richiami di teoria della complessità
• 2a - Pre-processing
• 2b - Branch-and-bound
• 2c - Algoritmo di Balas
• 3a1 - Esempio di branch-and-bound: LOPCC
• 3a2 - Esempio di branch-and-bound: MLCO
  
• 3b - Bounds e rilassamenti
• 3c - Richiami di programmazione lineare
• 4a - Polyhedral combinatorics
• 4b - General cutting planes for ILP and MILP
• 5 - Special cutting planes for ILP and MILP
• 6a - Gomory cuts in B&C for M0-1P
• 6b - Lifting
• 7a - B&C for TSP and ATSP
• 7b - ATSP with precedence constraints
• 8a - MTZ formulation for the ATSP
• 8b - Interior point methods
• 9 - Lagrangean relaxation
• 11 - Example: the Swath Segment Selection Problem
• 11a - The Held and Karp lower bound for the TSP
• 11b - Additive bounds
• 12 - Column generation
• 13a - Examples on column generation
  
• 13b - Column generation stabilization
• 14 - Dynamic programming for polynomial-time problems
• 15a - Dynamic programming examples: LIFO rescheduling, order picking
• 16 - Dynamic programming for NP-hard problems

• Esercizi sul pre-processing
• Esercizio sull'algoritmo di Balas
• Esercizio sui tagli di Gomory (autore ignoto)
• The Set Covering Problem and Lagrangean relaxation
• LR GAP in Excel
• LR SCP in Excel
• Examples of Lagrangean relaxations with AMPL
  
• An exercise on column generation
• Esercizi sulla programmazione dinamica

• Examples of column generation with AMPL

• [2b] E. Balas, An Additive Algorithm for Solving Linear Programs with Zero-One Variables, Operations Research 13, 4 (1965) 517-546.
• [2b] F. Glover, S. Zionts, A Note on the Additive Algorithm of Balas, Operations Research 13, 4 (1965) 546-549.
• [2b] P.A. Jensen, J.F. Bard, Additive algorithm for the pure 0-1 integer programming, Operations Research Models and Methods, Wiley, 2003.
• [3a1] G. Righini, A branch-and-bound algorithm for the linear ordering problem with cumulative costs, European Journal of Operational Research 186 (2008) 965–971
• [4b] G. Cornuéjols, Revival of Gomory cuts in the 1990's, 2005
• [4b] H. Marchand, A. Martin, R. Weismantel, L. Wolsey, Cutting planes in integer and mixed integer programming, Discrete Applied Mathematics 123 (2002) 397 – 446
• [6a] E. Balas, S. Ceria, G. Cornuéjols, N. Natraj, Gomory cuts revisited, Operations Research Letters 19 (1996) 1-9
• [6] J.E. Mitchell, Branch-and-cut algorithms for combinatorial optimization problems, in Handbook of applied optimization, P.M. Pardalos and M.G.C. Resende eds., Oxford University Press, 2000.
• [7] J. Larsen, Branch and cut for TSP, Department of Management Engineering / Operations Research, Technical University of Denmark.
  
• [7] M. Fischetti, A. Lodi, P. Toth, Exact methods for the asymmetric traveling salesman problem, in The traveling salesman problem and its variations, G. Gutin and A. Punnen eds., Kluwer, 2002.
• [9] J.E. Beasley, Lagrangean relaxation, 1992
• [9] J.E. Beasley, An algorithm for the set covering problem, European Journal of Operational Research 31 (1987) 85-93
• [11] R. Cordone, F. Gandellini, G. Righini, Solving the swath segment selection problem through Lagrangean relaxation, Computers and OR 35 (2008) 854-862.
• [11a] M. Held, R. Karp, The traveling-salesman problem and minimum spanning trees, Op. Res. 18 (1970) 1138-1162
  
• [11a] T. Volgenant, R. Jonker, A branch-and-bound algorithm for the symmmetric traveling salesman problem base on the 1-tree relaxation, European Journal of Operational Research 9(1982) 83-89
• [11a] C.L. Valenzuela, A.J. Jones, Estimating the Held-Karp lower bound for the geometric TSP, European Journal of Operational Research 102 (1997) 157-175
  
• [11b] M. Fischetti, P. Toth, An additive bounding procedure for combinatorial optimizazion problems, Op. Res. 1989
• [11b] L. Diedolo, G. Righini, Additive bounding for the Double TSP with Multiple Stacks, ODS 2020.
  
• [12] J. Desrosiers, M.E. Luebbecke, A primer in column generation, 2005
• [13a] A. Ceselli, G. Righini, A Branch-and-Price Algorithm for the Multi-level Generalized Assignment Problem, Operations Research 54 (2006) 1172-1184
  
• [13a] A. Ceselli, F. Liberatore, G. Righini, A computational evaluation of a general branch-and-price framework for capacitated network location problems, Annals of Operations Research 167 (2009) 209-251
  
• [13a] G. Righini, L. Zaniboni, A branch-and-price algorithm for the multi-source Weber problem, International Journal of Operations Research 2 (2007) 188-207
  
• [15a] G. Nicosia, A. Pacifici, U. Pferschy, J. Resch, G. Righini, Optimally rescheduling jobs with a Last-In-First_out buffer, Journal of Scheduling 24 (2021) 663-680
• [15a] U. Pferschy, J. Resch, G. Righini, Algorithms for rescheduling jobs with a LIFO buffer to minimize the weighted number of late jobs, Journal of Scheduling 26, 3 (2023) 267-287
• [15a] M. Barbato, A. Ceselli, G. Righini, A polynomial-time dynamic programming algorithm for an optimal picking problem in automated warehouses, Journal of Scheduling 27 (2024) 393-407

• Using Glpsol with Gusek
• The AMPL book