Permutations de boites

[Oli1]

Bonjour,

Ma question est la suivante :

Je souhaite faire permuter des boites ayant chacune une valeur et un poids différent d'un ensemble A vers un ensemble B. Il y a une liste de boites différentes dans chaque ensemble A et B. Chaque ensemble a une capacité limitée en poids. Je voudrais savoir s'il existerait d'après vous une méthode ou un algorithme qui permettrait d'améliorer la valeur de la liste des boites de l'ensemble B par la liste des boites de l'ensemble A tout en respectant la limite de poids de l'ensemble B. Existerait-il une solution élégante pour faire cela sans tomber dans une factorielle qui consisterait à combiner toutes les boites de l'ensemble A avec toutes les boites de l'ensemble B pour ne retenir que le groupe de boites qui possède une valeur améliorante ?

En vous remerciant,

O.R.

[GaBuZoMeu]

Bonjour,

Je ne suis pas sûr de bien comprendre ce que tu veux, mais est-ce que ce n'est pas en fait le problème du sac-à-dos ? https://fr.wikipedia.org/wiki/Probl%C3%A8me_du_sac_%C3%A0_dos
Sinon, en quoi est-ce différent ?

[Oli1]

Oui on peut le rattacher au problème du sac à dos, sauf que là je compare deux ensembles de boites (ou deux sacs si tu veux).

[GaBuZoMeu]

Je ne comprends pas la différence. Dans le problème du sac à dos, il y a ce qui est dans le sac-à-dos et ce qui est en dehors du sac-à-dos. Quelle différence avec les deux ensembles ?

[Oli1]

dans le problème sac à dos on a une liste de boites et un sac vide qu'il faut remplir au mieux, alors que là on a un sac plein de boites et une liste de boites à l'extérieur qu'on veut faire permuter avec celles du sac quand cela est possible pour améliorer sa valeur.

[GaBuZoMeu]

Quand tu parles de "permuter", tu veux dire que le nombre de boîtes dans chaque ensemble reste constant ? Les seules manipulations autorisées, c'est d'échanger une boîte de A et une boîte de B ?

[Oli1]

Oui exactement.
si je fais une exploration combinatoire des ensembles de boites de chaque sac sous la forme d'un calcul matriciel j'aurai très probablement la réponse en prenant la plus forte valeur du premier ensemble et en la substituant à la plus faible valeur du second ensemble, mais le problème c'est que si les deux sacs ont chacun un très grand nombre de boites, je risque vite de tomber dans une explosion combinatoire.

[lyceen95]

Autre question :
Quand on permute 2 boites, ça se passe comment ?
Option 1 : j'extrais la boite a de l'ensemble A, la boite b de l'ensemble B, et je les remets, a dans B et b dans A.
Option 2 : j'extrais la boite a de A et je la mets dans B (en vérifiant que la contrainte de poids reste vérifiée), puis j'extrais la boite b de B et je la mets dans A.

L'option 2 est évidemment beaucoup plus contraignante.

[Oli1]

