Discussion :

[Nemerle]

Salut, comment-y k'est-ce qu'on fait avec le truc suivant: dans une compact connexe K du plan, comment choisir N points K tel que

- toute paire de points a un distance supérieur à une constante C
- la somme de ces distances est minimale

Gné?

[pseudocode]

En faisant du circle packing dans un compact ?

[Nemerle]

Nan, passqu'euh mon nombre de points N et mon D est petit par rapport à mon compact.

En fait Pseudocode, si tu veux le détail, voila:

mon K est décomposé en un pavage de "briques", et il y a en a beaucoup. Je veux decomposer mon K en N ensembles disjoints de briques, ensembles qui doivent tous avoir "à peu près" la meme taille. Ensuite, je vous trouver une brique dans chacun des N ensembles de telle sorte que la somme des distances entre ces N briques soit minimale.

[pseudocode]

Et bien heu... y a donc deux problèmes distincts ?

1. décomposer K en N ensembles disjoints qui ont tous a peu près la même taille
2. trouver un circuit de N points (chacun dans un ensemble) qui soit de longueur minimale

Ou alors les deux problèmes sont liés ? Il faut décomposer K de telles facon que le circuit soit minimum ?

[Nemerle]

oui 1 est aussi un problème!! Mais disons pour simplifier que tu fais un Voronoï en N-morceaux et tu passes au problème 2...


(mais si tu sais optimiser d'un coup 1+2, I take)

[pseudocode]

oui 1 est aussi un problème!! Mais disons pour simplifier que tu fais un Voronoï en N-morceaux et tu passes au problème 2...

Hum... pas évident. Mathématiquement, vu qu'on est dans un cas continu je suppose qu'on doit pouvoir utiliser les multiplicateurs de Lagrange.

Mais ca serait moi, je ferais de multiples essais avec un algo simplex (Nelder–Mead).

(mais si tu sais optimiser d'un coup 1+2, I take)

Heu... non.

[Nebulix]

J'essaie de comprendre le pb.
Tu as un pays K de forme donnée composé de M communes que tu veux regrouper en N départements, définir un chef-lieu au centre de chaque département.
Ensuite construire des autoroutes qui relient 2 à 2 les chef-lieus.
N est-il donné au départ ?
Le critère "somme des distances" est-il le mieux adapté ?

[Aleph69]

Bonsoir,

l'idée d'utiliser des multiplicateurs de Lagrange semble a priori être une bonne approche. Tu cherches un ensemble E={x1,x2,...xN} de N points de K tels que
la fonctionnelle "somme des distances" soit minimale avec des contraintes d'inégalité que tu introduis par des multiplicateurs de Lagrange. Par contre, tel que tu as posé ton problème initial, les briques dont tu parles n'interviennent pas. Mais peut-être que cela ne te pose pas de problème de les définir a posteriori?

[Nemerle]

tu peux préciser? Comment user de multiplicateur de Lagranges sur un problème de multi-déplacements?

[Aleph69]

Bonjour,

je ne sais pas ce que tu appelles un problème de multi-déplacements. Tel que tu as posé ton problème initialement, il s'agit d'un problème de partitionnement en pavage de Voronoi qui peut se résoudre soit par une approche géométrique (Delaunay), soit par une approche numérique (k-means,vq,kohonen,etc). La fonctionnelle que tu souhaites minimiser est tout à fait particulière et nécessite d'introduire des multiplicateurs pour tenir compte de tes contraintes. Enfin, j'opterai plutôt pour une approche stochastique par descente de gradient, ou équivalent, que pour une approche déterministe par minimisations locales successives. Concernant l'approche géométrique, il faudrait par exemple pouvoir générer un très grand nombre de points dans ton domaine K (par Monte-Carlo ou autre selon la connaissance que tu as de K), puis ensuite le mailler (a priori de manière non structuré par Delaunay si K n'a pas une forme particulière ou tensorisée), puis ensuite partitionner a posteriori ce maillage (enfin le graphe correspondant) comme ce qu'on fait en calcul parallèle pour l'équilibrage de tâche ou les méthodes de décomposition de domaine (il existe des bibliothèques pour ça, par ex. METIS et ParMETIS).

[Nemerle]

L'algorithme implémenté actuellement procède effectivement par une décomposition en zone de Voronoï; chaque médoïde des zones de Voronoï subit un petit déplacement dans les 4 directions et ceci récursivement sur les N zones pour rechercher un optimal. Le point de "départ" initialisant le 1ier découpage en 2 zones de Voronoï parcourt aussi le périmètre de K.

Cet algorithme donne une solution raisonnable, mais le temps de calcul est long. On envisage aussi un choix de N points dans les Voronoï par algorithme génétique ou par swarm optimisation.


Concernant l'approche par multiplicateur, ok pour la fonction somme des distance à différentier, mais comment modélises-tu des contraintes???

[Aleph69]

Concernant l'approche par multiplicateur, ok pour la fonction somme des distance à différentier, mais comment modélises-tu des contraintes???

Les multiplicateurs de Lagrange te servent justement à prendre en compte tes contraintes. Jette un oeil à ce document :
http://math.unice.fr/~dreyfuss/P13.pdf
et en particulier aux théorèmes 18 et 19 pages 41 et 42.

Si le document ne te convient pas, tu peux faire une recherche sur google avec les mots-clés "cours" et "optimisation".

[Nemerle]

Je connais les multiplicateurs, merci!
Mais ici, je ne vois pas comment definir les contraintes.

La fonction fitness f a 2*n variables, et se differencie aisément.
Mais quid de la contrainte? Appartenance
D'un point a K? Soit un ensemble d'inegalites d'hyperplans?

[Aleph69]

Bonjour,

si j'ai bien compris ton problème initial, tes contraintes sont des inégalités et portent sur la distance minimale entre deux points quelconques :

toute paire de points a un distance supérieur à une constante C

[Nemerle]

D'accord tu repars du problème simplifié initial.

Dans le cas où il n' y a pas cette contrainte, mais où K est partitionné en N zones de même taille (sauf la derniere, le "résiduel"), comment définir la contrainte d'appartenance d'un point à un zone, si ce n'est pas une liste d'équations ax+by< ou >c? Liste obtenue à partir d'une liste de points définissant le périmètre de la zone?

[Aleph69]

Bonsoir,

en s'inspirant des pavages de Voronoi. Le tien est certainement centroidal. Un point x appartient à une zone si et seulement la distance entre x et la germe g de cette zone est strictement inférieure aux distances entre x et les autres germes (je considère que ton pavage est ouvert pour ne pas avoir de cas indécidables).

[Nemerle]

Tu as raison, à une modif près c'est une très bonne idée... je vais la faire tester pour voir ce que ça donne.

Merci

[Nemerle]

Bonsoir,

en s'inspirant des pavages de Voronoi. Le tien est certainement centroidal. Un point x appartient à une zone si et seulement la distance entre x et la germe g de cette zone est strictement inférieure aux distances entre x et les autres germes (je considère que ton pavage est ouvert pour ne pas avoir de cas indécidables).

J'ai regardé... et tout cela est difficle... je reprends le problème:

"
mon K est décomposé en un pavage de "briques", et il y a en a beaucoup. Je veux decomposer mon K en N ensembles disjoints de briques, ensembles qui doivent tous avoir "à peu près" la meme taille. Ensuite, je vous trouver une brique dans chacun des N ensembles de telle sorte que la somme des distances entre ces N briques soit minimale.
"


En prenant N briques comme variables du modèles, puis
- en définissant les N cellules de Voronoi associées pour obtenir les nombres de briques NBn de ces cellules
- on définit les containtes par

1) somme des distances minimales
2) Tous les NBn inférieurs à une constante M

