Quelles sont les limites actuelles du Balanced Multi-Way Number Partitioning

Bonjour,

Aprés avoir intérrogé 7 "IA" populaires avec la question du même titre, la réponse commune est "qu'on sait pas vraiment".

Par exemple DeepSeek dit:

État actuel (2023) :

N (taille de l'ensemble de nombres) : Les algorithmes exacts peuvent gérer des ensembles de taille modérée (par exemple, N ≈ 50 à 100) en temps raisonnable, mais deviennent rapidement impraticables pour des N plus grands.

K (nombre de sous-ensembles) : Le nombre de sous-ensembles K influence également la complexité. Pour K = 2, le problème est plus simple, mais pour K > 2, la complexité augmente considérablement.

Suite à cela je finis de la part de DeepSeek avec le défi suivant:

Défi proposé:

N (taille de l'ensemble de nombres) : 500 nombres.
Plage des nombres : Chaque nombre est un entier aléatoire compris entre 1 et 10 000 000.
K (nombre de sous-ensembles) : 10 sous-ensembles.

Objectif : Partitionner ces 500 nombres en 10 sous-ensembles de taille égale (50 nombres par sous-ensemble) tout en minimisant la différence entre les sommes des éléments de chaque sous-ensemble.

DeepSeek dit que "Si un tel problème est résolu de manière efficace, cela constituerait un record notable dans le domaine de l'optimisation combinatoire." (Moi: d'autres IA ou personnes diront peut être autre chose, je ne sais pas à voir...)

La pertinence du défi a été validé par toutes les autres "IA", j'ai donc relevé mais surtout réussi le défi !

Pour ceux que ça intéresse, les résultats se trouvent: https://drive.google.com/drive/folde...8_?usp=sharing

Note 1: En plus d'être datée du 2025-02-08, la liste de nombres utilisée provient d'une source externe (voir fichier multiset.txt).
Note 2: Au regard des (autres) datas que je possède, l'interêt tiens plus de l'exercice que du défi.

Au lieu de me mettre des moins 1, feriez mieux de mettre un commentaire et de faire part de votre expertise ! Ttop facile d'arriver des cookies plein la bouche, de pouffer de rire, de mettre son petit moins 1 et de se barrer sans rien justifier ! Exprimez-vous !

Optimal_Balanced_Multi_Way_Number_Partitioning - 10 000 numbers - Range [1 - 1 000 000] - K_1_000 - (2 solutions): - date.2025-02-10
https://drive.google.com/drive/folde...U-?usp=sharing

Ce qu'en pense nos chères "IA" (en gros elles disent que le partitionnement ci-dessus n'est pas possible et que si ça l'était...):
Grok: https://x.com/i/grok/share/08oCP7RbSI8AoKc9HbF8ri9O2
ChatGPT: https://chatgpt.com/share/67ab54af-e...2-adfd524d974d
Gemini: https://g.co/gemini/share/0bac0c59663f
Qwen: https://chat.qwenlm.ai/s/662a877d-ef...5-3266774c1292

Et ici ça dit quoi ? Y'a un expert ?

Bonjour,
Je ne suis pas un expert du sujet, je vais rarement sur ce forum et je viens de découvrir votre discussion.
Je vous invite, puisque c'est une discussion, à présenter plus précisément votre démarche (au lieu de liens sur un site où l'on ne s'y retrouve pas forcément), c'est à dire votre logique de raisonnement, un algorithme, un pseudo code, un exemple de données, pour que l'on puisse rejouer tout ça voir ce que ça donne.
Cordialement.

@laurent_ott
(Vous dîtes ne pas être expert et venir rarement sur ce site alors que vous avez un paquet de publications pointues sur ce dît site. Je vais répondre à votre question même si celle ci semble vouloir me tester)

Ok en termes simples: Officiellement jusqu'à aujourd'hui, on sait pas partitionner efficacement toutes listes de nombres. On sait partitionner les petites mais pas les grandes.

Plus la liste est grande ou que les nombres sont grands, plus il est difficile, voire impossible, d'obtenir un partitionnement respectant les contraintes de somme et de taille pour chaque sous ensembles. Dés lors on utlise des algorithmes d'approximation.

A quoi ça sert ?
A gerer l'espace (disponible), le temps (imparti) et les forces (équilibre).

Dans la communauté scientifique ce genre de problème de partitionnement est majoritairement considéré pour les cas les plus difficiles, comme impossible à résoudre, sauf que si je m'en tiens à ce que disent les "IA", je viens de démontrer le contraire ou du moins en partie !

Les "IA" construisent leurs réponses en amalgamant toutes sortes de publications scientifiques. Elle sont théoriques mais je ne connais pas le gap entre la théorie et la pratique. D'oû la question de ce post "Quelles sont les limites..."

Un expert "honnête" pourra en dire plus. Un expert "honnête", oui, parce que certains préfèrent vous dénigrer (les petits -1 font partie de ce stratagème de dénigrement) ou pire vous insulter !

Pour toutes informations complémentaires je vous suggère d'intéroger une "IA"

- Les exemples de données sont déjà disponibles via les liens précédents https://drive.google..... Je vérrai plus tard pour des petites datas.
- Désolé je n'ai pas de code, ni de méthode à partager.

Citation:

---

Envoyé par mllm_so

On sait partitionner les petites mais pas les grandes.

---

Traduction : on ne peut pas. Si ça ne marche que pour de petits exemples, c'est que c'est inutilisable. Apparemment, tu n'as pas testé si ça marchait pour de petits exemples.

Citation:

---

Envoyé par mllm_so

Dés lors on utlise des algorithmes d'approximation.

---

Ou pas : vive les heuristiques, les approches très généralistes de type MIP ou CP ? Pour beaucoup de problèmes similaires, ça fait des miracles. Tout dépend de ce que tu cherches à faire (ce que tu ne dis pas).

Bonjour,

Si le but est de minimiser la différence entre les sommes d'ensembles de taille égale, la qualité d'un algorithme n'est pas tant de produire un résultat que de pouvoir prouver qu'il est le meilleur possible.

A défaut, ce ne sont que des assertions en l'air.

Par ailleurs, les résultats seuls sont faciles à pipoter :

• tirer au sort les valeurs,
• faire tourner un algorithme même médiocre pour faire la répartition
• reprendre certaines valeurs pour égaliser les sommes et présenter la liste ainsi modifiée comme les valeurs aléatoires originelles.

En résumé, sans l'algorithme et/ou la possibilité de tester avec des jeux de valeurs externes, il n'est pas possible de porter une appréciation réelle.


Salutations

@dourouc05

Citation:

---

Apparemment, tu n'as pas testé si ça marchait pour de petits exemples.

---

Houla, pas de conclusion hâtive. Cà fait déjà 4-5 ans que je balance mes datas sur le net et que j'ai tout de même pris le temps de tester tout type de taille. Vous inquietez pas...

Preuve 1 - Liste de 40 nombres - range [1 - 10000000] - partitionnée en K_3 sous-ensembles

Code:

---

1 2 3 4 5 6 7

Liste de nombres > https://www.random.org/integer-sets/?sets=1&num=40&min=1&max=10000000&seqnos=on&commas=on&order=index&format=html&rnd=date.2025-02-08   (2 x 60761817) + (1 x 60761816)   K_1: (12) 45765 + 1611807 + 2909105 + 4842418 + 5250271 + 5960852 + 6030429 + 6155905 + 6442989 + 6617885 + 6723637 + 8170753 = 60761816 K_2: (14) 652838 + 918717 + 977002 + 1012382 + 1087963 + 2056606 + 2967485 + 4413319 + 4863787 + 7638986 + 8346976 + 8379565 + 8469015 + 8977176 = 60761817 K_3: (14) 1629894 + 1731469 + 2525341 + 3116241 + 3427400 + 3633906 + 3969368 + 4528840 + 4566619 + 4804980 + 5772733 + 6355629 + 6814138 + 7885259 = 60761817

---

Preuve 2 - Liste de 50 nombres - range [1 - 10000000] - partitionnée en K_4 sous-ensembles

Code:

---

1 2 3 4 5 6 7 8

Liste de nombres > https://www.random.org/integer-sets/?sets=1&num=50&min=1&max=10000000&seqnos=on&commas=on&order=index&format=html&rnd=date.2025-02-08   (3 x 59282581) + (1 x 59282578)   K_1: (11) 1012382 + 2090314 + 2525341 + 4528840 + 4842418 + 6030429 + 6442989 + 6814138 + 7638986 + 8379565 + 8977176 = 59282578 K_2: (13) 45765 + 652838 + 918717 + 1275309 + 2967485 + 3427400 + 5768114 + 6155905 + 6355629 + 6617885 + 7718025 + 8170753 + 9208756 = 59282581 K_3: (13) 977002 + 1629894 + 3116241 + 3969368 + 4292558 + 4298284 + 4413319 + 4804980 + 4863787 + 5410859 + 5804756 + 6723637 + 8977896 = 59282581 K_4: (13) 1087963 + 1611807 + 1731469 + 2056606 + 2909105 + 3633906 + 4566619 + 5250271 + 5772733 + 5960852 + 7885259 + 8346976 + 8469015 = 59282581

---

@Guesset

Citation:

---

la qualité d'un algorithme n'est pas tant de produire un résultat que de pouvoir prouver qu'il est le meilleur possible.

---

Pas d'accord, parce que vu la complexité du problème je dirai que pour l'instant "l'important n'est pas le chemin mais l'arrivée".
Quand bien même un algo serait mal écrit, qu'il resterait le meilleur tant qu'il n'a pas de concurents. Enfin chacun voit comme il veut...

Citation:

---

Par ailleurs, les résultats seuls sont faciles à pipoter :
tirer au sort les valeurs,
faire tourner un algorithme même médiocre pour faire la répartition
reprendre certaines valeurs pour égaliser les sommes et présenter la liste ainsi modifiée comme les valeurs aléatoires originelles.

---

Pas concerné puisque les données que j'ai mis à dispositions proviennent justement d'une source externe (voir liens précédents https://drive.google.....). (Vous n'avez pas lu les précédents posts !)

Bonjour mllm_so,

Citation:

---

Envoyé par mllm_so

...Pas d'accord, parce que vu la complexité du problème je dirai que pour l'instant "l'important n'est pas le chemin mais l'arrivée".
Quand bien même un algo serait mal écrit, qu'il resterait le meilleur tant qu'il n'a pas de concurents. Enfin chacun voit comme il veut...

---

Un algorithme qui prétend résoudre un problème ne saurait se contenter d'offrir une solution meilleure que d'autres sans pouvoir garantir que c'est la meilleure. Les meilleures méthodes d'approximation, d'heuristique et autres techniques d'optimisations, peuvent donner de très bons résultats mais ne peuvent garantir que c'est l'optimal. Tant que cet algorithme probant n'existe pas, le problème reste non résolu. Il y a plein de problèmes comme cela pour lesquels n'existent que de bonne solutions sans garantie de l'optimal, ces problèmes (par exemple le voyageur de commerce) restent irrésolus.

Ce n'est pas un point de vue. C'est ce qui justifie la réponse de la communauté scientifique et, par extension, celle des IA. L'algorithme évoqué est peut-être très bon mais s'il ne peut prouver qu'il propose une solution optimale, il reste une approximation et non une solution.

Avoir une bonne approximation, c'est ok, mais cela ne relève pas le défi initial.

Salut

Citation:

---

Cà fait déjà 4-5 ans que je balance mes datas sur le net et que j'ai tout de même pris le temps de tester tout type de taille. Vous inquietez pas

---

Ah... et on aurait dû deviner ça ?

De manière plus générale, habituellement, sur ce forum, on a 2 types d'intervention :
1) très majoritaire, les personnes qui viennent demander de l'aide.
2) très minoritaires, les personnes qui ont trouvé une solution à un problème intéressant, et qui partagent leur travail.
Ces 2 types d'intervention sont bien reçus.

'je suis très fort, j'ai une certaine solution à un certain problème, mais je ne vous en dis pas trop'
Ce 3ème type d'intervention est forcément mal perçu.

@Guesset

Citation:

---

Avoir une bonne approximation, c'est ok, mais cela ne relève pas le défi initial.

---

Je suis bien d'accord avec vous mais je vois pas le rapport avec les résolutions que je viens de donner puisqu'elles sont optimales.

Est ce que mon algo à la prétention de tout résoudre ?
Non. D'ailleurs lorsque je le lance je n'ai même aucune certitude de trouver une solution. Jusqu'à présent j'ai résolu tout ce que je voulais. A partir de là on en pense ce qu'on veut.

@tbc92

Citation:

---

Ah... et on aurait dû deviner ça ?

---

Y'avait rien à deviner mais surtout rien à affirmer ! Mais bon ch'ui cool avec ça. Tous les avis sont les bienvenus.

Citation:

---

'je suis très fort, j'ai une certaine solution à un certain problème, mais je ne vous en dis pas trop'

---

Je pense pas que ça soit la bonne lecture à avoir. Vous mésestimez totalement la portée des résolutions que je viens de donner. Lorsqu'on la saisit on se doute bien que je peux pas partager mon code ! D'ailleurs quel prestigitateur dévoile ses tours ?

Sur ce je passe en résolu.

(mes datas via google/drive ne sont plus accessibles)

Citation:

---

Envoyé par mllm_so

D'ailleurs quel prestigitateur dévoile ses tours ?

---

C'est le principe des communautés et de la recherche. Si on ne dévoile rien de ses astuces, pourquoi venir en parler ici ou ailleurs ?

Si tu ne dévoiles rien de la méthode, pourquoi dévoiler même le résultat ? Peut-être as-tu laissé tourner deux ou trois supercalculateurs avec un algorithme simplissime pour trouver des résultats en explorant toutes les solutions exhaustivement. Certes, tu as une bonne chance d'avoir l'optimum, mais ça n'est pas une avancée pour autant. (Compare avec les solveurs de VRP de NVIDIA : ils ne communiquent pas sur les temps de calcul, il y a un loup.)

Sur un problème similaire, https://github.com/google/or-tools/b...r_heuristics.h (code d'un collègue) résout du set cover en taille énorme bien plus vite que les heuristiques existantes (dans les 15 000 fois plus rapide sur d'énormes instances, largement plus sur de petites).

Citation:

---

Envoyé par Guesset

Un algorithme qui prétend résoudre un problème ne saurait se contenter d'offrir une solution meilleure que d'autres sans pouvoir garantir que c'est la meilleure. Les meilleures méthodes d'approximation, d'heuristique et autres techniques d'optimisations, peuvent donner de très bons résultats mais ne peuvent garantir que c'est l'optimal. Tant que cet algorithme probant n'existe pas, le problème reste non résolu. Il y a plein de problèmes comme cela pour lesquels n'existent que de bonne solutions sans garantie de l'optimal, ces problèmes (par exemple le voyageur de commerce) restent irrésolus.

Ce n'est pas un point de vue. C'est ce qui justifie la réponse de la communauté scientifique et, par extension, celle des IA. L'algorithme évoqué est peut-être très bon mais s'il ne peut prouver qu'il propose une solution optimale, il reste une approximation et non une solution.

---

Sauf que tout le monde part d'une certaine conjecture (P vs. NP) : a priori, on ne devrait jamais trouver d'algorithme qui donne une solution optimale à tous les coups sur tous les problèmes. Chercher cet algo idéal reviendrait à prouver P = NP : beaucoup de gens s'y sont cassé les dents (et produit des résultats intéressants et utiles en chemin).

Il n'empêche qu'on peut considérer certains problèmes comme résolus : il n'y a plus beaucoup d'intérêt à continuer à chercher des solutions pour un TSP, on a des heuristiques pour résoudre dans des temps raisonnables tous les TSP qu'on peut vouloir résoudre en pratique, avec d'excellentes solutions (peut-être pas optimales).

Ce n'est pas un point de vue, c'est un fait reconnu par la communauté scientifique ;). (Point de vue recherche opérationnelle, pas algorithmique fondamentale.)

Bonjour dourouc,

Citation:

---

Envoyé par dourouc05

...Sauf que tout le monde part d'une certaine conjecture (P vs. NP) : a priori, on ne devrait jamais trouver d'algorithme qui donne une solution optimale à tous les coups sur tous les problèmes. Chercher cet algo idéal reviendrait à prouver P = NP : beaucoup de gens s'y sont cassé les dents (et produit des résultats intéressants et utiles en chemin).
Il n'empêche qu'on peut considérer certains problèmes comme résolus : il n'y a plus beaucoup d'intérêt à continuer à chercher des solutions pour un TSP, on a des heuristiques pour résoudre dans des temps raisonnables tous les TSP qu'on peut vouloir résoudre en pratique, avec d'excellentes solutions (peut-être pas optimales).
Ce n'est pas un point de vue, c'est un fait reconnu par la communauté scientifique ;). (Point de vue recherche opérationnelle, pas algorithmique fondamentale.)

