Welcome to the web page of the junior seminar of the LIPN
Here you can find every information about past and future seminars - room B107
Désirée Rigonat (DecisionBrain): "Optimising a large scale bike sharing system: the London experience".
The London Cycle Hire Scheme (LCHS), managed by Serco Group Plc, is one
of the largest bike sharing schemes in the world, with 815 stations and
over 13,000 bikes. Due to the size and utilisation rate of the system,
Serco faces a major challenge in ensuring adequate supply of bikes at
all locations at all times. Furthermore, the Transport for London (TfL),
which oversees the LCHS, has very strict service commitments, KPI
targets and associated financial penalties. To optimize the mamagement
of such a large scheme, DecisionBrain designed and provided a decision
support tool called the Distribution Planning Optimization (DPO) System.
DPO operates 24hours a day and tackles several complex problems:
forecasting the demand for bikes and docking points, finding the best
inventory levels for all stations at any given time so that demand is
satisfied, building a schedule for Serco operators that are employed in
bike redistribution in order to reach the said best inventory levels at
stations and finally building a schedule for operators in charge of
repairs and maintenance. In this talk, we will illustrate how the
aforementioned problems have been tackled and the solving algorithms
that have been developed. Thanks to DPO, Serco is now able to
consistently meet the service levels required by TfL and has improved
the overall quality and availability of the service, as reported by both
the Serco LCHS Operations team and actual LCHS utilisation data.
Thi Thanh Huyen Nguyen (LoVe): "Quasi optimal model checking for concurrent systems".
A dynamic partial order reduction (DPOR) algorithm is optimal when it always explores at most one representative per Mazurkiewicz trace. Existing literature suggests that the reduction obtained by the non-optimal, state-of-the-art Source-DPOR (SDPOR) algorithm is comparable to optimal DPOR. We show the first program with O(n) Mazurkiewicz traces where SDPOR explores O(2^n) redundant schedules.
We furthermore identify the cause of this blow-up as an NP-hard problem. Our main contribution is a new approach, called Quasi-Optimal POR, that can arbitrarily approximate an optimal exploration using a provided constant k. We also present parallelization of our QPOR to speed up the exploration using parallel resources.
We also present an implementation of our method in a new tool called Dpu using specialised data structures. Experiments with Dpu, including Debian packages, show that optimality is achieved with low values of k, outperforming state-of-the-art tools.
This meeting in particular will be an opportunity to know each other and to introduce ourselves. There will be a short talk from Emiliano (representative of the PhD students in the Board of the Lab - "Conseil de labo") on important infos about thesis and laboratory committee, and the presentation of the junior seminar guidelines. We will be open to suggestions in order to improve the junior seminars.
Emiliano Lancini (AOC): "Box-Total Dual Integrality and k-Edge Connectivity".
The concept of total dual integrality dates back to the works of Edmonds, Giles and Pulleyblank in the late 70's, and is strongly connected to min-max relations in combinatorial optimization.
In this work we show a characterization of series-parallel graphs in terms of box-total dual integrality of the k-edge-connected spanning subgraph polyhedron.
The system ${A}x\ge b$ is totally dual integral (TDI) if, for each integer vector c for which $\min \{c x:Ax\ge b\}$ is finite, there exists an integer optimal solution of $\max \{yb:yA = c,\, y \ge0\}$ such that:
$$\min \{c x:Ax\ge b\} = \max \{yb:yA=c, \,y \ge0\}.$$
It is known that every integer polyhedron can be described by a TDI system $Ax\ge b$ with $A$ and $b$ integer. The integrality of the TDI system is desirable because, then we have a min-max relation between combinatorial objects.
We are interested in the stronger property of box-TDIness. A system $ A x\ge b$ is called box-TDI if the system $Ax\ge b, \ell\le x \le u$ is TDI for all rational vectors $\ell$ and $u$.
A polyhedron that can be described by box-TDI system is called a box-TDI polyhedron.
This definition is motivated by the fact that any TDI system describing a box-TDI polyhedron is box-TDI.
The past few years, this property has received a renewed interest and several new box-TDI systems were discovered.
We prove that, for $k\ge2$, the k-edge-connected spanning subgraph polyhedron is a box-TDI polyhedron if and only if the graph is series-parallel. Moreover, in this case, we provide a box-TDI system with integer coefficients describing this polyhedron.
Mathias Ramparison (LoVe): "Timed automata with parametric updates".
Timed automata (TAs) represent a powerful formalism to model and verify systems where concurrency is mixed with hard timing constraints. However, they can seem limited when dealing with uncertain or unknown timing constants. Several parametric extensions were proposed in the literature, and the vast majority of them leads to the undecidability of the EF-emptiness problem: “is the set of valuations for which a given location is reachable empty?” Here, we study an extension of TAs where clocks can be updated to a parameter. While the EF- emptiness problem is undecidable for rational-valued parameters, it becomes PSPACE-complete for integer-valued parameters. In addition, exact synthesis of the parameter valuations set can be achieved. We also extend these two results to the EF-universality (“are all valuations such that a given location is reachable?”), AF-emptiness (“is the set of valuations for which a given location is unavoidable empty?”) and AF-universality (“are all valuations such that a given location is unavoidable?”) problems.
Issam Falih (A3): "Attributed Networks Clustering: Application to recommender systems".
Au cours de la dernière décennie, les graphes se sont révélés être un
outil efficace pour modéliser des systèmes complexes. La problématique
de détection de communautés est une tâche centrale dans l'analyse des
réseaux complexes. La majeure partie des travaux dans ce domaine
s'intéresse à la structure topologique des réseaux. Cependant, dans
plusieurs cas réels, les réseaux complexes ont un ensemble d'attributs
associé aux nœuds et/ou aux liens. Ces réseaux sont dites : "réseaux
attribués".
Mes activités de recherche sont basées principalement sur la détection
des communautés dans les réseaux attribués. Pour aborder ce problème,
nous nous sommes intéressés dans un premier temps aux attributs
relatifs aux liens, qui sont un cas particulier des réseaux
multiplexes. Un multiplexe est un modèle de graphe multi-relationnel
qui est souvent représenté par un graphe multi-couches. Chaque couche
contient le même ensemble de nœuds mais encode une relation
différente. Dans ces travaux, nous menons une étude comparative des
différentes approches de détection de communautés dans les réseaux
multiplexes. Cette étude est faite sur des réseaux réels. Ensuite,
nous proposons une nouvelle approche centrée graine pour la détection
de communautés dans les graphes multiplexes qui a nécessité la
redéfinition des métriques de bases des réseaux complexes au cas
multiplexe. Puis, nous présentons une approche de clustering dans les
réseaux attribués qui prend en considération à la fois les attributs
sur les nœuds et la structure topologique du réseau. La validation de
mes approches a été faite avec des indices internes et externes, mais
aussi par une validation guidée par un système de recommandation que
nous avons proposé et dont la détection de communautés est sa tâche
principale.
Tsinjo Rakotoarimalala (CALIN): "Recherche approchée de motif dans un texte".
On appelle boule de rayon k et de centre un mot u l'ensemble de tous les
mots à distance inférieure ou égale à k. On s'intéresse dans l'exposé à
la distance d'édition appelée aussi distance de Levenshtein. Quelle est
la taille de cette boule pour un mot de longueur m ? Cette question nous
intéresse pour en déduire la borne inférieure de la complexité en nombre
de caractères lus de la recherche approché de motif dans un texte dans
des certaines conditions.
Xin YE (LoVe - formerly LCR): "Reachability Analysis of self modifying codes".
Self modifying code is code that modifies its own instructions during
execution time. It is nowadays widely used, especially in malware to make
the code hard to analyse and to detect by anti-viruses. Thus, the analysis
of such self modifying programs is a big challenge. Push-down systems
(PDSs) is a natural model that is extensively used for the analysis of
sequential programs because they allow to accurately model procedure calls
and mimic the program’s stack. In this work, we propose to extend the
PushDown System model with self-modifying rules. We call the new model
Self-Modifying PushDown System (SM-PDS). A SM-PDS is a PDS that can modify
its own set of transitions during execution. We show how SM-PDSs can be
used to naturally represent self-modifying programs and provide efficient
algorithms to compute the backward and forward reachable configurations of
SM-PDSs. We implemented our techniques in a tool and obtained encouraging
results. In particular, we successfully applied our tool for the detection
of self- modifying malware.
First junior seminar of the year 2017-2018: presentation of the junior seminar to new PhD students
Tsinjo Rakotoarimalala (CALIN): "La borne optimale de la recherche de plusieurs motifs dans un texte aléatoire".
En 1977, Andrew C. Yao dans "the complexity of pattern matching on random string" montre que toutes les occurrences de la plupart des motifs de longueur m se cherchent en $(n/m) ln(m)$ dans un texte aléatoire de longueur n. Nous généralisons la preuve de Yao 1977 pour des dictionnaires composés de plusieurs motifs.
L'idée est d'encadrer la complexité de l'algorithme optimal inconnu d'un coté on généralise un algorithme de Frédriksson et Grabrowski pour la borne supérieure et de l'autre coté on simplifie le problème et on généralise la méthode de Yao pour la borne inférieure. Le résultat principal est de montrer que la compexité de l'algorithme optimal est en $\theta ( n (\max (ln( s r_m m) /m + \frac{1}{s m_{min}} )))$ où $r_m$ est le nombre de motifs de longueur m dans le dictionnaire et $m_{min}$ est la longueur de plus court motif du dictionnaire.
Emiliano Lancini (AOC): "Multicuts in series parallel graphs and Box-TDIness".
summary (pdf)
Antoine Kaszczyc (LCR): "Typer les acteurs Akka".
Akka est un cadriciel de programmation concurrente. Il est composé d'entités appelés acteurs qui s'envoient des messages. Mon travail consiste à apporter des vérifications statiques aux programmes utilisant Akka. La technique utilisée est un typage assez simple utilisant un graphe. La propriété vérifiée est la possibilité de traitement de tout message envoyé.
Imad Kissami (AOC): "High Performance Computational Fluid Dynamics on Clusters and Clouds".
In order to run computational fluid dynamics (CFD) codes on large scale infrastructures, parallel computing has to be used because of the computational intensive nature of the problems. in this paper we investigate the adapt platform where we couple flow partial differential equationsand a poisson equation. This leads to a linear system which we solve using direct methods. The implementation deals with the mumps parallel multi-frontal direct solver and mesh partitioning methods using METIS to improve the performance of the framework. We also investigate, in this paper, how the mesh partitioning methods are able to optimize the mesh cell distribution for the adapt solver.
Enrico Bettiol (AOC):
"Simplicial Decomposition for Large-Scale Quadratic Convex Programming"
keywords: minimisation of convex function, large scale, simplex, simplicial decomposition, pricing function
Presentation of the junior seminar, quick presentations (5 min) of subjects of thesis by PhD students of all teams.
© LIPN 2019 | Mentions légales
2