[PDF] [PDF] Equipe : Optimisation Combinatoire - Cedric-Cnam

[PDF] Optimisation Combinatoire : Programmation Linéaire et - LIP6

29 sept 2015 · 3 3 Problèmes classiques en optimisation combinatoire 27 du problème En effet , il y a une variable par sommet du graphe et une inégalité par

[PDF] Résolution de problèmes combinatoires et optimisation par - CNRS

Cette méta-heuristique a permis de résoudre différents problèmes d'optimisation combinatoire, comme par exemple le problème du voyageur de commerce [ 

[PDF] Optimisation combinatoire Concepts fondamentaux - LAMSADE

blèmes d'optimisation combinatoire Celle-ci consiste à ramener un tel problème à la résolution d'un programme linéaire en décrivant l'enveloppe convexe de 

[PDF] RECHERCHE OPÉRATIONNELLE : Optimisation Combinatoire

On verra dans le cours que le problème du voyageur de commerce est probablement de complexité exponentielle (il est NP-difficile) Toutefois, il y a des

[PDF] Méthodes doptimisation combinatoire en - MIAT INRA

23 sept 2019 · 1 7 1 Résolution du problème dual Lagrangien L'optimisation combinatoire ( ou discrète) est une branche très importante en re- cherche 

[PDF] Optimisation Combinatoire (Méthodes approchées)

Polynomial Vs Exponential Page 17 P = NP ? ○ Classe P: problèmes de décision pour lesquels on connaît des algorithmes polynomiaux

[PDF] Equipe : Optimisation Combinatoire - Cedric-Cnam

pour le problème général de la programmation linéaire en nombres entiers De nombreux problèmes d'optimisation combinatoire peuvent se formuler comme 

[PDF] tony buzan booster sa mémoire pdf

[PDF] ouverture numérique d'une fibre optique demonstration

[PDF] avc echelle fast

[PDF] vite avc

[PDF] question a poser pour detecter un avc

[PDF] fast avc

[PDF] référentiel de certification de la visite médicale

[PDF] leem

[PDF] nouvelle charte visite medicale 2017

[PDF] mathématique appliquée ? la finance pdf

[PDF] theoreme de bezout methode

[PDF] faire fonctionner un algorithme a la main

[PDF] ecrire un algorithme a la main

[PDF] expliquer les pourcentages en cm2

[PDF] les besoins nutritionnels de l'homme cours

Equipe : Optimisation Combinatoire

Rapport d'Activités 2001-2002

Responsable et coordonnées

Alain Billionnet, professeur

tél. : 01 69 36 73 33 télécopie : 01 69 36 73 05 e-mail : billionnet@iie.cnam.fr

Composition

A. Billionnet (Professeur des Universités à l'IIE), M.-C. Costa (Professeur des Universités au

CNAM) S. Elloumi, C. Picouleau, Agnès Plateau (Maîtres de Conférences au CNAM), A. Faye, F.

Roupin (Maîtres de Conférences à l'IIE),

K. Djebali (Doctorante et ATER à l'IIE), M. Zrikem (Doctorante et ATER à l'IIE), P. Meurdesoif (ATER à l'IIE), F. Jarray (Doctorant-moniteur au CNAM), L. Létocart (Doctorant et ATER au CNAM), L. Grouz (ATER à Paris X), S. Le Nestour (Doctorant et ingénieur à Air

France)

Professeur invité pendant 1 mois dans l'équipe en 2002 : Dominique de Werra, Professeur à l'EPFL, Lausanne.

Description des activités de recherche

Problématique

Un axe important de l'équipe est celui de l'optimisation d'une fonction pseudo-booléenne (c'est-à-dire de {0,1} n dans R), quelconque, avec contraintes ou sans contraintes. Cette modélisation, extrêmement générale, permet de formuler de très nombreux problèmes d'optimisation combinatoire. Malheureusement ces problèmes sont en général difficiles et, dans beaucoup de cas, seuls des exemples de petit e taille peuvent actuellement être résolus. Un autre axe concerne les problèmes de reconstr uction de figures du plan discret à partir de leurs deux projections orthogonales. Un troisième axe concerne les problèmes de multiflots de coût minimal en nombres entiers. Un quatrième axe concerne la mise au point d'algorithmes

