{"id":990,"date":"2018-02-16T14:51:00","date_gmt":"2018-02-16T13:51:00","guid":{"rendered":"https:\/\/samovar2022.int-evry.fr\/index.php\/2018\/02\/16\/journee-optimisation-methodes\/"},"modified":"2020-09-04T18:45:47","modified_gmt":"2020-09-04T16:45:47","slug":"journee-optimisation-methodes","status":"publish","type":"post","link":"https:\/\/samovar.telecom-sudparis.eu\/index.php\/2018\/02\/16\/journee-optimisation-methodes\/","title":{"rendered":"Journ\u00e9e optimisation METHODES"},"content":{"rendered":"

Important :<\/strong> Dans le cadre du plan vigipirate et afin de faciliter l\u2019organisation de cette journ\u00e9e, vous devez obligatoirement vous inscrire au pr\u00e9alable en cliquant ici.<\/a><\/p>\n

Quand:<\/strong> Le lundi 5 mars 2018
\nO\u00f9:<\/strong> En salle H218, \u00e0 T\u00e9l\u00e9com SudParis<\/p>\n

Programme de la journ\u00e9e<\/strong><\/p>\n

– Accueil: 10h00<\/p>\n

– 10h30-11h10- Jos\u00e9 Neto, T\u00e9l\u00e9com SudParis
\nTitre : Approches pour le probl\u00e8me de coupe maximum<\/strong>
\nR\u00e9sum\u00e9 : \u00c9tant donn\u00e9 un graphe non orient\u00e9 et pond\u00e9r\u00e9 sur les ar\u00eates, le probl\u00e8me de coupe maximum consiste \u00e0 d\u00e9terminer un sous-ensemble de sommets S de sorte que la somme des poids des ar\u00eates ayant exactement une extr\u00e9mit\u00e9 dans cet ensemble soit maximum.
\nDiff\u00e9rents mod\u00e8les et m\u00e9thodes pour aborder ce probl\u00e8me notoirement difficile sont pr\u00e9sent\u00e9s. <\/p>\n

– 11h10-11h50 – Alain Faye, ENSIIE<\/a>
\nTitre : Un algorithme quadratique pour calculer les dates d\u2019atterrissage optimales d\u2019une s\u00e9quence d\u2019avions<\/strong>
\nR\u00e9sum\u00e9 : Ce papier \u00e9tudie le probl\u00e8me du s\u00e9quencement des avions lors de leur arriv\u00e9e \u00e0 l\u2019a\u00e9roport, probl\u00e8me connu dans la litt\u00e9rature sous le nom de Aircraft Landing Problem. Il s\u2019agit de s\u00e9quencer les avions arrivant sur la piste d\u2019atterrissage tout en respectant des conditions de s\u00e9curit\u00e9 entre les avions. Les avions cr\u00e9ent des turbulences et une dur\u00e9e minimum entre deux atterrissages successifs doit \u00eatre respect\u00e9e. La dur\u00e9e de s\u00e9paration d\u00e9pend du type des avions qui se suivent. Un petit avion qui atterrit derri\u00e8re un gros avion doit attendre plus longtemps qu\u2019un gros avion qui atterrit \u00e0 la suite d\u2019un petit. Chaque avion i peut atterrir dans une certaine fen\u00eatre de temps [Ei , Li ]. Ei est la date au plus t\u00f4t \u00e0 laquelle l\u2019avion peut atterrir, Li est la date au plus tard. Dans cette fen\u00eatre, Ti est la date pr\u00e9f\u00e9r\u00e9e d\u2019atterrissage qui correspond \u00e0 la date \u00e0 laquelle l\u2019avion arriverait sur la piste s\u2019il allait \u00e0 sa vitesse de croisi\u00e8re. Si l\u2019avion i \u00e9tait seul il atterrirait \u00e0 la date Ti mais en pr\u00e9sence d\u2019autres avions un arbitrage est n\u00e9cessaire. Les avions doivent soit acc\u00e9l\u00e9rer pour atterrir plus t\u00f4t ou au contraire ralentir voire faire des boucles pour arriver plus tard afin de respecter les contraintes de s\u00e9curit\u00e9. Une d\u00e9viation par rapport \u00e0 la date pr\u00e9f\u00e9r\u00e9e d\u2019atterrissage engendre un co\u00fbt lin\u00e9aire. L\u2019objectif est de minimiser le co\u00fbt total de d\u00e9viation. Sur chaque piste, le probl\u00e8me se d\u00e9compose en deux phases: d\u2019abord choisir l\u2019ordre des avions et ensuite choisir les dates d\u2019atterrisage. Ce dernier probl\u00e8me peut se r\u00e9soudre par un PL (Programme Lin\u00e9aire). Ici nous proposons un algorithme polynomial de complexit\u00e9 quadratique en fonction du nombre d\u2019avions. Cet algorithme est bas\u00e9 sur la programmation dynamique.
\nPour tester l\u2019efficacit\u00e9 de cet algorithme par rapport au PL, nous impl\u00e9mentons chaque m\u00e9thode dans un algorithme it\u00e9ratif de type recuit simul\u00e9. L\u2019algorithme it\u00e9ratif recherche la meilleure s\u00e9quence vis-\u00e0-vis de l\u2019objectif et le co\u00fbt d\u2019une s\u00e9quence est calcul\u00e9 soit par le PL dans une premi\u00e8re version de l\u2019algorithme, soit par l\u2019algorithme polynomial dans une deuxi\u00e8me version. Les deux algorithmes ont \u00e9t\u00e9 test\u00e9s sur des instances de la litt\u00e9rature, instances de 100 \u00e0 500 avions. L\u2019objectif de ces tests est d\u2019\u00e9valuer l\u2019apport de l\u2019algorithme polynomial par rapport au PL. Dans un premier temps, les vitesses des deux algorithmes ont \u00e9t\u00e9 compar\u00e9es.
\nOn constate le gain important apport\u00e9 par l\u2019algorithme polynomial. L\u2019algorithme polynomial est entre 7,8 et 9,8 fois plus rapide que le PL. Ce gain en rapidit\u00e9 permet \u00e0 l\u2019algorithme it\u00e9ratif, en un temps fix\u00e9, d\u2019obtenir de bien meilleures solutions lorsqu\u2019il utilise l\u2019algorithme polynomial.<\/p>\n

– 12h00-14h00- Pause d\u00e9jeuner<\/p>\n

-14h-14h30- Marc Castella, T\u00e9l\u00e9com SudParis<\/a>
\nTitre : Une approche d’optimisation globale pour la minimisation de crit\u00e8res rationnels favorisant la parcimonie<\/strong>
\nR\u00e9sum\u00e9: We consider the problem of recovering an unknown signal observed through a nonlinear model and corrupted with additive noise. More precisely, the nonlinear degradation consists of a convolution followed by a nonlinear rational transform. As a prior information, the original signal is assumed to be sparse. We tackle the problem by minimizing a least-squares fit criterion penalized by a Geman-McClure like potential. In order to find a globally optimal solution to this rational minimization
\nproblem, we transform it in a generalized moment problem, for which a hierarchy of semidefinite programming relaxations can be used. To overcome computational limitations on the number of involved variables, the structure of the problem is carefully addressed, yielding a sparse relaxation able to deal with up to several hundreds of optimized variables. Our experiments show the good performance of the proposed approach. <\/p>\n

14h30- 15h- Gilles Geeraerts, Universit\u00e9 Libre de Bruxelles<\/a>
\nTitre: \u00ab To reach or not to reach? Efficient Algorithms for total payoff games \u00bb<\/strong>
\nR\u00e9sum\u00e9: Quantitative games are two-player zero-sum games played on directed weighted graphs. Total-payoff games (that can be seen as a refinement of the well- studied mean-payoff games) are the variant where the payoff of a play is computed as the sum of the weights. We present the first pseudo-polynomial time algorithm for total-payoff games in the presence of arbitrary weights. It consists of a non-trivial application of the value iteration paradigm. Indeed, it requires to study, as a milestone, a refinement of these games, called min-cost reachability games, where we add a reachability objective to one of the players. For these games, we give an efficient value iteration algorithm to compute the values and optimal strategies (when they exist), that runs in pseudo-polynomial time. <\/p>\n

– 15h00-15h15: pause<\/p>\n

-15h15-15h45- Massinissa Merabet, Ph.D. in Computer Science, ENSIIE<\/a><\/p>\n

Titre : R\u00e9solution du probl\u00e8me de recherche d\u2019arbres couvrants ayant
\nun minimum de branchements<\/strong>
\nR\u00e9sum\u00e9 : \u00c9tant donn\u00e9 un graphe G = (V, E) non orient\u00e9, un sommet de G est dit sommet de branchement s\u2019il a un degr\u00e9 strictement sup\u00e9rieur \u00e0 deux. Le probl\u00e8me Minimum Branch Vertices (MBV) consiste \u00e0 trouver un arbre couvrant de G ayant un minimum de sommets de branchement. Il trouve son int\u00e9r\u00eat pratique principalement dans le routage Broadcast appliqu\u00e9 aux r\u00e9seaux optiques. En effet, \u00e9tant le sous-graphe connexe permettant de couvrir les sommets en utilisant un minimum de liens, l\u2019arbre est une structure classique pour ce type de routage. Dans les r\u00e9seaux tout-optique, les fonctions de commutation et de routage sont fournies par les brasseurs optiques OXC (optical cross-connect). Seuls certains OXC, on\u00e9reux, peuvent diviser une longueur d\u2019onde entrante vers plusieurs ports de sortie gr\u00e2ce \u00e0 un coupleur optique afin d\u2019offrir un service Broadcast. Cette division g\u00e9n\u00e8re un affaiblissement du faisceau lumineux ainsi qu\u2019une d\u00e9gradation du signal. Un sommet de branchement dans l\u2019arbre couvrant correspond a un sommet \u00e9quip\u00e9 de coupleur optique dans le r\u00e9seau. Afin de r\u00e9duire les co\u00fbts et de limiter les pertes, il convient donc de minimiser leur nombre, tout en garantissant la faisabilit\u00e9 du routage. Le probl\u00e8me MBV est NP-difficile et n\u2019est pas approximable en temps polynomial avec un rapport constant. Je propose une m\u00e9thode de r\u00e9solution exacte utilisant la programmation lin\u00e9aire en nombres entiers, un algorithme polynomial donnant une solution approch\u00e9e sans garantie, ainsi qu\u2019un noyau exponentiel de taille O(k2^k), o\u00f9 le param\u00e8tre k repr\u00e9sente
\nle nombre de sommets dont on ne peut d\u00e9cider en temps polynomial s\u2019ils sont sommets de branchement dans une solution optimale. L\u2019existence de ce noyau d\u00e9montre que ce probl\u00e8me est FPT vis-\u00e0-vis de k. Enfin, des exp\u00e9rimentations sur des graphes al\u00e9atoires permettront d\u2019\u00e9valuer ces diff\u00e9rentes approches.<\/p>\n

-15h45-16h15- Remi Watrigant, Universit\u00e9 Claude Bernard Lyon 1<\/a><\/p>\n

Titre : Testing resiliency of instances using Integer Linear Programming<\/strong><\/p>\n

R\u00e9sum\u00e9 : We present a notion of resiliency for optimization or decision problems, which consists in deciding whether a solution of a given cost still exist after any (appropriately defined) modification has been applied to the instance. In order to tackle these kinds of problems, we introduce a resiliency version of an Integer Linear Program (ILP), and present a Fixed-Parameter Tractable (FPT) algorithm for testing whether an ILP is resilient. As a direct application of our approach, we study a resiliency version of a generalization of the Set Cover problem, arising in the field of access control. We analyze its parameterized complexity by considering several parameterizations, establishing the frontier between tractable and intractable cases.
\nThis is joint work with Jason Crampton, Gregory Gutin and Martin Koutecky<\/p>\n","protected":false},"excerpt":{"rendered":"

Important : Dans le cadre du plan vigipirate et afin de faciliter l\u2019organisation de cette journ\u00e9e, vous devez obligatoirement vous inscrire au pr\u00e9alable en cliquant ici. Quand: Le lundi 5 mars 2018 O\u00f9: En salle H218, \u00e0 T\u00e9l\u00e9com SudParis Programme de la journ\u00e9e – Accueil: 10h00 – 10h30-11h10- Jos\u00e9 Neto, T\u00e9l\u00e9com SudParis Titre : Approches […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"ocean_post_layout":"","ocean_both_sidebars_style":"","ocean_both_sidebars_content_width":0,"ocean_both_sidebars_sidebars_width":0,"ocean_sidebar":"","ocean_second_sidebar":"","ocean_disable_margins":"enable","ocean_add_body_class":"","ocean_shortcode_before_top_bar":"","ocean_shortcode_after_top_bar":"","ocean_shortcode_before_header":"","ocean_shortcode_after_header":"","ocean_has_shortcode":"","ocean_shortcode_after_title":"","ocean_shortcode_before_footer_widgets":"","ocean_shortcode_after_footer_widgets":"","ocean_shortcode_before_footer_bottom":"","ocean_shortcode_after_footer_bottom":"","ocean_display_top_bar":"default","ocean_display_header":"default","ocean_header_style":"","ocean_center_header_left_menu":"","ocean_custom_header_template":"","ocean_custom_logo":0,"ocean_custom_retina_logo":0,"ocean_custom_logo_max_width":0,"ocean_custom_logo_tablet_max_width":0,"ocean_custom_logo_mobile_max_width":0,"ocean_custom_logo_max_height":0,"ocean_custom_logo_tablet_max_height":0,"ocean_custom_logo_mobile_max_height":0,"ocean_header_custom_menu":"","ocean_menu_typo_font_family":"","ocean_menu_typo_font_subset":"","ocean_menu_typo_font_size":0,"ocean_menu_typo_font_size_tablet":0,"ocean_menu_typo_font_size_mobile":0,"ocean_menu_typo_font_size_unit":"px","ocean_menu_typo_font_weight":"","ocean_menu_typo_font_weight_tablet":"","ocean_menu_typo_font_weight_mobile":"","ocean_menu_typo_transform":"","ocean_menu_typo_transform_tablet":"","ocean_menu_typo_transform_mobile":"","ocean_menu_typo_line_height":0,"ocean_menu_typo_line_height_tablet":0,"ocean_menu_typo_line_height_mobile":0,"ocean_menu_typo_line_height_unit":"","ocean_menu_typo_spacing":0,"ocean_menu_typo_spacing_tablet":0,"ocean_menu_typo_spacing_mobile":0,"ocean_menu_typo_spacing_unit":"","ocean_menu_link_color":"","ocean_menu_link_color_hover":"","ocean_menu_link_color_active":"","ocean_menu_link_background":"","ocean_menu_link_hover_background":"","ocean_menu_link_active_background":"","ocean_menu_social_links_bg":"","ocean_menu_social_hover_links_bg":"","ocean_menu_social_links_color":"","ocean_menu_social_hover_links_color":"","ocean_disable_title":"default","ocean_disable_heading":"default","ocean_post_title":"","ocean_post_subheading":"","ocean_post_title_style":"","ocean_post_title_background_color":"","ocean_post_title_background":0,"ocean_post_title_bg_image_position":"","ocean_post_title_bg_image_attachment":"","ocean_post_title_bg_image_repeat":"","ocean_post_title_bg_image_size":"","ocean_post_title_height":0,"ocean_post_title_bg_overlay":0.5,"ocean_post_title_bg_overlay_color":"","ocean_disable_breadcrumbs":"default","ocean_breadcrumbs_color":"","ocean_breadcrumbs_separator_color":"","ocean_breadcrumbs_links_color":"","ocean_breadcrumbs_links_hover_color":"","ocean_display_footer_widgets":"default","ocean_display_footer_bottom":"default","ocean_custom_footer_template":"","ocean_post_oembed":"","ocean_post_self_hosted_media":"","ocean_post_video_embed":"","ocean_link_format":"","ocean_link_format_target":"self","ocean_quote_format":"","ocean_quote_format_link":"post","ocean_gallery_link_images":"on","ocean_gallery_id":[],"footnotes":""},"categories":[75],"tags":[],"class_list":["post-990","post","type-post","status-publish","format-standard","hentry","category-methodes","entry"],"_links":{"self":[{"href":"https:\/\/samovar.telecom-sudparis.eu\/index.php\/wp-json\/wp\/v2\/posts\/990","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/samovar.telecom-sudparis.eu\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/samovar.telecom-sudparis.eu\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/samovar.telecom-sudparis.eu\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/samovar.telecom-sudparis.eu\/index.php\/wp-json\/wp\/v2\/comments?post=990"}],"version-history":[{"count":1,"href":"https:\/\/samovar.telecom-sudparis.eu\/index.php\/wp-json\/wp\/v2\/posts\/990\/revisions"}],"predecessor-version":[{"id":1558,"href":"https:\/\/samovar.telecom-sudparis.eu\/index.php\/wp-json\/wp\/v2\/posts\/990\/revisions\/1558"}],"wp:attachment":[{"href":"https:\/\/samovar.telecom-sudparis.eu\/index.php\/wp-json\/wp\/v2\/media?parent=990"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/samovar.telecom-sudparis.eu\/index.php\/wp-json\/wp\/v2\/categories?post=990"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/samovar.telecom-sudparis.eu\/index.php\/wp-json\/wp\/v2\/tags?post=990"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}