Parcours Operations research, combinatorics and optimization (ORCO) 2e année

This course presents advanced methods and technics for Operations Research.

Reminder :

Linear Programming, Dynamic Programming, MIP modelling and BB
Complexity (P, NP, Co-NP)

Advanced MIP :

formulation, cuts, bounds
applications
lagragian relaxation
column generation
Benders decomposition
Solvers

Constraint Programming

Heuristics

local search
approximation algorithms

Voir la page complète

The aim of this course is to provide a broad knowledge of fundamental problems in Combinatorial Optimization to show their algorithmic solutions and to derive min-max results on them. In order to achieve this goal a new object called a polyhedron is introduced. This polyhedral approach helps to shed new light on some classic results of Combinatorial Optimization.

Syllabus: Study of polyhedra associated to problems of Combinatorial Optimization ; Theory of blocking polyhedra ; Connectivity: shortest paths, spanning trees and spanning arborescences of minimum weight ; Flows: Edmonds-Karp Algorithm, Goldberg-Tarjan Algorithm, minimum cost flows ; Matchings: Hungarian method, Edmonds' Algorithm, Chinese postman problem; Matroids: greedy algorithm, intersection of two matroids ; Graph coloring ; Applications coming from various areas of Operations Research.

Voir la page complète

The objective of this course is to present different techniques to handle uncertainty in decision problems. These techniques will be illustrated on several applications e.g. inventory control, scheduling, energy, machine learning.

https://moodle.caseine.org/course/view.php?id=1084

Voir la page complète

Voir la page complète

The aim of this course is to learn how to use the structure of graphs and other discrete objects to obtain general results on them, and in particular efficient algorithms solving important problems.

We will cover the following topics:

• Structural Graph Theory: we will study the structure of important graph classes with nice algorithmic properties (planar graphs, interval graphs, comparability graphs, ...) and show several concrete problems that can be solved thanks to their structural properties.
• Graph Drawing: with the rise of Big Data, representing huge data sets is a fundamental challenge. Efficient ways to represent large graphs will be presented.
• Codes: we will see various codes (dominating, locating, identifying, ...) in graphs and their applications.
• Extremal combinatorics: the typical question in this field is "what global condition do we need to impose in some graph in order to make sure that some nice structure appears locally?" We will introduce a powerful tool called "the probabilistic method", an show how it can be applied to solve problems in this important area of research.

Voir la page complète

Voir la page complète

Voir la page complète

This course offers the possibility for the students to gain some experience by facing open/difficult combinatorial problems.

The goal is to model and solve a combinatorial problem with direct industrial applications. We expect the students to take a variety of approaches (local search, compact/extended linear programming formulations, constraint programming, ...) and establish useful results (lower bounds, cuts, complexity,...).

The experimental results will be compared to the litterature (a known academic open benchmark will be available in this case) or will be validated by the industrial partner.

Voir la page complète

Presenting models and tools for solving problems of company location and transport management in a supply chain.

Description:

This course presents two aspects: strategic design of a distribution network in a supply chain and tactical-operational aspects of network management.

For each aspect the course develops two key points:

• in network design, the choice of location and the establishment of services (production site, warehouse, logistics platform) and the synthesis of the transport network (connections / roads between production sites, warehouses, logistics centres)
• in network management, planning and modes of distribution transport (planning delivery rounds, number and types of vehicles).

For each of the three problem areas: location, delivery rounds and network design, students will study both modelling and techniques for accurate resolution (Branch-and-Bound) plus techniques for approximate resolutions (Lagrangian relaxation , metaheuristics) and how they are set up in commercial software (OPL-CPLEX Studio, Excel solver), or free software (COIN, lp-solve) or ad-hoc.

Evaluation :

Individual written exam (1/2 of the final mark) and group project (1/2 of the final mark).

Voir la page complète

