Sem 3 UAQ Optimisation (OLD)

Sem 3 UAQ Optimisation (OLD)

(to be discontinued - valid up to batch 2017)

Applications  @  UAQ  30 ECTS credits

Mathematical modelling and optimisation

The curriculum proposed by the University of L'Aquila (UAQ), "Mathematical Modelling and Optimisation" (MMO), provides students with strong mathematical foundations of data analytics and train them to their applications in complex decision making processes. The theoretical topics include basic equations of mathematical physics and nonlinear equations arising in traffic flows and fluid dynamics, stochastic processes, forecasting models, analysis and design of dynamic multi-agent networks. The curriculum emphasizes a comprehensive introduction to optimisation theory, including linear and non-linear optimisation, and deepen advanced topics in combinatorial and network optimisation and operations scheduling. The program also includes hands-on practice in the formulation, analysis and application of optimisation in science and engineering, along with computational training with state-of-the-art optimisation software.

Research interests of MMO faculty cover several areas of theoretical and computational Optimisation with long-standing partnerships with European and US institutions. Among them, the universities of Wisconsin-Madison, Lehigh (Pennsylvania), Lancaster (UK), Bilkent (TR). A well-established collaboration is also on-going with the IASI institute of Italian National Research Council (CNR). The Optimisation group in L'Aquila has a long tradition in the applications of data analytics and operations research in industry as well. Optimisation solutions have been developed is several fields, such as telecommunication,
manufacturing, operations and workforce management and logistics, in partnerships with important industrial and institutional players.

Below you can find information about the subjects for this semester.

Advanced analysis I [6 credits]

  • ECTS credits 6
  • University University of L'Aquila
  • Semester 3
  • Objectives

     

    The main objectives of the course are as follows:

    • to provide knowledge of mathematical methods that are widely used by researchers in the area of Applied Mathematics;
    • to apply this knowledge to a variety of topics, including the basic equations of mathematical physics and some current research topics about nonlinear equations (traffic flow, gas dynamics, fluid dynamics).
  • Topics

     

    • Measure and integration theory.
    • Functions of bounded variation.
    • Distributions theory.
    • Fourier transform. Sobolev spaces.
    • Application to the study of partial differential equations:
    • elliptic equations of second order, parabolic equations of second order, hyperbolic systems of first-order equations, nonlinear conservation laws.
    • An outline of semigroup theory.

Optimisation Models and Algorithms [6 credits]

  • ECTS credits 6
  • University University of L'Aquila
  • Semester 3
  • Objectives

     

     

  • Topics

     

     

    Introduction to optimization: linear, nonlinear and discrete optimization. Combinatorial optimization (CO) and its relation to linear programming (LP). Relevant CO problems, their 01 LP formulations and the universal algorithm.
    System of linear inequalities, projections, Fourier-Veronese’s Theorem, Fourier-Motzkin’s Method. Theorems of the alternative and duality theory in LP. Examples and interpretations.
    Matroids and the greedy algorithm. Rado’s Theorem. Trivial, graphic, vectorial, partition and matching matroid. Submodular set functions.
    Algorithms and bounds for special problems. Dynamic programming, examples of application to optimal paths and to knapsack. Shortest path and Dijkstra algorithm. Bipartite matching, algorithms for the unweighted and the weighted case.
    A general algorithm: branch-and-bound.
    Approximation algorithms. Examples: 01 knapsack and metric TSP.
    A real industrial application.

  • Prerequisites

     

    (short survey included in the course): elements of graph theory and of computational complexity

  • Books

     

    C.H. Papadimitriou, K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity (Dover Publications)
    Course slides and exercises freely available from the DISIM website

