Graphes k-partis et conception de circuits VLSI Pierre Fouilhoux Maitre de Conférences Université Pierre et Marie Curie - LIP6 Directeur: A. Ridha Mahjoub

Graphes k-partis et conception de circuits VLSI

Pierre FouilhouxMaitre de ConférencesUniversité Pierre et Marie Curie - LIP6

Directeur: A. Ridha MahjoubUniversité Blaise Pascal - LIMOS

Ecole Doctorale Sciences pour l’Ingénieur

Trouverun meilleur élément

dans un ensemble fini valué

Optimisation Combinatoire


Placement d’émetteurs hertziens


Placement d’émetteurs hertziens


Problème du Voyageur de commerce


Problème du Voyageur de commerce


Conception de circuits intégrés (VLSI)

ComposantRéseau Points terminaux


Conception de circuits intégrés (VLSI)


Reconstruction du génome

T

TC

AG

T

TC

AG

T

TC

AG


RechercheOpérationnelle Théorie des Graphes

T

TC

AG

Théorie des Graphes


RechercheOpérationnelle

Stable dans un graphe = Sommets isolés

T

TC

AG




Stable dans un graphe

T

TC

AG




k-partition dans un graphe

T

TC

AG




T

TC

AG




bipartition dans un graphe (k=2)

C

T

TC

AG




bipartition dans un graphe (k=2)

C

T

TC

AG


RechercheOpérationnelle Théorie des Graphes

PB(G)=conv { xW | W V, (W,E(W)) est biparti }nIR

,,1)(0 Vvvx

,),(,1)( impaircycleTWquetelETVWWuxWu

.,)( Vventiervx

Vv

vxvcMax )()(

T

TC

AG



Programmation mathématiqueApproches polyédralesThéorie des Graphes

T

TC

AG

T

TC

AG

Polymorphisme génétique

SNP : Single Nucleotide Polymorphism

Reconstituerles 2 haplotypeset les SNP

ATCGATGCATGAATGCATGCAATCGATGGATGTATGCAAGCA

Organismes diploïdes T

A

Assemblage SNP d’haplotypes

Molécule d’ADN

2 haplotypes

f1 ATCGATGCATGAf2 TCGATGGATGAATf3 ATGCATGTATGCAAf4 ATGAATGCATGCAf5 CATGCA

Fragments fi


Détection des SNP


SNP sj

S1S2 S3


Objectif

Reconstituer

les deux haplotypes

f1f2

f5

f4

f3

H1H2

Enlèvement minimal de fragments

f1

f2

f5

f4

f3

Problème de bipartisation de graphe

Lippert, Schwartz, Lancia, Istrail (2001)


est équivalent au

f3


S1S2 S3

f2

f1

f4

f5

fj

fiHaplotype 1

Haplotype 2

Résolution informatiquedu problème de bipartisation

v1

v2

v3

v4

v5

v7

v8

v9

v1

0 v6

v1

v2

v3

v4

v5

v7

v8

v9

v1

0 v6


v1

v2

v3

v4

v5

v7

v8

v9

v1

0 v6

v1 v2 v3 v4 v5 v6 v7 v8 v9 v10

1 1 1 1 1 1 1 1 1 1


vi

conservé

ôté

1

0

v1

v2

v3

v4

v5

v7

v8

v9

v1

0 v6

v1 v2 v3 v4 v5 v6 v7 v8 v9 v10

1 1 1 0 1 1 1 1 0 1


Ce n’est pas une solution

vi

conservé

ôté

1

0

C

v1

v2

v3

v4

v5

v7

v8

v9

v1

0 v6

v1 v2 v3 v4 v5 v6 v7 v8 v9 v10

0 1 1 1 1 1 1 1 1 1


C’est une solution

vi

conservé

ôté

1

0


Une première idée: Enumération de toutes les solutions

n 2n Temps de calculBlue Gene

Ordinateurdu futur

10 1024 0,00000…1 seconde

…

20 1 048 576 1 milliardième de sec

…

50 1,26 million de milliards

16 minutes quelques sec

100 1 267 milliards de milliards de milliards

1,1 milliardd’années

1 milliard d’années

1000

10301 … …

n sommets 2n=2x2x…x2 solutions à énumérer

n fois

pierreF

Blue Gene le calculateur d'IBM et des US:36,01 teraflops (mille milliards d'opérations par seconde)Vie du soleil environ 10 milliards d'années

