Discussion :

[sans_deconner]

Bonjour,
J'ai un problème qui s'apparente à celui du sac à dos.
J'ai fait un programme de PSE.
Je souhaiterais améliorer sa performance.

Je compte le nombre de feuilles et le nombre de noeuds parcourus.
Je souhaite en réduire le nombre.
Outre les éléments habituels du PSE (couper des branches inutiles), il me semblait que trier la liste devrait avoir un impact sur le nombre de noeuds/feuilles parcouru(e)s.
Vrai?

Et aussi qu'il fallait trier dans l'ordre croissant de ratio valeur / poids.
L'idée étant qu'en commençant l'arbre par les items les moins probables, on va couper plus de branches.
Vrai?

[dourouc05]

Effectivement, en prenant les objets dans l'ordre indiqué par ce ratio, tu as une très bonne heuristique (qui te donne une solution primale, puis une duale en considérant que tu prends "autant que possible" du premier objet que tu ne peux pas faire rentrer dans ton sac). Tu peux l'appliquer à chaque nœud de ton arbre pour améliorer tes bornes, ça pourrait accélérer tes traitements.

[sans_deconner]

en prenant les objets dans l'ordre indiqué par ce ratio, tu as une très bonne heuristique (qui te donne une solution primale

Donc, en triant par valeur/poids ascendant, on coupe plus de branches?

tu prends "autant que possible" du premier objet que tu ne peux pas faire rentrer dans ton sac)

Salut,
Je n'ai pas compris.

[dourouc05]

Donc, en triant par valeur/poids ascendant, on coupe plus de branches?

1. En triant quoi ? En faisant quoi avec ce tri ? Il faut être un chouïa plus précis, là (et ce n'est pas juste de la pédanterie : en l'état, je n'ai pas assez compris ce que tu expliques pour te dire si tu as raison ou pas avec une certitude suffisante).
2. L'espoir est que tu limites l'exploration, oui, mais je ne peux pas te le garantir pour n'importe quelle instance.

Je n'ai pas compris.

Si tu arrives à faire rentrer les premier et deuxième objets (respectivement, des poids de 10 et 15, pour un sac de capacité 30), en les considérant dans l'ordre du ratio valeur/poids, tu peux faire rentrer "un peu" du troisième objet (s'il a un poids de 10, tu pourras en faire rentrer la moitié). Puisque la solution n'est pas réalisable (elle n'est pas entière), ce n'est pas une borne primale ; par contre, ça te donne une borne duale (relâchement linéaire du problème initial, mais sans utiliser le simplexe).

[sans_deconner]

1. En triant quoi ?

Le tableau d'éléments candidats à entrer dans le sac.

En faisant quoi avec ce tri ?

Qui dit tri, dit critère de tri.
Donc il faut bien choisir un critère.

Il faut être un chouïa plus précis, là (et ce n'est pas juste de la pédanterie : en l'état, je n'ai pas assez compris ce que tu expliques pour te dire si tu as raison ou pas avec une certitude suffisante).
2. L'espoir est que tu limites l'exploration, oui, mais je ne peux pas te le garantir pour n'importe quelle instance.

On tente d'entrer successivement les éléments dans le sac (puis on coupe des branches lorsqu'il n'y a plus assez de poids disponible), il faut bien avoir un ordre dans lequel on essaie de les faire entrer.
Donc, voilà, je me dis qu'en entrant d'abord les moins probables, j'aurais plus de branches à couper.

Si tu arrives à faire rentrer les premier et deuxième objets (respectivement, des poids de 10 et 15, pour un sac de capacité 30), en les considérant dans l'ordre du ratio valeur/poids, tu peux faire rentrer "un peu" du troisième objet (s'il a un poids de 10, tu pourras en faire rentrer la moitié).

OK. Mais quel rapport avec ma question?

Puisque la solution n'est pas réalisable (elle n'est pas entière), ce n'est pas une borne primale ; par contre, ça te donne une borne duale (relâchement linéaire du problème initial, mais sans utiliser le simplexe).

Je n'ai pas compris.