pour le problème général de la programmation linéaire en nombres entiers. Enfin, une étude

est menée sur les problèmes d'ordonnancement avec délais de communication. Dans ces 5

axes, les travaux de l'équipe visent à une meilleure compréhension de ces problèmes difficiles

dans le but d'améliorer leur résolution c'est à dire de proposer des algorithmes permettant de

résoudre des instances de taille " raisonnable ». Nous présentons ci-dessous les résultats

obtenus dans ces différents axes de recherche. 11 activités principales ont été retenues mais

beaucoup de travaux sont communs à plusieurs activités.

Résultats obtenus

Activité n° 1 : Optimisation non linéaire en variables 0-1. Etude de problèmes génériques comme, par exemple, l'affectation et la semi-affectation quadratique, le sac à dos quadratique ou hyperbolique, le partitionnement de graphes, la coloration de graphes, la recherche de chemins optimaux dans un graphe sous contraintes, la recherche d'ensembles remarquables dans un graphe...Ces problèmes NP-difficiles sont souvent mal résolus et nous avons, en particulier, proposé de nouvelles méthodes permettant

d'améliorer de façon importante leur résolution (traiter de plus grandes instances). Nous nous

sommes intéressés à leur résolution exacte (énumération implicite, relaxation linéaires,

relaxations quadratiques convexes et semi-définies positives, approche polyédrique, programmation linéaire en variables mixtes) et à leur résolution approchée (heuristiques

spécifiques, métaheuristiques). Nous avons également proposé des algorithmes -approchés

et des schémas d'approximation (algorithmes approchés fondés sur la résolution de la relaxation continue de problèmes linéaires ou quadratiques en entiers, transfert de schémas

d'approximation du cas linéaire au cas fractionnaire, résultats négatifs si " P est différent de

NP »).

Activité n° 2 : Application de l'optimisation non linéaire en variables 0-1 à des problèmes concrets particuliers Placement optimal de tâches dans les systèmes répartis ou multiprocesseurs : Il existe une grande variété de problèmes de placement et nous nous sommes limités aux modèles dont l'objectif ne nécessite pas la prise en compte de contraintes de précédence. Les travaux de

l'équipe concernent l'élaboration d'algorithmes efficaces (exacts et approchés) pour différents

modèles de placement de tâches avec et sans contraintes de ressources. Plusieurs contrats de

recherche sur le placement de tâches et l'optimisation d'architectures ont été signés avec EDF

(Direction des Etudes et Recherches). Optimisation de l'architecture de réseaux de télécommunications Une première étude a

concerné un problème d'optimisation lié à l'architecture des réseaux urbains (réseaux

constitués d'un ensemble de centres qui communiquent et qui doivent être raccordés de façon

" optimale » suivant une topologie en anneau). Une deuxième étude, qui se termine

actuellement, concerne l'optimisation de l'architecture des réseaux GSM,problème étudié, en

liaison avec France-Telecom R&D. Définir une architecture consiste à faire des choix

d'équipement de certains sites et à relier des sous-ensembles de clients à des sites équipés, par

l'intermédiaire de boucles. De nombreuses contraintes sont à prendre en compte comme, par exemple, la longueur maximale d'une boucle ou la charge maximale d'un équipement. La méthode proosée pour les réseaux urbains, fondée en partie sur la program mation linéaire

mixte et des méthodes de coupes a permis de traiter des problèmes de taille réelle. En ce qui

concerne les réseaux GSM, la méthode proposée qui utilise programamtion mathématique et heuristiquesnous permet de traiter des instances de taille moyenne.

Activité n° 3 : Modélisation

et résolution de problèmes d'optimisation combinatoire par la programmation linéaire en variables mixtes. De nombreux problèmes d'optimisation combinatoire peuvent se formuler comme un programme linéaire mixte. Une des difficultés de cette approche réside dans la recherche d'une bonne formulation car il en existe souvent plusieurs pour un même problème. Les travaux menés sur le sujet concernent donc le choix d'une bonne formulation, l'ajout de coupes (contraintes redondantes en variables entières mais non redondantes en variables

réelles) et l'expérimentation : cette partie est très importante car on ne peut être assuré de