En fait les deux cas que vous mentionnez sont des cas de permutation que je qualifierais de 1-Uplet : 1 boite de l'ensemble A contre 1 boite de l'ensemble B si cette permutation est améliorante. Ces permutations 1-Uplet ne me posent pas de problème particulier. Il suffit d'ordonner de manière inversée les deux listes de boites (celles du sac A que l'on veut faire rentrer en ordre décroissant, celles du sac B que l'on veut faire sortir en ordre croissant) pour créer un effet ciseau entre les deux listes inversées qui sélectionne à l'exacte les candidats potentiels à la permutation. A ce titre le choix entre l'option 1 ou l'option 2 ne me semble pas déterminant (ou alors je ne perçois pas la différence dès lors que l'on effectue bien une permutation entre les deux ensembles avec un effet améliorant). Donc on peut partir sur l'option 1 que vous mentionnez.

En fait ce qui me fait faire de vrais cauchemars et qui me semble beaucoup plus difficile à maîtriser, ce sont les permutations de boites que je qualifie de 2-Uplet. Il y a je pense 3 types de permutations : 1 boite de l'ensemble A contre 2 boites de l'ensemble B, 2 boites de l'ensemble B contre 1 boite de l'ensemble A, et 2 boites de l'ensemble A contre 2 boites de l'ensemble B. Ce qui me semble si problématique dans tous ces cas, c'est que les valeurs et les poids des couples de boites que l'on fait permuter se compensent. Il est donc très difficile de leur appliquer un principe de sélection ordinale. C'est sur ces catégories de permutations 2-Uplet plus spécifiquement que je me questionne pour savoir s'il existerait un modèle algorithmique de traitement.

[GaBuZoMeu]

Dans ton dernier message tu dis le contraire de ce que tu avais précédemment répondu :
Moi : "Les seules manipulations autorisées, c'est d'échanger une boîte de A et une boîte de B ?"
Toi : "Oui exactement. "
et maintenant :
Toi ; "1 boite de l'ensemble A contre 2 boites de l'ensemble B, 2 boites de l'ensemble B contre 1 boite de l'ensemble A, ..."
Faudrait savoir ...

[Oli1]

Bonjour,

Vos observations et questions vont me permettre de préciser ma question en me basant sur un exemple.

Soit deux ensembles (ou deux sacs) A et B. On veut permuter des boites depuis A vers B afin d'améliorer la valeur de la liste des boites de l'ensemble B. L'ensemble B a un poids limite de 934 kg à ne pas dépasser.

Ma question est donc la suivante : Existe-t-il une méthode simple de classement ordinal qui permettrait de faire apparaître le "plus grand groupe de permutation", c'est à dire un troisième ensemble regroupant certaines boites de A et certaines boites de B à faire permuter afin d'améliorer la valeur de la liste de B ?). J'en arrive à cette notion ordinale de "plus grand groupe de permutation" (au sens d'un groupe réunissant le plus grand nombre de boites à permuter) car je suis assez convaincu que c'est ce groupe qui aura dans 99% des cas le plus fort effet améliorant sur l'ensemble B. Et comme qui peut le plus peut le moins, si nous sommes capables de faire apparaître le plus grand groupe de permutation par une méthode ordinale simple, nous saurons également faire apparaitre des groupes de permutation de moindre importance.

Liste des boites : 25 boites

'labore-8': { id: 'labore-8', value: 587, weight: 16 },
'qui-21': { id: 'qui-21', value: 409, weight: 11 },
'iure-16': { id: 'iure-16', value: 920, weight: 133 },
'delectus-23': { id: 'delectus-23', value: 727, weight: 137 },
'quam-13': { id: 'quam-13', value: 414, weight: 67 },
'aut-11': { id: 'aut-11', value: 255, weight: 28 },
'ipsum-22': { id: 'ipsum-22', value: 765, weight: 360 },
'voluptas-15': { id: 'voluptas-15', value: 624, weight: 257 },
'quasi-18': { id: 'quasi-18', value: 800, weight: 498 },
'sunt-5': { id: 'sunt-5', value: 583, weight: 290 },
'reiciendis-1': { id: 'reiciendis-1', value: 641, weight: 383 },
'assumenda-17': { id: 'assumenda-17', value: 858, weight: 755 },
'occaecati-24': { id: 'occaecati-24', value: 716, weight: 552 },
'nobis-12': { id: 'nobis-12', value: 634, weight: 575 },
'corporis-0': { id: 'corporis-0', value: 675, weight: 793 },
'dolorum-6': { id: 'dolorum-6', value: 478, weight: 618 },
'esse-9': { id: 'esse-9', value: 483, weight: 759 },
'distinctio-4': { id: 'distinctio-4', value: 317, weight: 340 },
'doloremque-7': { id: 'doloremque-7', value: 332, weight: 731 },
'pariatur-10': { id: 'pariatur-10', value: 280, weight: 559 },
'consequuntur-14': { id: 'consequuntur-14', value: 215, weight: 740 },
'reiciendis-20': { id: 'reiciendis-20', value: 110, weight: 292 },
'recusandae-19': { id: 'recusandae-19', value: 73, weight: 493 },
'quae-3': { id: 'quae-3', value: 80, weight: 672 },
'corrupti-2': { id: 'corrupti-2', value: 7, weight: 901 }

Ensemble A :

'assumenda-17',
'ipsum-22',
'occaecati-24',
'corporis-0',
'reiciendis-1',
'nobis-12',
'voluptas-15',
'sunt-5',
'esse-9',
'dolorum-6',
'doloremque-7',
'distinctio-4',
'pariatur-10',
'consequuntur-14',
'reiciendis-20',
'quae-3',
'recusandae-19',
'corrupti-2'

Ensemble B : Valeur totale : 1112, Poids total : 890,

'iure-16',
'quasi-18',
'delectus-23',
'labore-8',
'quam-13',
'qui-21',
'aut-11'

[fatal_error]