This course introduces the field of MAS, various theoretical aspects (agent architectures, reasoning, interactions, game theory, social choice, etc), as well as practical applications from recent research. The focus is mostly on agent-based social simulation, and how to integrate psychological aspects in agents (so-called “human factors”: emotions, biases…) to make them more human-like and realistic. Applications discussed include epidemics modelling, computational economy, crisis management, urban planning, serious games, etc. The practical part of the course comprises several tutorials with various agent-based modelling platforms (in particular GAMA and Netlogo), scientific papers discussions, and analysis and/or extension of existing models. 

Voir la page complète

Voir la page complète

Voir la page complète

The course present the main cryptographic primitives and security protocols, focusing on security parameters and properties.

Pedagogical goals:

- generic cryptographic primitives: one-way, trap-door and hash functions; random generators; symmetric and assymertic cipher; interactive protocols;

- security properties : complexity and reduction proofs; undistinguidhability; non-malleability; soundness, completeness and zero-knowledge; confidentiality; authentication; privacy; non-repudiation

- use, deployment and integration of protocols in standard crypro lib (eg open-ssl)

- security proofs : fundations and verification based on tools (eg avispa)

Voir la page complète

Statistical learning is about the construction and study of systems that can automatically learn from data. With the emergence of massive datasets commonly encountered today, the need for powerful machine learning is of acute importance. Examples of successful applications include effective web search, anti-spam software, computer vision, robotics, practical speech recognition, and a deeper understanding of the human genome. This course gives an introduction to this exciting field. In the first part, we will introduce basic techniques such as logistic regression, multilayer perceptrons, nearest neighbor approaches, both from a theoretical and methodological point of views. In the second part, we will focus on more advanced techniques such as kernel methods, which is a versatile tool to represent data, in combination with (un)supervised learning techniques that are agnostic to the type of data that is learned from. The learning techniques that will be covered include regression, classification, clustering and dimension reduction. We will cover both the theoretical underpinnings of kernels, as well as a series of kernels that are important in practical applications. Finally we will touch upon topics of active research, such as large-scale kernel methods and the use of kernel methods to develop theoretical foundations of deep learning models.

Voir la page complète

Machine Learning is one of the key areas of Artificial Intelligence and it concerns the study and the development of quantitative models that enables a computer to perform tasks without being explicitly programmed to do them. Learning in this context is hence to recognize complex forms and to make intelligent decisions. Given all existing entries, the difficulty of this task lies in the fact that all possible decisions is usually very complex to enumerate. To get around that, machine learning algorithms are designed in order to gain knowledge on the problem to be addressed based on a limited set of observed data extracted from this problem. To illustrate this principle, consider the supervised learning task, where the prediction function, which infers a predicted output for a given input, is learned over a finite set of labeled training examples, where each instance of this set is a pair constituted of a vector characterizing an observation in a given vector space, and an associated desired response for that instance (also called desired output). After the training step, the function returned by the algorithm is sought to give predictions on new examples, which have not been used in the learning process, with the lowest probability of error. The underlying assumption in this case is that the examples are, in general, representative of the prediction problem on which the function will be applied. We expect that the learning algorithm produces a function that will have a good generalization performance and not the one that is able to perfectly reproduce the outputs associated to the training examples. Guarantees of learnability of this process were studied in the theory of machine learning largely initiated by Vladimir Vapnik. These guarantees are dependent on the size of the training set and the complexity of the class of functions where the algorithm searches for the prediction function. Emerging technologies, particularly those related to the development of Internet, reshaped the domain of machine learning with new learning frameworks that have been studied to better tackle the related problems. One of these frameworks concerns the problem of learning with partially labeled data, or semi-supervised learning, which development is motivated by the effort that has to be made to construct labeled training sets for some problems, while large amount of unlabeled data can be gathered easily for these problems. The inherent assumption, in this case, is that unlabeled data contain relevant information about the task that has to be solved, and that it is a natural idea to try to extract this information so as to provide the learning algorithm more evidence. From these facts were born a number of works that intended to use a small amount of labeled data simultaneously with a large amount of unlabeled data to learn a prediction function.

The intent of this course is to propose a broad introduction to the field of Machine Learning, including discussions of each of the major frameworks, supervised, unsupervised, semi-supervised and reinforcement learning.

Voir la page complète

