2015


Retour à la vue des calendrier
Jeudi 2 Juillet
Heure: 12:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Solving the quadratic shortest path problem
Description: Borzou Rostami Finding the shortest path in a directed graph is one of the
most important combinatorial optimization problems, having applications
in a wide range of fields. In its basic version, however, the problem
fails to represent situations in which the value of the objective function
is determined not only by the choice of each single arc, but also
by the combined presence of pairs of arcs in the solution. In this paper
we model these situations as a Quadratic Shortest Path Problem, which
calls for the minimization of a quadratic objective function subject to
shortest-path constraints. We prove strong NP-hardness of the problem
and analyze polynomially solvable special cases, obtained by restricting
the distance of arc pairs in the graph that appear jointly in a quadratic
monomial of the objective function. Based on this special case and problem
structure, we devise fast lower bounding procedures for the general
problem and show computationally that they clearly outperform other
approaches proposed in the literature in terms of their strength.
Heure: 14:30 - 15:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Action synthesis for branching time logic: theory and applications
Description: Micha? Knapik Action-Restricted Computation Tree Logic (ARCTL) is a simple extension of CTL,
proposed by Pecheur and Raimondi, where the actions allowed along the considered
runs can be explicitly indicated by path selectors. ARCTL allows to
express properties
such as "a safe state is unavoidable for every path built from Forward
and Left actions",
denoted by AF{Forward,Safe}safe. By replacing the concrete sets of
actions with free
variables we obtain a parametric version of the logic pmARCTL, where
properties such
as AF{X}safe are allowed, where X is a parameter. We introduce a
fixed-point theory
that allows for the exhaustive synthesis of all the valuations of the
variables which make
the pmARTCL formulae hold in a given model. The theory has been
implemented in an
open source stand-alone tool and evaluated on scalable examples with
promising results.
Mardi 7 Juillet
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Nonlinear dynamics and complex systems [TBC]
Description: Joshua Socolar
Vendredi 24 Juillet
Heure: 11:00 - 12:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Monetary Economics Simulation: Stock-Flow Consistent Invariance, Monadic Style
Description: Antoine Kaszczyc
Mardi 8 Septembre
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Why and when does the half-normal distribution appear in combinatorics?
Description: Michael Wallner We present an extension of a theorem by Michael Drmota and Michèle Soria [1997] that can be used to identify the limiting distribution for a class of combinatorial schemata. This is achieved by determining analytical and algebraic properties of the associatedbivariate generating function. We give sufficient conditions implying a half-normal limiting distribution, extending the known conditions leading to either a Rayleigh, a Gaussian or a convolution of the last two distributions. Finally, we present some applications to lattice path and tree enumeration, images and preimages in random mappings.
Mardi 15 Septembre
Heure: 12:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: A branch-and-cut-and-price algorithm for the green vehicle routing problem with partial recharges and multiple technologies
Description: Alberto Ceselli
Abstract: We tackle a variation of the vehicle routing problem in which the transportation fleet is composed of electric vehicles with limited autonomy in need for recharge during the execution of their duties. Different technologies can be chosen at each station, offering different trade-off between recharge cost and time.

We present an algorithm exploiting column generation, cutting planes and branch-and-bound for the exact solution of the problem. The pricing phase requires elementary resource constrained shortest path problems to be solved, and is carried out with both heuristics and an exact dynamic programming routine. The cut separation phase is performed by running heuristics from the literature on a particular support graph.

Experiments on benchmark instances from the VRP literature reveal that our algorithm is effective in solving instances with up to thirty customers, nine recharge stations, five vehicles and three technologies to optimality.
Mercredi 23 Septembre
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: A fresh view on the matching problem (attention, c'est un mercredi)
Description: Sergio Caracciolo I will review some new results in the stochastic euclidean bipartitematching problem.First I will look at the simple one dimensional version, for whichmany exact results can be achieved. Afterwards, by discarding thediscrete nature of the problem, as usual in a critical system, I willshow how it is possible to resort to a continuous version for which ananalytical expression for the minimum cost and correlation functionscan be computed.
Heure: 14:00 - 16:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: A fresh view on the matching problem
Description: Sergio Caracciolo I will review some new results in the stochastic euclidean bipartite
matching problem.
First I will look at the simple one dimensional version, for which
many exact results can be achieved. Afterwards, by discarding the
discrete nature of the problem, as usual in a critical system, I will
show how it is possible to resort to a continuous version for which an
analytical expression for the minimum cost and correlation functions
can be computed.
Lundi 28 Septembre
Heure: 14:00 - 15:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Golfred: Génération de récits à partir d'expériences spatiales d'un robot de service par extraction de connaissances textuelles
Description: Jorge Garcia Flores Le but du projet est de donner à un robot la capacité de lire les phrases écrites qu'il rencontre sur son chemin et d'en faire un compte rendu à la fin de son parcours. Notre hypothèse est que la production de ce genre de récits est possible en embarquant le système de lecture automatique (machine reading) FRED dans le robot Golem (développé par l'équipe de Luis A. Pineda, professeur à l'IIMAS) et en adaptant le système de génération de texte RTGen (développé par l'équipe de Claire Gardent au LORIA). Le robot a la capacité de se déplacer dans le labo et de reconnaître les messages textuels, tandis que FRED est capable de chercher et d'interpréter des mots clés à partir de DBPedia, la base de données de Wikipedia. Enfin l'adaptation de RTgen aux données RDF de DBPedia permettra de transformer le graphe RDF construits par FRED en un texte décrivant le parcours de Golem. Le principal critère discursif pour la génération du récit est le parcours spatial: Golem (aidé par FRED et RTGen) raconte ce qu'il a lu sur son chemin (et trouvé sur Wikipedia).