J'appele combinaison un ensemble de boites
soit MAX_B le poids max de B

On peut dans un premier temps ignorer la validité de MAX_A et se concentrer sur générer toutes les combinaisons valides pour B

On commence avec toutes les boites dans A
Et on commence pour combinaisons de B avec la combinaison vide (de fait..)

on prend la première boite de A
pour chaque combinaison de B
soit on prélève la première boite de A pour la mettre de B:
* on prend alors la combinaison courante et on lui ajoute la boite prélevée
soit on la laisse (idem on conserve la combinaison courante intacte)

* Ici, il reste plus qu'à éviter de générer cette combinaison dans B si il en existe déjà une qui a le même poids avec une valeur supérieure
ET réciproquement, si il en existe déjà une avec le même poids mais dont la valeur est inférieure à la nouvelle, alors il faut remplacer l'existante par la nouvelle

-----

Ensuite si on a une contrainte sur MAX_A aussi
remarquons qu'à deux combinaisons de poids égaux de B, le poids est le même pour sa combinaison "complémentaire" de A.
il ne reste alors qu'à rajouter le check sur le poids de A lorsqu'on observe la meilleure combinaison de B (qui peut-être ne satisfait pas MAX_A)

Code: Tout sélectionner


const boxes = {'labore-8': { id: 'labore-8', value: 587, weight: 16 },
'qui-21': { id: 'qui-21', value: 409, weight: 11 },
'iure-16': { id: 'iure-16', value: 920, weight: 133 },
'delectus-23': { id: 'delectus-23', value: 727, weight: 137 },
'quam-13': { id: 'quam-13', value: 414, weight: 67 },
'aut-11': { id: 'aut-11', value: 255, weight: 28 },
'ipsum-22': { id: 'ipsum-22', value: 765, weight: 360 },
'voluptas-15': { id: 'voluptas-15', value: 624, weight: 257 },
'quasi-18': { id: 'quasi-18', value: 800, weight: 498 },
'sunt-5': { id: 'sunt-5', value: 583, weight: 290 },
'reiciendis-1': { id: 'reiciendis-1', value: 641, weight: 383 },
'assumenda-17': { id: 'assumenda-17', value: 858, weight: 755 },
'occaecati-24': { id: 'occaecati-24', value: 716, weight: 552 },
'nobis-12': { id: 'nobis-12', value: 634, weight: 575 },
'corporis-0': { id: 'corporis-0', value: 675, weight: 793 },
'dolorum-6': { id: 'dolorum-6', value: 478, weight: 618 },
'esse-9': { id: 'esse-9', value: 483, weight: 759 },
'distinctio-4': { id: 'distinctio-4', value: 317, weight: 340 },
'doloremque-7': { id: 'doloremque-7', value: 332, weight: 731 },
'pariatur-10': { id: 'pariatur-10', value: 280, weight: 559 },
'consequuntur-14': { id: 'consequuntur-14', value: 215, weight: 740 },
'reiciendis-20': { id: 'reiciendis-20', value: 110, weight: 292 },
'recusandae-19': { id: 'recusandae-19', value: 73, weight: 493 },
'quae-3': { id: 'quae-3', value: 80, weight: 672 },
'corrupti-2': { id: 'corrupti-2', value: 7, weight: 901 }
}
const MAX_B = 934
const maxWeight = [...Object.values(boxes)].reduce((s, { weight: w }) => s + w, 0)
const MAX_A = maxWeight // 10050

let candidates = new Map([[0, { value: 0, weight: 0, ids: ['identitybox'] }]])
let best = {
  value: 0
}
for (const box of Object.values(boxes)) {
  const next = new Map([...candidates.entries()])
  for (const candidate of candidates.values()) {
    const weight = candidate.weight + box.weight
    if (weight > MAX_B) {
      continue
    }

    const value = candidate.value + box.value
    if (!next.has(weight) || value > next.get(weight).value) {
      const betterCandidate = { value, weight, ids: [box.id, ...candidate.ids] }
      if (value > best.value) {
        const P_A = maxWeight - weight
        if (P_A < MAX_A) {
          console.log('improve', { P_A, betterCandidate })
          best = betterCandidate
        }
      }
      next.set(weight, betterCandidate)
    }
  }
  candidates = next
}



https://jsfiddle.net/g2z5y9kd/

Code: Tout sélectionner