l'efficacité d'une formulation tant que l'on ne l'a pas testée sur des instances réelles. La

démarche a été appliquée à l'optimisation d'architecture de réseaux de télécommunication, au

problème du sac à dos quadratique, à certains problèmes d'emplois du temps, à la recherche

de chemins optimaux dans les graphes avec une fonction économique non linéaire, à différentes applications de la programmation stochastique notamment dans le domaine financier et à des problèmes de gestion de stocks non linéaires et discrets. Activité n° 4 : Programmation linéaire en nombres entiers A l'origine destinées à la résolution de probl èmes de programmation linéaire continue, les méthodes intérieures ont trouvé un champ d'applications beaucoup plus large incluant aussi bien des problèmes de programmation quadratique que des problèmes d'optimisation en nombres entiers et, plus récemment encore, des problèmes de programmation semi-définie. Le

travail réalisé dans ce thème a été la conception et la validation d'une méthode hybride

utilisant un code de points intérieurs pour la résolution de programmes linéaires en nombres

entiers.

Activité n° 5 : Localisation

Le problème du p-Centre est bien connu en théorie de la localisation et a de nombreuses applications. Il s'agit de localiser au maximum p entrepôts parmi M sites possibles et

d'allouer chacun des N clients à la facilité la plus proche, de façon à ce que la distance

maximale entre un client et l'entrepôt qui le dessert soit minimale. Nous avons proposé une nouvelle approche (programmation linéaire en 0-1 et nouvelle méthode de calcul de bornes)

du problème qui nous permet de résoudre différentes instances tirées de TSPlib dont la taille

atteint 1817 entrepôts et 1817 clients.

Activité n° 6 : Tomographie discrète

La tomographie discrète ou reconstruction d'images discrètes à partir de certaines de leurs projections est un sujet en pleine expansion. Ses applications industrielles en cristallographie et en imagerie médicale font de ce sujet une source importante de problèmes algorithmiques.

Plusieurs résultats significatifs ont été obtenus dans ce thème. Nous nous intéressons

actuellement au problème de reconstruction d'un tableau tricolore et au problème de reconstruction d'une matrice de permutation à partir de ses projections diagonales. Activité n° 7 : Multichemins, multiflots entiers et multicoupes Ce thème concerne la recherche de multicoupes et multiflots en nombres entiers de valeur maximale dans un graphe. Les arêtes du graphe étant munies de capacité et/ou de coûts, trouver un multiflot entier maximal consiste à router une quantité maximale de flots entre k paires de sommets appelés sources (S 1 , S 2 ,...S k ) et puits (T 1 , T 2 ,..,T k ). Si les demandes pour chaque couple (S k ,T k ) sont fixées, on recherche le routage de coût minimal. Trouver une multicoupe minimale consiste à sélectionner un ensemble d'arêtes de poids minimal coupant tous les chemins reliant une source S k

à un puits T

k . Nous avons obtenu plusieurs résultats intéressants sur ces problèmes qui sont très difficile en nombres entiers. Une application importante de ce problème est l'optimisation de la pose de câbles dans les centrales EDF. Un contrat de recherche entre le CNAM-CEDRIC et EDF subventionne les recherches sur ce sujet.

Perspectives

