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). |
|
|