Materiale per il corso di Ottimizzazione Discreta

• 1 - Richiami di teoria della complessità
• 1a - Linear programming
• 1b - Bounds and relaxations
• 2a - Branch-and-bound
• 2b - Branch-and-bound example
• 3 - Pre-processing
• 4 - Balas algorithm
  
• 5a - Polyhedral combinatorics
• 5b - Gomory cuts
• 6 - General cutting planes for ILP and MILP
• 7 - Special cutting planes for ILP and MILP
• 8 - Lifting
• 9 - Gomory cuts in B&C for M0-1P
• 10 - B&C for TSP and ATSP
  
• 11 - Lagrangean relaxation
• 12 - Example: the Swath Segment Selection Problem
• 13 - The Held and Karp lower bound for the TSP
• 14 - Additive bounding
• 15 - Column generation
• 15b - Column generation (version 2)
  
• 16a - Column generation stabilization (dual cuts)
• 16b - Column generation stabilization
• 17a - Example: the multilevel generalized assignnment problem
• 17b - Example: the multi-depot heterogeneous vehicle routing problem with time windows
• 17c - Example: the two-dimensional level strip packing problem
• 17d - Example: the Multi-Weber problem
• 17e - Example: the Single-Source Capacitated Facility Location Problem
• 17f - Example: the Ordered Open-End Bin Packing Problem
• 17g - Example: the Multi-Depot Vehicle Routing Problem with Heterogeneous Fleet and Time Windows
  
• 18a - Dynamic programming for polynomial-time problems
• 18b - Dynamic programming for NP-hard problems
• 18c - Dynamic programming for LIFO rescheduling
  

• Using Glpsol with Gusek
• Example: Bin Packing Problem (model and data)
• The Set Covering Problem and Lagrangean relaxation
• The AMPL book
  
• Examples of Lagrangean relaxations with AMPL
  
• An exercise on column generation
• Examples of column generation with AMPL
• Dynamic programming exercises
• LR GAP in Excel
• LR SCP in Excel
  

• [2b] G. Righini, A branch-and-bound algorithm for the linear ordering problem with cumulative costs, European Journal of Operational Research 186 (2008) 965–971
• [3] Exercises on pre-processing
  
• [4] E. Balas, An Additive Algorithm for Solving Linear Programs with Zero-One Variables, Operations Research 13, 4 (1965) 517-546.
• [4] F. Glover, S. Zionts, A Note on the Additive Algorithm of Balas, Operations Research 13, 4 (1965) 546-549.
• [4] Lecture notes on Balas algorithm (Univ. of Iowa)
• [4] P.A. Jensen, J.F. Bard, Additive algorithm for the pure 0-1 integer programming, Operations Research Models and Methods, Wiley, 2003.
• [5] G. Cornuéjols, Revival of Gomory cuts in the 1990's, 2005
• [6] H. Marchand, A. Martin, R. Weismantel, L. Wolsey, Cutting planes in integer and mixed integer programming, Discrete Applied Mathematics 123 (2002) 397 – 446
• [10] 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.
• [10] J. Larsen, Branch and cut for TSP, Department of Management Engineering / Operations Research, Technical University of Denmark.
  
• [10] 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.
• [11] J.E. Beasley, Lagrangean relaxation, 1992
• [11] J.E. Beasley, An algorithm for the set covering problem, European Journal of Operational Research 31 (1987) 85-93
• [12] R. Cordone, F. Gandellini, G. Righini, Solving the swath segment selection problem through Lagrangean relaxation, Computers and OR 35 (2008) 854-862.
• [13] M. Held, R. Karp, The traveling-salesman problem and minimum spanning trees, Op. Res. 18 (1970) 1138-1162
  
• [14] M. Fischetti, P. Toth, An additive bounding procedure for combinatorial optimizazion problems, Op. Res. 1989
• [14] L. Diedolo, G. Righini, Additive bounding for the Double TSP with Multiple Stacks, ODS 2020.
• [15] J. Desrosiers, M.E. Luebbecke, A primer in column generation, 2005
• [16] T. Gschwind, S. Irnich, Dual inequalities for stabilized colummn generation revisited, INFORMS Journal on Computing 28 (2016) 175-194.
• [17] A. Ceselli, G. Righini, A branch-and-price algorithm for the multilevel generalized assignment problem, Operations Research 54 (2006) 1172-1184
• [17] A. Bettinelli, A. Ceselli, G. Righini, A branch-and-cut-and-price algorithm for the multi-depot heterogeneous vehicle routing problem with time windows, Transportation Research C 19 (2011) 723-740
• [17] A. Bettinelli, A. Ceselli, G. Righini, A branch-and-price algorithm for the two-dimensional level strip packing problem, 4OR 6 (2008) 361-374
• [18] 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
• [18] 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.
  
• [19] Nocedal, Wright, Numerical Optimization, 2006
• NP-completeness: alcune pagine tratte da Korte, Vygen, Combinatorial Optimization, Springer 2006.
  
• TCSS slides: esempio di applicazione del rilassamento Lagrangeano