- ECTS Credits: 6
- Semester: 1
- Year: 2
- Campus: University of Aveiro
- Language: English
- ECTS Credits: 2
- Semester: 2
- Year: 2
- Campus: Gdansk University of Technology
- Language: English
- Unit Coordinator: Fabrizio Rossi
- ECTS Credits: 6
- Semester: 2
- Year: 1
- Campus: University of L'Aquila
- Language: English
- Aims:
- Ability to recognize and model network optimization problems as Integer Linear Programming problems.
- Knowledge of fundamental algorithmic techniques for solving large scale Integer Linear Programming problems.
- Knowledge of commercial and open source Integer Linear Programming solvers.
- Content:
- Formulations of Integer and Binary Programs: The Assignment Problem; The Stable Set Problem; Set Covering, Packing and Partitioning; Minimum Spanning Tree; Traveling Salesperson Problem (TSP); Formulations of logical conditions.
- Mixed Integer Formulations: Modeling Fixed Costs; Uncapacitated Facility Location; Uncapacitated Lot Sizing; Discrete Alternatives; Disjunctive Formulations.
- Optimality, Relaxation and Bounds. Geometry of R^n: Linear and aune spaces; Polyhedra: dimension, representations, valid inequalities, faces, vertices and facets; Alternative (extended) formulations; Good and Ideal formulations.
- LP based branch-and-bound algorithm: Preprocessing, Branching strategies, Node and variable selection strategies, Primal heuristics.
- Cutting Planes algorithms. Valid inequalities. Automatic Reformulation: Gomory's Fractional Cutting Plane Algorithm. Strong valid inequalities: Cover inequalities, lifted cover inequalities; Clique inequalities; Subtour inequalities. Branch-and-cut algorithm.
- Software tools for Mixed Integer Programming.
- Lagrangian Duality: Lagrangian relaxation; Lagrangian heuristics.
- Network Problems: formulations and algorithms. Constrained Spanning Tree Problems; Constrained Shortest Path Problem; Multicommodity Flows; Symmetric and Asymmetric Traveling Salesman Problem; Vehicle Routing Problem Steiner Tree Problem; Network Design. Local Search Tabu search and Simulated Annealing MIP based heuristics.
- Heuristics for network problems: local search, tabu search, simulated annealing, MIP based heuristics.
- Reading list:
L.A. Wolsey, Integer Programming. Wiley. 1998.
- Code: DT0307
- Unit Coordinator: Raffaele D'Ambrosio, Carmen Scalone
- Programme: RealMaths
- ECTS Credits: 6
- Semester: 2
- Year: 1
- Campus: University of L'Aquila
- Language: English
- Delivery: In-class
- Aims:
Learning objectives.
The aim of the course is to provide knowledge and skills in the field of discretization of differential problems and skills in the analysis of theoretical properties and in the design of mathematical software based on the proposed numerical schemes.
Learning outcomes.
At the end of the course, each learner should:
- know the most relevant numerical methods for the approximation of differential equations, together with the aspects related to their implementation in an accurate and efficient mathematical software;
- understand and be able to explain notions, theses and proofs in the field of numerical mathematics for differential problems;
- be able to apply their knowledge to solve numerically, using a programming environment, differential problems;
- be able to read and understand other texts on related topics. - Content:
WELL POSEDNESS OF THE PROBLEM
Hadamard well-posed differential problems. Picard-Lindelof iterations, analysis of their convergence, long-term analysis. Existence and uniqueness of solutions. Continuous dependence on initial data and vector fields. Gronwall lemma. Examples of differential problems of interest in real applications.DIFFERENCE EQUATIONS
Linear difference equations. Space of solutions and its basis. Casorati matrix. General solution of homogeneous and inhomogeneous equations. Characteristic equations.ONE-STEP DISCRETIZATIONS
Discretization of the domain, numerical grids. Euler method. Consistency, zero-stability and convergence. Local truncation error. Trapezoidal method. Fixed point iterations for implicit schemes.LINEAR MULTISTEP METHODS
Multistep discretizations, starting procedure. First and second characteristic polynomials. Implicit methods and convergence analysis of fixed point iterations. Local truncation error. Linear difference operator. Consistency. Zero-stability and root condition. Convergence and order of convergence. Lax equivalence theorem. Methods arising from quadrature formulae. Adams-Bashforth and Adams-Moulton schemes. Dahlquist barriers.RUNGE-KUTTA METHODS
Definition and classification of Runge-Kutta methods. Order conditions. Butcher theory of order: B-trees, square bracket representation, order, symmetry and density; elementary differentials; elementary weights. B-series. Convergence analysis. Butcher barriers. Implicit methods: Gauss, Radau and Lobatto methods.LINEAR STABILITY ANALYSIS AND STIFF PROBLEMS
Dahlquist test problem. Linear stability analysis for linear multistep and Runge-Kutta methods. Regions and intervals of absolute stability. Stepsize restrictions. Boundary locus. A-stability, L-stability, A(alpha)-stability. Rational approximations of the exponential, Padé approximations. Stiff problems, stiffness ratio. A-priori Prothero-Robinson analysis.VARIABLE STEPSIZE IMPLEMENTATION
Predictor-corrector schemes. Error estimates. Stepsize control strategy: computation of the optimal stepsize, PI and PID controller. Newton iterations for implicit Runge-Kutta methods.GEOMETRIC NUMERICAL INTEGRATION
Numerical conservation of contractivity for dissipative problems. One-sided Lipschitz. Logarithmic norm. G-stability, B-stability, algebraic stability. Differential problems with first integrals. Conservation of linear invariants. Conservation of quadratic invariants. Symplectic Runge-Kutta methods. Hamiltonian problems: symplecticity of the flow, preservation of the Hamiltonian. Long-time behavior of symplectic methods to Hamiltonian problems. Modified differential equations. Benettin-Giorgilli theorem. - Pre-requisites:
Basic Numerical Analysis and differential equations.
- Reading list:
- R. D'Ambrosio, Numerical Approximation of Ordinary Differential Problems - From Deterministic to Stochastic Numerical Methods, Springer (2023).
- E. Hairer, C. Lubich, G. Wanner, Geometric Numerical Integration, Springer (2006).