improve {
  P_A: 10049,
  betterCandidate: {
    value: 4264,
    weight: 911,
    ids: [
      'sunt-5',
      'voluptas-15',
      'quam-13',
      'delectus-23',
      'iure-16',
      'qui-21',
      'labore-8',
      'identitybox'
    ]
  }
}


[GaBuZoMeu]

Je comprends de moins en moins la différence avec un classique problème de sac-à-dos.

[GaBuZoMeu]

Comme je suis plus fainéant que fatalerror, j'ai utilisé un module tout fait dans SageMath..

Code: Tout sélectionner

from sage.numerical.knapsack import knapsack

knapsack(seqboites, max=934)

[4264.0,
[(16, 587, 'labore-8'),
(11, 409, 'qui-21'),
(133, 920, 'iure-16'),
(137, 727, 'delectus-23'),
(67, 414, 'quam-13'),
(257, 624, 'voluptas-15'),
(290, 583, 'sunt-5')]]

[Oli1]

Merci à vous tous et plus particulièrement à Fatal Error pour sa réponse très complète !

[Oli1]

[quote="fatal_error"]
Bonjour Fatal Error
J'ai fait tourner le code que vous proposez et je le trouve original dans son approche et intéressant dans ses résultats.
Afin de pousser la réflexion sur cette recherche d'un troisième ensemble, j'aurais une question.

Ma question est la suivante : pensez vous qu'il soit possible de rajouter une contrainte supplémentaire dans le code afin que le résultat obtenu par le tri des boites ne soit plus issu de la somme des boites mais du produit des boites ? Comment organiser le calcul des combinaisons afin que le résultat du tri des ensembles de boites nous permette de factoriser une donnée de départ (de poids et / ou de valeur) qui en serait le produit ?

L'idée serait donc d'indiquer une quantité de départ (sous la forme de poids ou de valeur exacte) et de demander au code de trouver les listes de boites dont la valeur totale ou le poids total en seraient les facteurs.

J'avais en tête les suggestions suivantes :

