8 Février - 14 Février


Retour à la vue des calendrier
Mardi 9 Février
Heure: 12:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Primal Heuristics for Branch-and-Price
Description: Francois Vanderbeck Math heuristics have become an essential component in mixed integer programming (MIP) solvers. Extending generic MIP heuristics, our study outlines generic procedures to build primal solutions in the context of a Branch-and-Price approach and reports on their performance. Rounding the linear relaxation solution of the Dantzig-Wolfe reformu-lation, which is typically tighter than that of the original compact formulation, sometimes produces better solutions than state-of-the-art specialised heuristics as revealed by our numerical experiments. We focus on the so-called diving methods and their combination with diversification-intensification paradigms such as Limited Discrepancy Search, sub-MIPing, relaxation induced neighbourhood search, local branching, and strong branching. The dynamic generation of variables inherent to a column generation approach requires specific adaptation of heuristic paradigms. Our contribution lies in proposing simple strategies to get around these technical issues. Our numerical results on Generalized Assignment, Cutting Stock, and Vertex Coloring problems sets new benchmarks, highlighting the performance of diving heuristics as generic procedures in a column generation context.
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: TBC
Description: Nicolas Basset
Jeudi 11 Février
Heure: 14:00 - 15:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Timed Aggregate Graph : a finite graph for model checking of Time Petri Nets
Description: Amal Chamakh Time Petri Nets (TPNs) are one of the most powerful formalisms for the
specification and the verification of systems involving explicit timing
constraints. To deal with model checking of timed systems modeled by TPNs, we
propose a new finite graph, called Timed Aggregate Graph (TAG), abstracting
the behavior of bounded TPNs with strong time semantics. The main feature of
this abstract representation compared to existing approaches is the encoding
of the time information. This is done in a pure way within each node of the
TAG allowing to compute the minimum and maximum elapsed time in every path of
the graph. The TAG preserves timed traces and reachable states of the
corresponding TPN and allows for on-the-fly verification of reachability
properties. We also introduce an algorithm for a modular construction of the
TAG, to better confine the state explosion problem.
Vendredi 12 Février
Heure: 11:00 - 12:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Hacking Nondeterminism with Induction and Coinduction
Description: Damien Pous Finite automata are used in a wide range of verification problems.
We introduce "bisimulation up to congruence" as a technique for
proving language equivalence of non-deterministic finite automata.
Exploiting this technique, we devise an optimisation of the classical
algorithm by Hopcroft and Karp which, as we show, is exploiting a
weaker "bisimulation up to equivalence" technique. The resulting
algorithm can be exponentially faster than the recently introduced
"antichain algorithms".