Bonjour a tous,

Je ne traine plus vraiment sur ce forum depuis peu mais je me suis retrouve face a un probleme (que je n'ai pas vraiment cherche a resoudre) qui se pourrait en interesser plus d'uns ici.
Je me dis que ca a l'air d'avoir un lien entre du partitionnement et les premieres theories d'equilibre entre l'offre et la demande en macro-economique des systemes fermes et les optimum de pareto.
Pourtant je seche un peu a premier ordre... mais j'avoue etre flemmard ces jours-ci.

C'est inspire d'un fait reel qui est arrive donc je vais partir sur un exemple concret :

Une grande entreprise decide de brader 6 de ces produits dans un bundle au prix defiant toute concurrence. L'entreprise doit ecouler 1 000 de ces bundles pour vider ses stocks. Le bundle regroupe toujours les 6 memes produits.
Les 6 produits se revelent etre tres differents et peu de personnes se reveleraient interessees par l'acquisition de ces 6 produits. On the other hand, le prix ramene a l'unite se revele tres actif.... que faire ?
Les potentiels acheteurs (nombre fini) decident de monter un topic sur un forum afin de rassembler leur requetes et esperer former des groupes de personnes pouvant acheter le coffret des 6 objets ensemble.

Par exemple user1 voudrait l'objet O1 et O4
user 2 est uniquement interesse par l'objet O3
user3 est interese par O2, O5 et O6

Ensemble ils decident de s'allier pour acheter un bundle et se distribuer les couts entre eux.

Le jeu prend fin lorsqu'il n'y a plus de bundle ou plus de potentiels acheteurs.

On cherche a maximiser le nombre de personnes satisfaites. Une personne est dite satisfaite si et seulement si elle acquiert tous ses objets. On ne gere pas le cas de personne partiellement satisfaite, ca ne nous interesse pas.
Soit S l'ensemble des couples {U, {C1, C2, C3, C4, C5, C6}} avec U un utilisateur satisfait et {C1, C2, C3, C4, C5, C6} le vecteur a valeur dans {0, 1} d'acquisition de ses objets.
Evidemmment pour tout i e {1; 6}, somme pour tout u de S de Ci,u est inferieure ou egale a 1000

Le probleme revient donc a maximiser le cardinal de l'ensemble S.

A vos neuronnes.

PS: Le probleme devrait se resoudre facilement normalement si l'on accepte les situations de bonheur partiel dans notre probleme grace aux theories d'offre et de demande en macro-economie.
Sauf qu'ici vu que l'on ne considere pas ce cas et je ne suis pas sur que le raisonnement soit le meme du coup et ne face pas plutot appel a de l'algorithmique. Sauf si quelqu'un est ici capable de demontrer que l'optimal de la somme des bonheurs (partiels ou totaux) inclut l'optimale des bonheurs totaux. Dans ce cas la il suffirait juste de retrancher les couples dont la demande n'a pas ete entierement satisfaite. Je ne suis pas sur que cette conclusion soit vraie... peut-etre n'est pas si complique a demontrer ou infirmer que cela au final non plus.

deux questions: est ce que un bundle doit etre entierement utilise? (est ce que l'on peu jetter un objet?) Est ce que certains utilisaterus sont interesser a avoir 2 objet O1?

Oui pardon précision importante. Dans le cas général le gâchis n'est pas permis non plus. On ne pourra pas donner une basket si elle n'est pas consommée.

Non la requête est unique pour chaque objet.

pourquoi j'ai écrit une basket moi, je parlais d'un bundle évidemment.

Mon idée grosso modo est de recenser tous les ensembles de requêtes différentes dans un premier temps. Un ensemble est alors simplement résumable à un vecteur + la pondération de son cardinal propre.

Ensuite on recense l'ensemble des combinaisons complémentaires entre ensemble aboutissant à la formation d'un paquet.

Intuitivement on doit aboutir à un système linéaire dont il faut juste optimiser les coefficients (ça on sait faire).

J'ai tout bon ou je suis allé trop vite dans mon raisonnement ?

tbop2, ca revient a de la programmation lineaire en nombre entier. Et ca c'est pas gagner que ca se traite en temps polynomial. (sans que ca soit extremement difficile.)

Cependant, il y a de bonnes propriete au systeme je pense. En particulier si tu as n clients et k objets different, il y a une programmation dynamique en n^k.

Je rush un peu ces temps ci, mais je regarderais ca de plus pres pendant le week end.

Je viens d'ecrire je pense que j'ai la solution oui.

Si tu as k objets différents.

Donc après avoir trouvé l'ensemble R des requêtes différentes + cardinal de chacune. (ça ça coute vraiment quedal). Card (R) etant majore par n.
Apres cette étape sauf erreur de ma part on est debarassé du nombre de clients grosso modo, on a fait un gros filtrage.

Ensuite il faut trouver toutes les combinaisons linéaires possibles entre ces requete independantes R dont la somme vaut le vecteur 1.
C'est un peu long mais il y un avantage c'est que les coefficients linéaires ne peuvent que valoir 1 ou 0 à chaque fois. Le calcul peut tres vite s'arrêter à partir du moment ou on trouve 2 sur une ligne (on peut meme optimiser la rapidité peut-être par un post-traitement qui ferait vite aboutir les collisions entre requete lors des sommations par un re-sorting intelligent de la combinaison (un genre de triangulation)).
C'est une complexité en 2^card(R) si je ne m'abuse.

On en déduit alors le système suivant, ou tout Ki et le nombre de fois ou l'on procède à une combinaison Ci.
Tout Ki est majore par le plus petit cardinal de l'ensemble Rj pour lequel le coefficient est egal à 1.

La restriction supplementaire du systeme impose evidemment que la somme des Ki doit etre inferieure ou egale à k.

Apres ca l'exercice consiste à optimiser les Ki afain de maximiser la fonction :

{somme sur i de Ki * { somme sur j de ai,j * wj } }

Ou ai,j sont les j coefficients lineaires de la combinaison Ci, et wj les j cardinaux respectifs des j ensembles Rj.

PS: la derniere fonction etant evidemment majoree par n.

Hum non je dis de la merde, il faut juste maximiser la somme des Ki.

Non non je redis de la merde, c'était bien bon. Il est temps d'aller se coucher.

Ah bordel à cul non :

{somme sur i de Ki * { somme sur j de ai,j } }

C'est ça qu'il faut optimiser.

il ya une propriete de sous optimalite dans le systeme qui fait qu'une fois que tu as un groupe d'utilisateur qui demande exactement un bundle (ou un ensemble de bundle), tu peux retirer cet ensemble d'utilisateurs sans changer la structure du problmee. Ca n'aide pas au pire cas, mais ca aide enormement en pratique a couper le mechant 2^card{R}.

Pas sur de suivre ton raisonnement sur l'optimisation.

Yo

Ton problème m'a fait marrer, du coup dans la foulée j'ai codé une solution un peu particulière. En fait, pour éviter les problèmes de complexité calculatoire qui vont arriver si tu as des gros bundles et beaucoup de clients, j'ai utilisé une métaheuristique (un recuit simulé) qui cherche à trouver la meilleure solution à ton problème.
Si tu veux checker je t'ai mis le jar exec+les sources ici :
http://temp-share.com/show/YgFHqun0y

La bestiole prend 4 paramètres à l'exécution, c'est décrit dans le code (par ex java -jar bundles.jar 5 6 1000 100) te donnera un petit exemple simple.

han... c'est bien plus moche que je pensais comme probleme.

La contrainte du nombre limite de bundle est super chiante. La contrainte du nombre limite de client de chaque type est egalement super chiant. Ca retire des tonnes d'argument de sous optimalite... Des arguments glouton du genre: "une fois que j'ai trouve un groupe qui marche, je leur fourge un bundle et je recommence recursivement" ne fonctionne pas optimalement. Et mon petit doigt me dit que ca peut meme etre un choix arbitrairement mauvais.

Je commence a rejoindre l'avis de chris (hors bande). Il pense que le probleme est NP-Hard. Ca ressemble peut etre un peu trop a set cover ou a subset sum.

Hum oui ca semble pas etre simple a calculer mais je veux au moins savoir si on modele final est juste ou pas ?

J'ai du mal a le lire comme ca, mais je reecrirait ca en LaTeX proprement ce week end (si je ne me retrouve pas a devoir depiler mes emails de la semaine pendant laquelle note service email est tombe...)

TechnoKatze, j'ai lu ton code mais je ne suis pas sûr qu'il fasse bien ce que je demande et qu'il répondu au sujet en fait.

La solution est un peu plus compliquée que ça je crois

Yo

Le code fourni se contente de résoudre le problème d'optimisation suivant (en reprenant ta notation) :
Etant donné p produits vendus par une entreprise {p1,p2,...,pn} rassemblés au sein d'un bundle B = (p1,p2,...pi), i<= n.
Soit un ensemble {u1,u2,...un} de clients qui souhaitent acheter
chacun certains produits vendus dans le bundle.
On exprime le choix d'achat de l'utilisateur par le vecteur V = (v1,v2,...vi), v in {0,1}.
Les clients s'associent entre eux pour former des bundles complets.
Un groupe de clients n'achète que s'il a pu constituer un bundle complet.
On cherche l'association optimale de clients afin de maximiser le nombre de bundle formables (sachant qu'il en faut au moins 1000) et minimisant le nombre de clients insatisfait (= n'ayant pu former un bundler complet).

Le processus d'optimisation que je t'ai donné répond à la question exacte : "sachant un nombre n de clients, chacun associé à un vecteur de produits souhaités v, et l'ensemble U de toutes les associations de clients possible, quel est le sous-ensemble de U optimal permettant de maximiser le nombre de bundles formés".
Petit raccourci : je considère que puisque l'on forme l'ensemble optimal, il suffit de s'arrêter lorsque le 1000eme bundle est formé, c.a.d que l'ordre de formation des associations n'a pas d'incidence.
Un état de la chaîne de Markov du recuit simulé est généré à partir de deux mouvements : soit on associe 2 groupes existants pour en former un nouveau, soit on retire un client d'un groupe pour le placer dans un autre.
La formulation énergétique quant à elle cherche à minimiser le nombre de 0 dans le sous-ensemble courant, c.a.d le nombre de bundles non terminés ou de clients non satisfaits. Bien sur, si tout est à 1 l'énergie est à 0, on a donc le cas idéal.

Je ne sais pas si ça répond à l'ensemble du problème, mais sans doute à une partie