Soit G=(V,E) un graphe c un vecteur-poids sur les sommets de V.

Pour B V, on pose

.0

,1)(

sinon

BvsivxB

Formulation en un programme linéaire en nombres entiers

,,1)(0 Vvvx

,),(,1)( impaircycleTWquetelETVWWuxWu

.,)( Vventiervx

Vv

vxvcMax )()(

Formulation mathématique:Approche polyèdrale et algorithme de coupes


v1

v2

v3

(0,0,0) (1,0,0) (0,1,0) (0,0,1) (1,1,0) (1,0,1) (0,1,1) (1,1,1)


,,1)(0 Vvvx

,),(,1)( impaircycleTWquetelETVWWvxWu

.,)( Vventiervx

Vv

vxvcMax )()(

2321 vvv xxx

(0,1,0) (1,1,0)

(1,0,0)

(1,0,1)(0,0,1)

(0,1,1)

(0,0,0)

(1,1,1)

v1

v2

v3

On associe à chaque solution un point saillantd’un (hyper)-cube


,,1)(0 Vvvx


.,)( Vventiervx

Vv

vxvcMax )()(

2321 vvv xxx

(0,1,0) (1,1,0)

(1,0,0)

(1,0,1)(0,0,1)

(0,1,1)

v1

v2

v3


(0,0,0)

(1,1,1)


,,1)(0 Vvvx


.,)( Vventiervx

Vv

vxvcMax )()(

2321 vvv xxx

(0,1,0) (1,1,0)

(1,0,0)

(1,0,1)(0,0,1)

(0,1,1)

v1

v2

v3


(0,0,0)


PB(G)=conv { xW | W V, (W,E(W)) est biparti }nIR

Complexité des problèmes

On dit que ces problèmes sont faciles ou polynomiaux dans P et les autres problèmes sont donc dans Non-P

On ne sait pas dire si de nombreux problèmes célèbres

sont dans P ou dans Non-P

P=NP ?

Est-ce que ce problème de bipartisation est difficile ou non?

C’est la classe des problèmes dont on peut facilement savoir si une solution quelconque est valide ou non valide.

La classe de problème la plus célèbre est la Classe NP (Non-Deterministic Polynomial)

Croisement

Circuit électronique Ensemble de composants avec un ou plusieurs points terminaux reliés par des pistes rassemblées en réseaux.Croisement Deux pistes de réseaux différents qui se

croisent doivent être affectées à des couches différentes dans le but d’éviter les connexions interdites.

Problème de Via Minimization

Fil sur couche A B

Une affectation valide est une affectation des pistes sur les couches de manière à ce que deux pistes de réseaux différents qui se croisent, soient sur des couches différentes.Via Trou à percer pour connecter deux pistes

d’un même réseau.


Le problème de Via Minimization contraint

Déterminer une affectation valide des segments de pistes sur les couches avec un nombre minimum de

viassans déplacer les pistes.


Pour tout cycle impair C de G.Un via doit être percé à l’emplacementcorrespondant à un des sommetsdu cycle impair C.

C



C



C


Le problème de Via Minimization sur 2 couches

Le problème du sous-graphe biparti induit


est équivalent au

328 vias

88 réseaux1695 croisements

Temps de calcul 7min50

nb coupes 7551

nb sommets 6579


729 réseaux73166 croisements

nb sommets 291993

nb coupes 10481

Temps de calcul 4h05

2089 vias


Conclusion

Modélisation d’un problème de séquençage des génomes diploïdesModélisation du problème de Via Minimization

Etude polyédrale du problème de bipartisation de graphe

Elaboration de logiciels de résolution pour le problème de génomiqueet d’électronique.

Documents

Graphes k-partis et conception de circuits VLSI Pierre Fouilhoux Maitre de Conférences Université Pierre et Marie Curie - LIP6 Directeur: A. Ridha Mahjoub