La ROADEF
R.O.A.D
Événements
Prix
Publications
Plus
Forum
Connexion

Une structure de données très rapide pour manipuler une frontière Paréto?

Forum 'Discussions' - Sujet créé le 20/01/2022 par unknown (449 vues)


Le 20/01/2022 par unknown :

Sans forcement faire d'optimisation multi-objectif, j'ai souvent eu besoin de stocker n
valeurs qui satisfont les contraintes:
v1 <= v2 <= v3 .... <= vn
p1 <= p2 <= p3 .... <= pn

Ce besoin peut apparaître même dans la résolution du problème
de sac-à-dos par programmation dynamique; les v_i peuvent représenter
les valeurs et les p_i les poids. On a besoin de considérer un poids p supérieur
à un poids existant p_i uniquement si sa valeur v est aussi supérieure
à v_i.

Contrairement à un problème multi-objectif, on peut facilement arriver
à des frontières Paréto comme les (v_i, p_i) plus haut avec n=10000000.
Il peut devenir très cher de tester si une nouvelle paire (p,v) doit
faire partir de la frontière.

Quelqu'un connait une bibliothèque qui nous mets à disposition une structure
de données très rapide pour ce genre de taches?


A+,
Daniel

 







Moteur de recherche
Tous les forums


  La Société française de Recherche Opérationnelle et Aide à la Décision ROADEF est une association Loi 1901 Plus d'informations sur la ROADEF