Causality is at the core of our vision of the world and of the way we reason. It has long been recognized as an important concept and was already mentioned in the ancient Hindu scriptures: “Cause is the effect concealed, effect is the cause revealed”. Even Democritus famously proclaimed that he would rather discover a causal relation than be the king of presumably the wealthiest empire of his time. Nowadays, causality is seen as an ideal way to explain observed phenomena and to provide tools to reason on possible outcomes of interventions and what-if experiments, which are central to counterfactual reasoning, as ‘‘what if this patient had been given this particular treatment?’’

Voir la page complète

This course is related to mathematical and statistical methods which are very used in supervised learning.

It contains two parts.

In the first part, we will focus on parametric modeling. Starting with the classical linear regression, we will describe several families of estimators that work when considering high-dimensional data, where the classical least square estimator does not work. Model selection and model assessment will particularly be described.

In the second part, we shall focus on nonparametric methods. We will present several tools and ingredients to predict the future value of a variable. We shall focus on methods for non parametric regression from independent to correlated training dataset. We shall also study some methods to avoid the overfitting in supervised learning.

This course will be followed by practical sessions with the R software.

Voir la page complète

This course deals with

• Topic 1: convex analysis

• Topic 2: convex programming

• Basic notions: vector space, affine space, metric, topology, symmetry groups, linear and affine hulls, interior and closure, boundary, relative interior

• Convex sets: definition, invariance properties, polyhedral sets and polytopes, simplices, convex hull, inner and outer description, algebraic properties, separation, supporting hyperplanes, extreme and exposed points, recession cone, Carathéodory number, convex cones, conic hull

• Convex functions: level sets, support functions, sub-gradients, quasi-convex functions, self-concordant functions

• Duality: dual vector space, conic duality, polar set, Legendre transform

• Optimization problems: classification, convex programs, constraints, objective, feasibility, optimality, boundedness, duality

• Linear programming: Farkas lemma, alternative, duality, simplex method

• Algorithms: 1-dimensional minimization, Ellipsoid method, gradient descent methods, 2nd order methods

• Conic programming: barriers, Hessian metric, duality, interior-point methods, universal barriers, homogeneous cones, symmetric cones, semi-definite programming

• Relaxations: rank 1 relaxations for quadratically constrained quadratic programs, Nesterovs π/2 theorem, S-lemma, Dines theorem Polynomial optimization: matrix-valued polynomials in one variable, Toeplitz and Hankel matrices, moments, SOS relaxations

Voir la page complète

Interactive Information Visualization (InfoVis)

InfoVis is the study of interactive graphical representations of abstract data (e.g. graphs linking people in social networks, series of stock options values evolving over time).

Graphical representations are a powerfull way to leverage the human perceptual capabilities to allow the user to explore and make sense of abstract data, and also to expose findings and convey ideas.

But to be efficient, a visualization has to be designed using knowledge about the human visual perception, the characteristics of the data, the kind of task that will be performed on those data.

The aim of this course is to provide the keys, both theoretical and practical, to build usable and useful interactive visualizations.

program summary:

- foundations: human visual perception, graphical variables, data types, the visualization pipeline.

- linked data: tree and graph visualization

- tabular data: time series and spatial data visualization

- dealing with large data: aggregation, multiple views, interaction

- validating visualization: visualization tasks, evaluation

Voir la page complète

In this course, we will introduce parallel programming paradigms to the students in the context of applied mathematics. The students will learn to identify the parallel pattern in numerical algorithm. The key components that the course will focus on are : efficiency, scalability, parallel pattern, comparison of parallel algorithms, operational intensity and emerging programming paradigm. Trough different lab assignments, the students will apply the concepts of efficient parallel programming using Graphic Processing Unit. In the final project, the students will have the possibility to parallelize one of their own numerical application developed in a previous course.

1. Introduction to parallelism
2. Introduction to general context of parallelism
3. Models of parallel programming
4. Description of various model of parallelism
5. Paradigm of parallelism
6. Templates of parallelism
7. Parallel architectures
8. Programming tools: Cuda

Voir la page complète