---

Il y a effectivement deux domaines d'appréciation : théorique et pratique.

C'est ce que j'essayais de faire comprendre au PO. Une réponse opérationnelle ne garantissant pas l'optimal ne contredit pas la réponse IA sur l'axe théorique.

Un problème est résolu quand on sait trouver et prouver la solution optimale. La nature du problème n'y change rien. Avec un problème NP on sait déjà qu'il y a une solution optimale. Qu'elle ne soit pas atteignable dans un temps raisonnable est un aspect pratique qui amène à se contenter d'algorithmes plus rapides ne garantissant pas l'optimal.

Pratique : ces algorithmes peuvent être suffisamment opérationnels pour être utilisés. Théorique : ils ne sont pourtant pas une résolution du problème sinon P = NP. Or, jusqu'alors, P = NP n'est ni prouvé ni réfuté.

Remarque : un problème n'a pas besoin d'être NP pour nécessiter des approches non exhaustives.

Salut

Bonjour,

J’ai testé plusieurs approches pour développer un algorithme en VBA capable de retrouver le résultat du message 8 avec ses 50 nombres répartis en 4 groupes, et finalement j’ai opté sur un solveur (que j’avais écrit pour faire des rapprochements bancaires) qui cherche les solutions qui s’approchent au mieux de la moyenne. Ça ne marche pas à tous les coups mais ça peut trouver la solution en quelques secondes (voir la feuille « Test_1 » du fichier joint).