Actuellement de nombreux problèmes d'optimisation combinatoire ne peuvent être résolus faute de disposer d'algorithmes efficaces. Deux axes principaux de recherche seront

développés pour essayer de progresser dans la résolution pratique de ces problèmes difficiles :

1. proposer des algorithmes de résolution (en solutions exactes) permettant de traiter des

problèmes de taille raisonnable. Des progrès théoriques et algorithmiques importants sont donc nécessaires puisque dans l'état actuel des connaissances de très nombreux problèmes comportant quelques dizaines de variables sont impossibles à résoudre.

2. lorsque les problèmes ne pourront être résolus en solutions exactes, on utilisera des

méthodes approchées comme la méthode du recuit simulé ou la méthode Tabou. Ces méthodes sont générales et souvent efficaces. Cependant elles ne donnent aucune information sur la qualité des solutions obtenues (garantie de performance). L'objet de la recherche sera donc de proposer des algorithmes (généraux si possible) de validation de ces heuristiques,

c'est-à-dire des algorithmes permettant de déterminer un majorant de l'écart entre la solution

optimale et la solution approchée. Bien entendu les axes 1 et 2 sont étroitement liés.

Publications

Publications dans des revues intern

ationales avec comité de lecture C.PICOULEAU, Reconstruction of domino tiling from its two orthogonal projections. Theoretical Computer Sciences (TCS), 255(1), 2001, pp. 437-447. A.BILLIONNET and S.ELLOUMI, Best reduction of the quadratic semi-assignment problem. Discrete Applied Mathematics (DAM), 109(3), 2001, pp. 197-213.

X.CASTELLANI, H.JIANG and A.BILLIONNET,

Method for the analysis and design of

class characteristic migrations during object system evolution. Information Systems 26,

2001, pp. 237-257.

A.BILLIONNET, Approximation algorithms for fractional knapsack problems. Operations

Research Letters (ORL), 30(5), 2002, pp. 336-342.