Robots are mechatronic systems with perception, decision and action capabilities, they are designed to perform different tasks in an autonomous way in the real world. Born in the 50s, Robotics is a driving force in the world economy, fostering innovation, enhancing productivity, creating high-tech jobs, and contributing to the global competitiveness of nations and industries. As technology continues to evolve, the role of robotics is likely to expand across diverse sectors, further shaping the economic landscape. Thanks to recent technological progress (AI in particular), it is expected that robots will increasingly be present in our daily lives for service and assistance. Robotics is considered an imminent technological and societal revolution and the "France 2030" investment plan has earmarked 800 millions Euros for Robotics alone (https://www.economie.gouv.fr/france-2030).

The integration of AI into robotics has been a gradual process but it has been transformative. The adoption of deep learning techniques since the mid-2010s revolutionized perception in robotics. Computer vision systems have become more sophisticated, enabling robots to recognize and understand visual information with unprecedented accuracy. More recently, Reinforcement Learning has gained prominence, allowing robots to learn through trial and error. This approach is particularly powerful for training robots to perform complex tasks, such as manipulation and navigation, in dynamic environments.

However, making intelligent decisions remains an elusive goal and several challenges remains to be solved. To that end, it is crucial for AI system designers to understand the core concepts of Robotics. Robotics is inherently interdisciplinary, it involves hardware and software components that need to be integrated seamlessly which poses practical challenges and constraints. Robotics involves working with various sensors whose information is crucial for decision-making. AI system designers need to understand how these sensors work and their limitations. Robotics also involves designing and implementing control systems to ensure precise and accurate movements. This includes understanding feedback control, kinematics, and dynamics. In summary, a solid understanding of Robotics is integral for AI system designers because it provides a broader perspective, practical insights, and hands-on experience that can enhance their ability to design, implement, and optimize AI systems for real-world applications.

Voir la page complète

This course provides an overview of cloud computing principles, building blocks and applications.

Over the past 15 years, the emergence of cloud computing infrastructures has fundamentally impacted the way to design and deploy software, in most application domains. At the core of IT infrastructures, cloud computing is today the main platform for implementing and deploying robust, scalable, potentially geo-distributed, elastic applications. Together with DevOps methods, it allows IT companies to rapidly deliver reliable software.

The course studies :

• The low-level mechanisms enabling the cost-efficiency, performance, scalability and resilience of cloud infrastructures,
• The software design principles involved in the construction of (distributed) cloud applications,
• The cloud services facilitating the implementation of cloud-native applications.

Through lectures, practical sessions, and the study of recent research publications (from academia and industry), students will learn about the core principles and usage of:

• Virtualization technologies (hypervisors, kernels, and containers) enabling flexible, efficient, safe and secure hosting of code and data on a shared hardware and software infrastructure;
• The fundamental aspects of cloud infrastructures, services, and design patterns for the construction of efficient, scalable and resilient distributed applications;
• Microservice architectures, allowing organizations to design, develop and manage complex software services in an extremely modular way.

Voir la page complète

The automatic processing of languages, whether written or spoken, has always been an essential part of artificial intelligence. This domain has encouraged the emergence of new uses thanks to the arrival in the industrial field of many technologies from research (spell-checkers, speech synthesis, speech recognition, machine translation, …). In this course, we present the most recent advances and challenges for research. We will discuss discourse analysis whether written or spoken, text clarification, automatic speech transcription and automatic translation, in particular recent advances with neural models.

Information access and retrieval is now ubiquitous in everyday life through search engines, recommendation systems, or technological and commercial surveillance, in many application domains either general or specific like health for instance. In this course, we will cover Information retrieval basics, information retrieval evaluation, models for information retrieval, medical information retrieval, and deep learning for multimedia indexing and retrieval

Voir la page complète

Course content

Part 1: Access Control, or how to prevent unauthorized people from entering or accessing a system?

This part deals with:

• Cryptology for authentication and trust;
  • security needs : confidentiality, availability, integrity, non-repudiation (CAI/DICP);
  • cryptology primitives : private and public key ; trusted infrastructure (PKI and ledgers).
  • zero-knowledge protocols; secret sharing and multiparty computation / or Practical work with Open SSL
• Access control mechanisms (MAC, DAC, RBAC, ABAC) and their implementations
• The detection and remediation of security breaches such as intrusions and insider attacks
• The deployment of control filters in applications and proxies.

The presented approach is built on the model-driven security paradigm (MDS). It refers to the process of modeling security requirements at a high level of abstraction, and generating technical security implementations. Security models are transformed into enforceable security rules including the run-time security management (e.g. entitlements/authorisations). Three labs are planned:

• B4MSecure: we will apply a formal language with animation and model-checking facilities to identify security breaches in Access Control policies.
• Snort: in this practical session you will set a local environment to simulate two machines, the target machine and the attacker. You will learn how to create firewall rules, monitor your network and how to react when an attack is detected.
• Metasploit: you will discover technology intelligence for vulnerabilities through a practical session where you will reproduce an exploit to hack and take control over a web-based server.

Part 2: Overview of modern attacks on systems, protocols, and networks and countermeasures

This part is devoted to modern attacks carried out on the Internet scale, in particular attacks on the DNS system (Domain Name System), such as cache or zone poisoning attacks, reflection and amplification of DDoS attacks (Distributed Denial of Service), IP spoofing - the root cause of DDoS attacks, botnets (e.g., Mirai), domain generation algorithms used for command-and-control communications, modern malware (e.g., Emotet trojan, Avalanche), spam, phishing, and business email compromise (BEC) scams.

The module will discuss preventative measures and security protocols to fight modern attacks, such as DDoS protection services, IP source address validation (SAV) known as BCP 38, Sender Policy Framework, and DMARC protocols as the first line of defense against email spoofing and BEC fraud, and DNSSEC to prevent DNS manipulation attacks. It will also discuss large-scale vulnerability measurements (a case study of the zone poisoning attack) and the challenges of deploying current security technologies by the system and network operators.

This part will be concluded with a practical team assignment in which students will be divided into groups and will have to configure a secure system in a real-world environment. The goal is to secure their system against the various types of discussed attacks and exploit other groups' systems.

Voir la page complète

Information processing capabilities from the computer side seem to be almost limitless now. However, these capabilities are only useful if users can easily and efficiently express their needs and obtain results. This course addresses Human-Computer Interaction as the process of optimizing humans' sensorimotor capabilities to maximize the communication bandwidth. We review current research on:

• User's sensorimotor capabilities
• Modeling human-computer interaction bandwidth
• Novels forms of efficient HCI:
  • AR, Handheld AR and head-mounted display AR
  • Interaction with non-anthropomorphic AI
  • Discoverability
  • Tangible & shape-changing interaction

Class schedule and notes

Voir la page complète

Voir la page complète

Voir la page complète

The objective of this course is to provide the principles of advanced (supervised and unsupervised) machine learning algorithms, and explain their interest when applying them to address learning tasks using visual, auditory or textual data, as well as multi-modal combinations. Description The course is split into two parts. During the first part, a wide range of machine learning algorithms will be discussed. The second part will focus on deep learning, and presentations more applied to the three data modalities and their combinations. The following is a non-exhaustive list of topics discussed:

• Computing dot products in high dimension & Page Rank
• Matrix completion/factorization (Stochastic Gradient Descent, SVD)
• Monte-carlo, MCMC methods: Metropolis-Hastings and Gibbs Sampling
• Unsupervised classification: Partitionning, Hierarchical, Kernel and Spectral clustering
• Alignment and matching algorithms (local/global, pairwise/multiple), dynamic programming, Hungarian algorithm,…
• Introduction to Deep Learning concepts, including CNN, RNN, Metric learning
• Attention models: Self-attention, Transformers
• Auditory data: Representation, sound source localisation and separation.
• Natural language data: Representation, Seq2Seq, Word2Vec, Machine Translation, Pre-training strategies, Benchmarks and evaluation
• Visual data: image and video representation, recap of traditional features, state-of-the-art neural architectures for feature extraction
• Object detection and recognition, action recognition.
• Multimodal learning: audio-visual data representation, multimedia retrieval.
• Generative Adversarial Networks: Image-image translation, conditional generation

Voir la page complète

Voir la page complète

Voir la page complète

Cette UE est obligatoire pour les étudiant.e.s inscrit.e.s dans le PT MSTIC.
Elle est constituée d'une projet tutoré et d'un MOOC consacré à l'éthique de la Science. 

Voir la page complète

This course presents advanced methods and technics for Operations Research.

Reminder :

Linear Programming, Dynamic Programming, MIP modelling and BB
Complexity (P, NP, Co-NP)

Advanced MIP :

formulation, cuts, bounds
applications
lagragian relaxation
column generation
Benders decomposition
Solvers

Constraint Programming

Heuristics

local search
approximation algorithms

Voir la page complète

The aim of this course is to provide a broad knowledge of fundamental problems in Combinatorial Optimization to show their algorithmic solutions and to derive min-max results on them. In order to achieve this goal a new object called a polyhedron is introduced. This polyhedral approach helps to shed new light on some classic results of Combinatorial Optimization.

Syllabus: Study of polyhedra associated to problems of Combinatorial Optimization ; Theory of blocking polyhedra ; Connectivity: shortest paths, spanning trees and spanning arborescences of minimum weight ; Flows: Edmonds-Karp Algorithm, Goldberg-Tarjan Algorithm, minimum cost flows ; Matchings: Hungarian method, Edmonds' Algorithm, Chinese postman problem; Matroids: greedy algorithm, intersection of two matroids ; Graph coloring ; Applications coming from various areas of Operations Research.

Voir la page complète

The objective of this course is to present different techniques to handle uncertainty in decision problems. These techniques will be illustrated on several applications e.g. inventory control, scheduling, energy, machine learning.

https://moodle.caseine.org/course/view.php?id=1084

Voir la page complète

Voir la page complète

The aim of this course is to learn how to use the structure of graphs and other discrete objects to obtain general results on them, and in particular efficient algorithms solving important problems.

We will cover the following topics:

• Structural Graph Theory: we will study the structure of important graph classes with nice algorithmic properties (planar graphs, interval graphs, comparability graphs, ...) and show several concrete problems that can be solved thanks to their structural properties.
• Graph Drawing: with the rise of Big Data, representing huge data sets is a fundamental challenge. Efficient ways to represent large graphs will be presented.
• Codes: we will see various codes (dominating, locating, identifying, ...) in graphs and their applications.
• Extremal combinatorics: the typical question in this field is "what global condition do we need to impose in some graph in order to make sure that some nice structure appears locally?" We will introduce a powerful tool called "the probabilistic method", an show how it can be applied to solve problems in this important area of research.

Voir la page complète

Voir la page complète

Voir la page complète

This course offers the possibility for the students to gain some experience by facing open/difficult combinatorial problems.

The goal is to model and solve a combinatorial problem with direct industrial applications. We expect the students to take a variety of approaches (local search, compact/extended linear programming formulations, constraint programming, ...) and establish useful results (lower bounds, cuts, complexity,...).

The experimental results will be compared to the litterature (a known academic open benchmark will be available in this case) or will be validated by the industrial partner.

Voir la page complète

Presenting models and tools for solving problems of company location and transport management in a supply chain.

Description:

This course presents two aspects: strategic design of a distribution network in a supply chain and tactical-operational aspects of network management.

For each aspect the course develops two key points:

• in network design, the choice of location and the establishment of services (production site, warehouse, logistics platform) and the synthesis of the transport network (connections / roads between production sites, warehouses, logistics centres)
• in network management, planning and modes of distribution transport (planning delivery rounds, number and types of vehicles).

For each of the three problem areas: location, delivery rounds and network design, students will study both modelling and techniques for accurate resolution (Branch-and-Bound) plus techniques for approximate resolutions (Lagrangian relaxation , metaheuristics) and how they are set up in commercial software (OPL-CPLEX Studio, Excel solver), or free software (COIN, lp-solve) or ad-hoc.

Evaluation :

Individual written exam (1/2 of the final mark) and group project (1/2 of the final mark).

Voir la page complète

Voir la page complète