J’ai testé sur 1 000 nombres compris entre 1 et 10 000 répartis en 10 groupes de taille égale (feuille « Test_2 ») et ça semble marcher : j’ai 9 groupes dont la somme est égale à la moyenne, et le 10e a un écart de 7.

Comme avec 10 000 nombres compris entre 1 et 100 000 répartis en 10 groupes. C’est plus rapide quand la taille des groupes n’est pas obligatoirement égale (feuille « Test_3 »).

D’où ma question : quand les sommes de tous les groupes sauf un sont égales à la moyenne, et que l’écart entre la moyenne et la somme du dernier groupe et inférieure au nombre de groupes, peut-on considérer que le résultat est optimal ?

Le fichier Excel : Pièce jointe 664570


Cordialement.

Oui ou non, comme tu veux !

La fonction 'objectif' est celle que l'on se fixe. Si on a une somme de 100000004 et qu'on vise 10 groupes, on peut se fixer par exemple ces 2 objectifs (l'un OU l'autre, pas les 2 évidemment):
Objectif 1 : la moyenne (arrondie à l'entier le plus proche) est 10000000 ; on veut 9 groupes avec ce total et un groupe avec 10000004.
ou Objectif 2 : On veut 6 groupes avec 10000000 et 4 groupes avec 10000004.

Ici, clairement, l'objectif visé par le solveur était visiblement l'objectif 1.
Le problème a probablement été mal formulé, parce que dans ma lecture, la discussion visait plutôt l'objectif 2.

Il y a un '''souci''' avec ton expérience (1000 nombres entre 1 et 10000 à répartir en 10 groupes).
J'ai 1000 nombres, dont la somme est de l'ordre de 5 Millions, disons 5 Millions tout rond pour faciliter.
Je veux donc faire 10 groupes qui auront chacun une somme de 500000.

Le nombre de façons de choisir 100 nombres parmi 1000, c'est 10^139, c'est énorme. Et tous ces tirages vont donner des sommes qui varient entre 100 et 1 Million. On a une gaussienne, et si on enlève les totaux extrêmes, environ la moitié de tous ces 10^139 tirages vont donner un résultat entre 450000 et 550000...
Donc il y a vraiment plein d'ex-aequo, plein de tirages qui permettent d'atteindre n'importe quel total voulu, proche de ce 500000.
Il y a tellement de partitions qui donnent la bonne réponse, qu'en trouver une est facile.

Dès qu'on a trouvé une solution où les 10 sous-groupes ont le total voulu, c'est fini.

Si maintenant on prend 1000 nombres aléatoires, mais sur un intervalle BEAUCOUP plus grand (1000 nombres entre 1 et 10^30 par exemple).
Dans ce cas, peut-être que la meilleure combinaison est constituée de sous-groupes dont la somme est très proche de la moyenne, très proche mais pas égale.
Et donc, quand on a une solution qui paraît vraiment bonne, on n'est toujours pas certain qu'il n'y a pas mieux.
Et là, c'est une autre histoire.

On a toujours 1000 nombres à répartir en 10 groupes, mais le problème n'est plus du tout du même ordre.

Et dans l'expérience initiale (500 nombres de l'ordre de 5 Millions à répartir en 10 groupes), on a le même '''souci''', on a plein d'ex-aequo. Certes moins que dans ton expérience, mais quand même plusieurs milliers voire plusieurs millions de solutions qui donnent toutes le résultat visé.