A.BILLIONNET, Approximate and exact solution methods for the hyperbolic 0-1 knapsack problem. Information Systems and Operational Research (INFOR), 40(2), 2002, pp. 97- 110.
M.-C.COSTA, A.HERTZ and M.MITTAZ, Bounds and heuristics for the Shortest Capacited Paths Problem. Journal of Heuristics, 8(4), 2002, pp. 449-465. M.-C.COSTA, F.-R.MONTCLAR and M.ZRIKEM, Variable neighborhood search for the optimization of cable layout problem. Journal of Intelligent Manufacturing, 13(5), 2002. P.MEURDESOIF, Strengthening the Lovász )(G bound for graph coloring. Mathematical

Programming, 2002.

Publications dans des revues nationales avec comité de lecture P.MEURDESOIF and B.ROTTEMBOURG, Semi-definite positive programming relaxations for graph K n -coloring in frequency assignment. RAIRO-Operations Research 35, 2001, pp. 211-228.

à paraître

M.-C.COSTA, L.LETOCART and F.ROUPIN, A greedy algorithm for multicut and integral multiflow in rooted trees. Operation Research Letters (ORL), 31(1), 2003, pp. 21-27. A.BILLIONNET, Using Integer Programming to Solve the Train Platforming Problem. A paraître dans Transportation Science. A.BILLIONNET, Minimising total average cycle stock subject to practical constraints. A paraître dans Journal of the Operational Research Society (JORS). A.BILLIONNET and E.SOUTIF, Using a mixed integer programming tool for solving the 0-1 quadratic knapsack problem. A paraître dans INFORMS Journal of Computing. A.BILLIONNET and E.SOUTIF, An exact method for the 0-1 knapsack problem. A paraître dans European Journal of Operational Research (EJOR). A.PLATEAU, D.TACHAT and P.TOLLA, A Hybrid Search Combining Interior Point Methods and Metaheuristics for 0-1 Programming. A paraître dans Transactions in

Operations Research.

A.BILLIONNET, Mixed integer programming for the 0-1 maximum probability model. A paraître dans European Journal of Operational Research (EJOR). A.BLANCHARD, S.ELLOUMI, A.FAYE et N.WICKER, Un algorithme de génération de coupes pour le problème de l'affectation quadratique. A paraître dans Information Systems and Operational research (INFOR).

S.ELLOUMI, M.LABBE and Y.POCHET,

A New Formulation and Resolution Method for

the p-Center Problem. A paraître dans INFORMS Journal of Computing.

Communications dans des congrès intern

ationaux avec sélection sur résumé A.BILLIONNET, Résolution d'un programme stochastique par la programmation linéaire mixte. FRANCORO III, Troisièmes journées francophones de recherche opérationnelle,

Québec, 9-12 mai 2001.

P.MEURDESOIF, The Lovász bound and some quadratizations in Graph Coloring. Max-

Clique'01 Workshop, Klagenfurt, may 2001.

M.-C.COSTA, L.LETOCART and F.ROUPIN, Minimal Multicut and Maximal Integer Multiflow : A survey. European Chapter on Combinatorial Optimization (ECCO

XIV), Bonn, June 2001.

S.ELLOUMI, M.LABBE and Y.POCHET, A new formulation and exact solution method for the p-center problem. The European Operational Research Conference, EURO 2001,

Rotterdam, 9-11 Juillet 2001.

A.BILLIONNET, S.ELLOUMI and L.GROUZDJERBI, A decomposition method for designing radio-mobile access networks based on SDH rings. The European Operational

Research Conference,

EURO 2001

, Rotterdam, 9-11 Juillet 2001. M.-C.COSTA, L.LETOCART and F.ROUPIN, Multicut and Integral Multiflow Duality. A polynomial Algorithm in Rooted Trees. Optimization Days, 6-9 mai 2001, Quebec, Canada. F.ROUPIN, Résolution de Max-2-SAT par programmation semidéfinie. FRANCORO III, Troisièmes journées francophones de recherche opérationnelle, Québec, 9-12 mai 2001. L. ALFANDARI, A. PLATEAU and P. TOLLA, A two-phase path relinking process for the

GAP. MIC'01 (4

th Metaheuristics International Congress), Porto, Juillet 2001.

A.BLANCHARD, S.ELLOUMI, A.FAYE et N.WICKER

, Un algorithme de coupes pour l'affectation quadratique. FRANCORO III, Troisièmes journées francophones de recherche opérationnelle, Québec, 9-12 mai 2001. F.R.MONCLAR and M.ZRIKEM, A Variable Neighborhood Search for the Optimization of power plant Cable, MIC'01 (4 th Metaheuristics International Congress), Porto, Juillet 2001. S.ELLOUMI, M.LABBE and Y.POCHET, Generalisations of the p-Center problem: formulations and solution methods. ECCO XV, European Chapter on Combinatorial

Optimization, Lugano 30 mai-1

er juin, 2002. F.JARRAY and L.WYNTER, An Optimal Smart Market for the Pricing of

Telecommunications Services. INFORMS, March 2002.

J.CARDINAL, S.ELLOUMI and M.LABBE, Local optimization of index assignments for multiple description coding. EUSIPCO, XIth European Signal Processing Conference, 2002. M.-C.COSTA, C.PICOULEAU and M.ZRIKEM, Solving Shortest Multipaths Problems on Grids. CIRO'02, Conférence Internationale de Recherche Opérationnelle, Marrakech, Maroc,

4-6 Juin, 2002.

L.LETOCART and F.ROUPIN,