La j'ai correctement modélisé pour faire du multiplicateurs. Mais... le problème est que je ne sais absolument pas expliciter NBn: K est compact, mais n'est pas forcément connexe ni convexe...

Je suis preneur d'autres idées! En l'état, on fait du génétique et pis c'est tout

[Aleph69]

mon K est décomposé en un pavage de "briques", et il y a en a beaucoup. Je veux decomposer mon K en N ensembles disjoints de briques, ensembles qui doivent tous avoir "à peu près" la meme taille.

Je ne sais pas ce que tu entends par "briques" mais ton problème ressemble beaucoup à ce que l'on trouve dans les méthodes de décomposition de domaine, à savoir : partitionner un domaine maillé en N sous-domaines de taille similaire. La bibliothèque METIS permet de faire cela :
http://glaros.dtc.umn.edu/gkhome/views/metis
Tu pourras trouver les détails des algorithmes employés dans la documentation et les publications associées. Il faut avoir quelques notions en théorie des graphes. Il y a aussi une version parallèle si besoin (ParMETIS). Tu peux contacter l'auteur, il répond aux questions.

Ensuite, je vous trouver une brique dans chacun des N ensembles de telle sorte que la somme des distances entre ces N briques soit minimale.

C'est peut-être une fausse bonne idée, mais a priori je commencerai par éliminer toutes les briques qui ne touchent pas de "bord" (les briques intérieures en quelque sorte) parce qu'intuitivement je pense qu'elles ne sont pas dans l'ensemble des solutions. Concernant la complexité de ton problème, ca te permet de passer d'un problème de dimension D à un problème de dimension D-1 (grosso modo). Partant de ce principe, je pense qu'une énumération doit être relativement efficace (par rapport au temps global de toute la procédure) même s'il y a sûrement plus malin.

Mais... le problème est que je ne sais absolument pas expliciter NBn: K est compact, mais n'est pas forcément connexe ni convexe...

Il faut vraiment que tu expliques ce qu'est une brique pour toi. Il y a sûrement moyen de s'en sortir en utilisant la relation d'Euler, quitte à passer par le dual de K (triangulation) et une étape de raffinement pour avoir des "briques". Au fait, tu travailles en quelle dimension?

Quelles sont les propriétés de K? Est-ce un polyèdre? Les composantes connexes de K sont-elles convexes, simplement connexes? Connais-tu ces propriétés à l'avance ou faut-il les détecter?

[Nemerle]

Je ne sais pas ce que tu entends par "briques" mais ton problème ressemble beaucoup à ce que l'on trouve dans les méthodes de décomposition de domaine, à savoir : partitionner un domaine maillé en N sous-domaines de taille similaire.

Certes (on connait, on utilise un processus de Voronoi pour obtenir de telles décompositions dans l'algo génétique), mais ce que je cherche, c'est un peu plus: partitionner un domaine de telle sorte que la somme des "distances" entre sous-domaines soit minimale; la "distance entre 2 sous-domaine étant librement définie par le choix préalable d'un point (=une brique) dans le domaine, qui joue le jeu de centroïde.

Donc mes varia sont

- la partition
- le choix d'un point (=une brique) dans chaque sous-domaine.

Mon domaine (2D) est naturellement décomposé par un pavage rectangulaire régulier, et j'appelle "brique" un élément de ce pavage. Ce domaine est "juste" compact: pas connexe, pas convexe, avec des "trous",etc...