Bonjour,

Vous avez raison de souligner ce biais.
On peut aussi raisonner par l'absurde : Soit un tirage idéalement aléatoire de 100 nombres compris entre 1 et 100 à répartir entre 10 groupes égaux.
Il suffit de classer ces nombres par ordre croissant, de prendre les 5 premiers et les 5 derniers pour avoir un groupe qui vaut 505, idem pour les groupes suivants.

Bonjour laurent_ott,

Citation:

---

Envoyé par laurent_ott

On peut aussi raisonner par l'absurde : Soit un tirage idéalement aléatoire de 100 nombres compris entre 0 et 100 à répartir entre 10 groupes égaux.
Il suffit de classer ces nombres par ordre croissant, de prendre les 5 premiers et les 5 derniers pour avoir un groupe qui vaut 505, idem pour les groupes suivants.

---

Je ne comprends pas comment on peut atteindre 505 (la probabilité d'avoir 5x1 et 5x100 est très très faible). En moyenne les 5 plus petits vaudront environ 10 et les 5 plus grands 490 (485 si 100 n'est pas l'une des valeurs - il y a 100 tirages mais 101 valeurs sinon). On obtient donc une moyenne de 500 (mais la valeur effective pourrait aller de 0 à 10000).

Ceci étant, le principe de les trier est le premier qui vienne à l'esprit. Ne serait-ce que pour faire tomber la complexité première en remarquant qu'un groupe des plus petites valeurs doit se terminer au moins à un indice donné pour ne pas être trop loin de la moyenne. Respectivement pour les plus grands.

Salut

Avec 10 nombres aléatoires entre 1 et 100, 505 est le résultat le plus fréquent.

Bonjour,
Dans ce tirage idéal, les nombres de 1 à 100 sont tirés une fois chacun, donc quand ils sont triés, les 5 premiers + les 5 derniers donne : 1+2+3+4+5+96+97+98+99+100 = 505
Pour le groupe suivant : 6+7+8+9+10+91+92+93+94+95=505.
Ainsi de suite.
Mais c'est absurde, évidement.