A semidefinite approach to solve multicut in trees. Optimization Days, Montréal, Canada, 6-8 mai, 2002. A.BILLIONNET and K.DJEBALI, Problème de rééquilibrage d'un portefeuille avec des coûts de transactions linéaires et fixes. CIRO'02, Conférence Internationale de Recherche Opérationnelle, Marrakech, Maroc, 4-6 Juin, 2002. F.ROUPIN, Semidefinite relaxations for several quadratic problems. CIRO'02, Conférence Internationale de Recherche Opérationnelle, Marrakech, Maroc, 4-6 Juin, 2002. M.-C.COSTA, Polynomial algorithms to solve the multiway cut and integer flow problems in trees. CO'02, Combinatorial Optimization, Paris, 8-10 avril 2002 et ECCO XV, European Chapter on Combinatorial Optimization, Lugano, 30 mai-1 juin, 2002. Communications dans des congrès nationaux avec sélection sur résumé A. FAYE Building facets for the quadratic 0-1 knapsack polytope - In Proceedings CO'02,

2002. Paris 8-10 Avril 2002

A. FAYE, O. BOYER , Construction de facettes pour le polytope du sac-à-dos quadratique en 0-1 - In Proceedings ROADEF 2002, 2002. Paris 20-22 Février 2002 A.BILLIONNET et K.DJEBALI, Construction de la frontière d'efficience pour un problème de portefeuille non convexe. ROADEF, 4

ème

congrès de la société française de recherche opérationnelle et d'aide à la décision, Paris, 20-22 février 2002. C.PICOULEAU, Stabilité des problèmes NP-complets. ROADEF, 4

ème

congrès de la société

française de recherche opérationnelle et d'aide à la décision, Paris, 20-22 février 2002.

M.-C.COSTA, L.LETOCART et F.ROUPIN,

Multiflots entiers et multicoupes: analyse de

leur difficulté. ROADEF, 4

ème

congrès de la société français e de recherche opérationnelle et d'aide à la décision, Paris, 20-22 février 2002. F.ROUPIN, De la programmation linéaire à la programmation semidéfinie : une approche générique pour la relaxation de problèmes combinatoires. ROADEF, 4

ème

congrès de la

société française de recherche opérationnelle et d'aide à la décision, Paris, 20-22 février 2002.

S.ELLOUMI, M.LABBE et Y.POCHET, Formulation et résolution d'un problème de p-

Centre tolérant aux pannes. ROADEF, 4

ème

congrès de la société française de recherche opérationnelle et d'aide à la décision, Paris, 20-22 février 2002. P.MEURDESOIF, Relaxations demi-définies pour la coloration de graphes et l'allocation de fréquences. ROADEF, 4

ème

congrès de la société française de recherche opérationnelle et d'aide à la décision, Paris, 20-22 février 2002. BLANCHARD, S. ELLOUMI, A. FAYE, N. WICKER Un algorithme de coupes pour l'Affectation Quadratique - In Proceedings FRANCORO III, 2001. Québec Canada 9-12 Mai 2001

Conférences invitées, séminaires

A.BILLIONNET, Optimisation quadratique en variables bivalentes (Tutorial). Journées franciliennes de recherche opérationnelle, 15 mars 2002, Paris. C.PICOULEAU, Coloriage et dominos : application à la construction de plannings. Journées franciliennes de recherche opérationnelle, 9 octobre 2002, Paris. M.-C.COSTA, Problèmes de multicoupes et multiflots en nombres entiers. Séminaire du LRI,

Université Paris 11, 14 juin 2002 et Séminaire du SMG, Université Libre de Bruxelles, 17 mai

2002.
F.ROUPIN, From Linear to Semidefinite Programming: A Recipe to obtain Semidefinite Relaxations for Bivalent Quadratic Problems. Séminaire du SMG, Université Libre de

Bruxelles, 29 novembre 2002.

Rapports de recherche

A. BLANCHARD, S. ELLOUMI, A. FAYE, N. WICKER

Une famille de facettes pour le polytope de l'affectation quadratique - Rapport CEDRIC 2002.
quotesdbs_dbs15.pdfusesText_21