- Créer autant de sacs (ou ensembles d'arrivée) qu'il y a de facteurs à trouver (2, 3, 4, 5... N).
- Indiquer le nombre de variables à optimiser : j'imagine que pour construire un tel produit, le nombre de variables à optimiser sera égal au nombre de facteurs que l'on veut traiter. Mais par soucis de simplicité peut-être serait-il mieux de travailler sur un cas avec 2 variables à optimiser (poids et valeur) et 2 facteurs.
- Indiquer le produit que l'on recherche. L'idée serait de travailler sur une quantité exacte que l'on indique à l'entrée. Or dans la logique combinatoire de votre code, pensez vous qu'il serait plus efficace de travailler sur : 1. Le produit des poids ou 2. Le produit des valeurs ou 3. Un produit poids*valeur ?
- Dans la perspective de la factorisation, le code ne doit plus seulement chercher à minimiser le poids et maximiser la valeur, mais il doit chercher une quantité exacte (de poids ou de valeur / de poids et de valeur) exprimée sous la forme d'un produit de plusieurs facteurs. D'après vous qu'est-ce que cela change au niveau de la gestion des combinaisons ? Doit-on maintenir les contraintes de maximisation de la valeur et de minimisation du poids afin que le code dispose d'un moyen de différencier les facteurs (par exemple pour chercher le plus petit facteur et le plus grand facteur au cas où on travaille sur un produit de deux facteurs) ou faut-il axer la recherche des facteurs sur d'autres incentives plus efficaces pour produire un résultat exact ?
- Afin de donner toutes les chances au code de trouver les bonnes combinaisons de facteurs lui permettant de générer le produit demandé, j'avais en tête une liste de boites suivantes disponibles par dizaines :
'labore-8': { id: 'labore-8', value: 1, weight: 7 }, * 10
'qui-21': { id: 'qui-21', value: 10, weight: 6 }, * 10
'iure-16': { id: 'iure-16', value: 100, weight: 5 }, * 10
'delectus-23': { id: 'delectus-23', value: 1000, weight: 4 }, * 10
'quam-13': { id: 'quam-13', value: 10.000, weight: 3 }, * 10
'aut-11': { id: 'aut-11', value: 100.000, weight: 2 }, * 10
'ipsum-22': { id: 'ipsum-22', value: 1.000.000, weight: 1 }, * 10
.... etc
Cet ensemble de boites est donc l'ensemble de départ.
(ici il s'agirait de boites avec lesquelles on veut calculer un produit dont les facteurs seraient fournis par la valeur uniquement. Dans l'hypothèse où on voudrait générer le produit par le poids il faudrait inverser l'ordre des données). La valeur maximale de la boite la plus forte est égale à l'échelle décimale du produit à factoriser (que l'on connaît). Cela signifie que l'on dispose bien d'une liste limitée de boites à l'entrée permettant de trouver par combinaison les facteurs par lesquels on souhaite réaliser le calcul du produit recherché.
- Comment traduire cette nouvelle contrainte dans le code que vous avez transmis ?

Je vous remercie pour vos lumières sur ce sujet et vous souhaite une excellente journée.

[fatal_error]

hi,

peut-etre pourrais tu fournir un exemple (minimal) avec sa solution afin d'illustrer
c'est souvent plus parlant

[lyceen95]

Si on veut multiplier des nombres et obtenir un produit le plus petit possible, c'est exactement comme additionner des nombres (et on peut le voir en passant par les logarithmes si besoin).
Si on veut multiplier des nombres entiers, et obtenir un résultat précis N, alors ça permet d'élaguer fortement l'arbre. On connaît les diviseurs de N, et il faut se limiter aux diviseurs de N.

[Oli1]

Bonjour Fatal_Error

Voici un exemple simple avec sa solution, sachant que le but de l'exercice est de voir si l'approche par les combinaisons de boites serait plus performante pour réaliser une factorisation que la recherche classique des diviseurs dont on sait qu'elle nécessite de très nombreuses itérations sur les très grands nombres.

J'ai un ensemble de N boites avec une certaine valeur et un certain poids attaché à chaque boite, et le problème est de choisir au maximum un ensemble de boites comme une liste telle que le produit de leur valeur soit égal à un certain nombre M. Les listes de boites sont triées en fonction de leur poids (ou d'une capacité totale du sac), la liste optimale étant celle dont la somme des poids est la plus faible.

Ex :- l'ensemble des boites est

(box value, box weight) : {(90, 10) , (80, 20), (60, 40), (40, 60), (15, 85), (10, 20},
et le Produit doit être égal à, Prod = 600,

Les solutions possibles sont :-

[Solution 1 :- {(15, 85), (40, 60)} :- Product = 15 * 40 = 600 ; Weight = 85 + 60 = 145
[Solution 2 :- {(60, 40), (10, 20)} :- Product = 60 * 10 = 600 : Weight = 40 + 20 = 60

Ainsi, la liste optimale est {Solution2}.

Sur la base de cet exemple minimal, plusieurs questions se posent qui ont toutes pour point commun de chercher à savoir comment formaliser le problème pour faciliter la production de la combinaison de boites permettant de calculer les facteurs du nombre M. Le problème change de nature dans la mesure où on ne cherche plus seulement une plus grande valeur ou un plus petit poids, mais une valeur exacte.

- Est-il préférable de faire le produit des valeurs et la somme des poids ? (comme dans l'exemple-ci dessus). Est-il préférable de faire la somme des valeurs et le produit des poids ? Est-il préférable de faire le produit de l'ensemble des valeurs et de l'ensemble des poids ? Qu'est-ce qui serait le plus cohérent ?

- S'agit-il de formaliser le problème comme un problème de sac à dos géométrique ? Dans ce cas, la liste des boites aurait la forme d'un ensemble de rectangles de valeurs différentes (on pourrait leur attribuer non pas une mais deux valeurs simultanément) et le nombre M figurerait l'aire d'un sac à dos rectangulaire. Le but serait d'emballer le produit des valeurs des boites dans le sac en prenant la liste qui a le poids minimal.

- Le problème de la recherche de valeur exacte (et plus seulement d'une plus grande valeur ou d'une plus petite valeur) pourrait-il se ramener à un problème de choix des typologies de boites à l'entrée ? Si on donnait la possibilité aux agents de définir librement la liste des boites à l'entrée (en déterminant librement la quantité, le poids et la valeur de chaque boite), quelle règle serait la plus pertinente pour faciliter les combinaisons qui permettront ultérieurement de générer le produit de valeur qui correspond à M ?

L'impression que me donne ce problème de produits est qu'il ne s'agit plus comme dans le problème sac à dos classique de déterminer la liste optimale de boites qui remplira au mieux le sac. Ici j'ai l'impression que ce sont les boites qui vont permettre de définit la forme optimale du sac (ou du moins sa bordure, son entour, sa taille ou son périmètre), comme s'il s'agissait d'un problème géométrique d'enceinte de clôture.

[Oli1]

http://www.cs.umanitoba.ca/~cccg2018/pa ... n5B-p2.pdf