Process and Operations Scheduling [6 credits]

  • ECTS credits 6
  • University University of L'Aquila
  • Semester 3
  • Objectives

     

    Train the students in recognizing machine scheduling problems, classify them in terms of computational complexity and solve them by heuristic, approximation or exact algorithms.

    LEARNING OUTCOMES
    On successful completion of this course, the student should:

    • Acquire knowledge of Machine Scheduling problems, their classification in terms of computational complexity and algorithmic techniques developed for their solution. Acquire the fundamentals of optimization methods for project management.
    • Acquire the ability to recognize Machine Scheduling problems in different application contexts, such as computer science, industrial engineering and management, and to identify effective solution paradigms.
    • Acquire autonomy in modeling and algorithmic choices for complex problems related to scheduling and project management.
    • Being able to hold a conversation and to read texts on topics related to the modeling of scheduling problems and the evaluation of algorithms for their solution
    • Acquire skills upgrading flexible knowledge and skills in the field of scheduling problems that arise in various areas, such as computer science, industrial engineering and management
  • Topics

     

     

    Elements of a (deterministic) scheduling problem, examples of practical applications
    Classification of scheduling problems
    Integer Linear Programming formulations
    Single machine scheduling: computational complexity, heuristic and exact algoritms
    Parallel machine scheduling: exact, heuristic and approximation algorithms
    Relationships with basic Combinatorial Optimization problems
    Optimization problems in Project Scheduling
    Job Shop scheduling: formulations, heuristic and exact algorithms

  • Prerequisites

     

    Basic elements of computational complexity, linear programming and network flows

  • Books

     

    Michael Pinedo, Scheduling Theory, Algorithms, and Systems. Prentice Hall

Modelling and control of networked distributed systems [6 credits]

  • ECTS credits 6
  • University University of L'Aquila
  • Semester 3
  • Objectives

     

    The aim of this course is to provide basic knowledge of the analysis and design of dynamic multiagent networks

  • Topics

     

     

    • Introduction to graph theory: graphs; matrices representation; algebraic and spectral graph theory; graph symmetries.
    • The agreement protocol - the static case: undirected and directed networks; agreement and markov chains; the Factorization Lemma.
    • The agreement protocol - Lyapunov and LaSalle: agreement via Lyapunov functions, agreement over switching digraphs, edge agreement, generalizations to nonlinear systems.
    • Formation Control: formation specification-shapes and relative states; shape based control; relative state based control, dynamic formation selection, assigning roles.
    • Mobile Robots: Cooperative robotics; weighted graph based feedback; dynamic graphs; formation control revisited; the coverage problem.

     

  • Prerequisites

     

    Linear Algebra. Linear control systems. Stability theory for linear control systems

  • Books

     

    M. Mesbahi and M. Egerstedt, Graph Theoretic Methods in Multiagent Networks. Princeton University Press. 2010

Italian Language and Culture for Foreigners (level A2) [3 credits]

  • ECTS credits 3
  • University University of L'Aquila
  • Semester 1
  • Objectives

     

    Students will reach an elementary level of both written and spoken Italian (A2 level according to CEFR).

  • Books

     

    -Nuovo Espresso 1, Alma Edizioni, ISBN: 9788861823181

Optimisation in signal processing and wavelets [6 credits]

  • ECTS credits 6
  • University University of L'Aquila
  • Semester 3
  • Objectives

     

    The aim of the course is to introduce the main constructions of wavelets and frames, show their applications to the modern signal processing and to numerical algorithms, and consider optimization problems solved in that theory. The course provides students with all necessary tools from functional and harmonic analysis to construct and analyze systems of wavelets and with the methods of optimal control for the corresponding optimization problems.

  • Topics

     

    A short overview of the Fourier analysis. Direct and inverse theorems of the approximation theory. Discrete and fast Fourier transform. Haar, Shannon-Kotelnikov, and Meyer systems. The cascade algorithms for the wavelet transform. The noise analysis. Compactly supported wavelets and frames. Daubechies wavelets. Optimization problems in wavelets: the best approximation rates, the smallest support, the minimal uncertainty constants. Methods of optimal control. Calculus of variations and the Pontryagin maximum principle.

Home Sem 3 UAQ Optimisation (OLD)