Discussion :

[Guesset]

Bonjour tbc92,

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

Ce qui me gênait était, d'une part, que les 100 tirages piochaient dans 101 valeurs de 0 à 100 et, d'autre part, qu'ils n'étaient pas indépendants (type loterie sans doublon).

Mais pour l'illustration cherchée, c'est OK.

Salut.

[mllm_so]

Liste de 50 nombres - range [1 - 100 000 000] - partitionnée en K_3 sous-ensembles - date.2025-02-19

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
Liste de nombres > https://www.random.org/integer-sets/?sets=1&num=50&min=1&max=100000000&seqnos=on&commas=on&sort=on&order=index&format=html&rnd=date.2025-02-19
 
(3 x 826169315)
 
K_1: (16) 560856 + 5911064 + 19493069 + 25666845 + 37494885 + 38021255 + 51989957 + 55022311 + 58396297 + 62221556 + 68200716 + 69279148 + 69675437 + 81891309 + 88194655 + 94149955 = 826169315
K_2: (17) 1027064 + 7411267 + 11102299 + 12097816 + 25580653 + 30389595 + 31126332 + 51972183 + 52508683 + 57875976 + 59962904 + 66996519 + 80571448 + 80638138 + 80974972 + 84394744 + 91538722 = 826169315
K_3: (17) 8754942 + 13542338 + 13619963 + 20815458 + 22659500 + 24028677 + 27677460 + 34389613 + 47487061 + 62750892 + 64004792 + 66206108 + 75120512 + 76915066 + 87116658 + 88559267 + 92521008 = 826169315

[laurent_ott]

Moi aussi j'y arrive, exemples parmi d'autres :

---------------

(19) 560856, 1027064, 8754942, 19493069, 20815458, 22659500, 34389613, 37494885, 38021255, 47487061, 51972183, 51989957, 52508683, 55022311, 59962904, 66996519, 76915066, 88559267, 91538722
(17) 5911064, 7411267, 11102299, 12097816, 13542338, 25580653, 27677460, 31126332, 62750892, 64004792, 66206108, 68200716, 75120512, 80571448, 88194655, 92521008, 94149955
(14) 13619963, 24028677, 25666845, 30389595, 57875976, 58396297, 62221556, 69279148, 69675437, 80638138, 80974972, 81891309, 84394744, 87116658

---------------

(17) 12097816, 20815458, 25580653, 55022311, 64004792, 69279148, 75120512, 76915066, 80571448, 1027064, 7411267, 30389595, 34389613, 37494885, 51989957, 91538722, 92521008
(18) 560856, 5911064, 11102299, 13619963, 19493069, 38021255, 51972183, 52508683, 62750892, 66206108, 66996519, 69675437, 84394744, 88559267, 22659500, 25666845, 57875976, 88194655
(15) 58396297, 59962904, 62221556, 80638138, 80974972, 81891309, 94149955, 13542338, 24028677, 27677460, 87116658, 8754942, 31126332, 47487061, 68200716

---------------

(17) 5911064, 13542338, 19493069, 34389613, 38021255, 51972183, 75120512, 87116658, 92521008, 25580653, 27677460, 47487061, 58396297, 59962904, 62221556, 62750892, 64004792
(18) 24028677, 30389595, 52508683, 66206108, 68200716, 88194655, 88559267, 1027064, 12097816, 13619963, 20815458, 22659500, 31126332, 37494885, 51989957, 66996519, 69279148, 80974972
(15) 560856, 7411267, 8754942, 11102299, 25666845, 55022311, 57875976, 69675437, 76915066, 80571448, 80638138, 81891309, 84394744, 91538722, 94149955

---------------

Bref, il n'y a pas de quoi casser trois pattes à un canard.
Et je ne vois pas le rapport avec le "défi" du premier message où il faut ventiler 500 nombres compris entre 1 et 10 000 000 en dix groupes de même taille.

[tbc92]

Et dans la question posée à ChatGPT, c'était encore un autre problème, on ne parlait pas de 10 groupes de 100, mais 100 groupes de 10. En combinatoire, on a 10^80 fois plus de cas à analyser si on fait une recherche exhaustive... toute petite différence.

[mllm_so]

@laurent_ott

Moi aussi j'y arrive, exemples parmi d'autres

J'vous rassure j'en doutais pas, d'autres l'on fait bien avant nous et avec des nombres bien plus grands !

Cas de Subset Sum:
Pour le 2eme problème de cette page https://stackoverflow.com/questions/...for-large-sums, les réponses suivantes ont été apportées (je ne les ai pas revérifiées depuis)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
target   : 262988806539946324131984661067039976436265064677212251086885351040000

subset   :   [116883914017753921836437627140906656193895584300983222705282378240000, 65747201634986581032996165266759994109066266169303062771721337760000, 29220978504438480459109406785226664048473896075245805676320594560000, 16436800408746645258249041316689998527266566542325765692930334440000, 12987101557528213537381958571211850688210620477887024745031375360000, 10519552261597852965279386442681599057450602587088490043475414041600, 5367118500815231104734380838102856661964593156677801042589496960000, 3246775389382053384345489642802962672052655119471756186257843840000, 1826311156527405028694337924076666503029618504702862854770037160000, 335444906300951944045898802381428541372787072292362565161843560000, 214684740032609244189375233524114266478583726267112041703579878400, 202923461836378336521593102675185167003290944966984761641115240000]
subset   :   [116883914017753921836437627140906656193895584300983222705282378240000, 65747201634986581032996165266759994109066266169303062771721337760000, 42078209046391411861117545770726396229802410348353960173901656166400, 21468474003260924418937523352411426647858372626711204170357987840000, 7305244626109620114777351696306666012118474018811451419080148640000, 4675356560710156873457505085636266247755823372039328908211295129600, 2629888065399463241319846610670399764362650646772122510868853510400, 1341779625203807776183595209525714165491148289169450260647374240000, 858738960130436976757500934096457065914334905068448166814319513600]
subset   :   [116883914017753921836437627140906656193895584300983222705282378240000, 65747201634986581032996165266759994109066266169303062771721337760000, 42078209046391411861117545770726396229802410348353960173901656166400, 16436800408746645258249041316689998527266566542325765692930334440000, 10519552261597852965279386442681599057450602587088490043475414041600, 7305244626109620114777351696306666012118474018811451419080148640000, 1826311156527405028694337924076666503029618504702862854770037160000, 811693847345513346086372410700740668013163779867939046564460960000, 657472016349865810329961652667599941090662661693030627717213377600, 519484062301128541495278342848474027528424819115480989801255014400, 202923461836378336521593102675185167003290944966984761641115240000]
subset   :   [116883914017753921836437627140906656193895584300983222705282378240000, 65747201634986581032996165266759994109066266169303062771721337760000, 29220978504438480459109406785226664048473896075245805676320594560000, 16436800408746645258249041316689998527266566542325765692930334440000, 12987101557528213537381958571211850688210620477887024745031375360000, 7305244626109620114777351696306666012118474018811451419080148640000, 4675356560710156873457505085636266247755823372039328908211295129600, 3246775389382053384345489642802962672052655119471756186257843840000, 2629888065399463241319846610670399764362650646772122510868853510400, 1826311156527405028694337924076666503029618504702862854770037160000, 1168839140177539218364376271409066561938955843009832227052823782400, 657472016349865810329961652667599941090662661693030627717213377600, 202923461836378336521593102675185167003290944966984761641115240000]
subset   :   [116883914017753921836437627140906656193895584300983222705282378240000, 65747201634986581032996165266759994109066266169303062771721337760000, 29220978504438480459109406785226664048473896075245805676320594560000, 21468474003260924418937523352411426647858372626711204170357987840000, 10519552261597852965279386442681599057450602587088490043475414041600, 7305244626109620114777351696306666012118474018811451419080148640000, 5367118500815231104734380838102856661964593156677801042589496960000, 2629888065399463241319846610670399764362650646772122510868853510400, 2385386000362324935437502594712380738650930291856800463373109760000, 1168839140177539218364376271409066561938955843009832227052823782400, 292209785044384804591094067852266640484738960752458056763205945600]
subset   :   [116883914017753921836437627140906656193895584300983222705282378240000, 42078209046391411861117545770726396229802410348353960173901656166400, 29220978504438480459109406785226664048473896075245805676320594560000, 21468474003260924418937523352411426647858372626711204170357987840000, 16436800408746645258249041316689998527266566542325765692930334440000, 12987101557528213537381958571211850688210620477887024745031375360000, 10519552261597852965279386442681599057450602587088490043475414041600, 5367118500815231104734380838102856661964593156677801042589496960000, 3246775389382053384345489642802962672052655119471756186257843840000, 1826311156527405028694337924076666503029618504702862854770037160000, 1341779625203807776183595209525714165491148289169450260647374240000, 858738960130436976757500934096457065914334905068448166814319513600, 335444906300951944045898802381428541372787072292362565161843560000, 214684740032609244189375233524114266478583726267112041703579878400, 202923461836378336521593102675185167003290944966984761641115240000]
subset   :   [116883914017753921836437627140906656193895584300983222705282378240000, 65747201634986581032996165266759994109066266169303062771721337760000, 42078209046391411861117545770726396229802410348353960173901656166400, 16436800408746645258249041316689998527266566542325765692930334440000, 12987101557528213537381958571211850688210620477887024745031375360000, 3246775389382053384345489642802962672052655119471756186257843840000, 2629888065399463241319846610670399764362650646772122510868853510400, 1826311156527405028694337924076666503029618504702862854770037160000, 657472016349865810329961652667599941090662661693030627717213377600, 292209785044384804591094067852266640484738960752458056763205945600, 202923461836378336521593102675185167003290944966984761641115240000]

Auteur: maxtuno.github.io 
(Je ne sais pas pourquoi, mais cet auteur est identifié sur certains forums / posts, comme peu crédible, complotiste, ou je ne sais quoi d'autre, alors qu'il présente de bons résultats)

Dans mon cas si je m'en tiens (tenais) aux conclusions de chaque "IA" mes résultats (K_1_000) sont à minima révolutionnaires (allez voir les liens) ! D'oû mon questionnement "Quelles sont les limites ..." sachant que je peux partitionner, que ce soit pour le "Balanced Multi Way Number Partitioning" ou le "(Balanced) Bin Packing 1d" des listes bien plus grandes.

Théorie vs réalité:
Au regard des résultats que je présente (et revendique), y'a t'il un expert pour confirmer, infirmer les conclusions que donne les "IA" ?

[mllm_so]

Ok j'reviens à la charge. Après avoir requestionné les IA (Grok, ChatGPT, Gemini, Copilot, Qwen, Deepseek, Perpexity, Mistral..) qui ont toutes donné les mêmes réponses d'infaisabilité, je peux désormais affirmer que tout ce qu'elles disent est absolument faux ! Non pas à cause de mes algos et datas mais parce que après avoir pousser Deepseek dans ses retranchements il m'a pondu un code plutôt efficace. Est ce qu'il le tient de sa "réflexion", je ne sais pas (autodidacte, je ne suis pas au fait de tout ce qui existe). Il donne des résultats similaires à l'un des miens, et l'un ou l'autre se révèlent plus précis sur certains cas.
La différence c'est qu'il nécessite (toujours) plus de mémoire. Cas pour > N = 10000 / K = 1000 (sans contrainte de taille et environnement de dev non-optimal):
Algo deepseek > 300 mo + 1 sec alloué par sous ensemble > temps d'éxecution = 23 sec
Mon (2e) algo > 16 Mo + pas de limite de temps alloué > temps d'éxecution = 7 sec

Bref, quelques corrections pour l'un et l'autre algos pour en faire des outils parfaits (ou presque parfaits ?).

Pourquoi maintenir cette idée d'infaisabilité ?! Mystére...

[dourouc05]

Pourquoi maintenir cette idée d'infaisabilité ?! Mystére...

Parce que, à moins d'un bouleversement profond de la théorie de l'informatique (P = NP), il n'existe pas d'algorithme en temps polynomial pour ce problème. C'est une notion très théorique et inattaquable par des expériences, uniquement par des preuves mathématiques.

Beaucoup de gens continuent de confondre la théorie et la pratique : on résout plein de problèmes NP-hard de très grande taille en pratique. On le fait parfois avec des algorithmes exacts dont le temps d'exécution est exponentiel en la taille du problème (plus rapides que des algos polynomiaux, selon les cas).

Une expérience plus intéressante sur tes algos : sont-ils exacts ? Existe-t-il une meilleure solution, avec un meilleur équilibre entre tes partitions ? Vu ce que tu dis ("plus précis sur certains cas"), je suppose que le résultat n'est pas toujours parfait.
Tu peux ensuite en calculer la complexité (théoriquement) et voir à quel point elle est corrélée avec tes expériences, tant pour le temps d'exécution que la mémoire.
Pour un algorithme non exact, à quel point est-il proche de la meilleure solution ? Parfois, tu peux prouver que tu seras toujours à un facteur 2 ou 1/n de l'optimum pour n nombres à partitionner (comme https://www.ijcai.org/Proceedings/11/Papers/122.pdf).

[mllm_so]

Précision: je suis autodidacte donc n'attendez pas de ma part un langage trop ou trés technique. Je sais juste écrire des algos qui tiennent la route.

il n'existe pas d'algorithme en temps polynomial pour ce problème

Cette affirmation n'est pas claire. On parle pour quels types de cas ?
J'affirme qu'il existe un algo polynomial pour "au moins" toutes listes de nombres aléatoires <= (N = 1 000 000 / K = 250 133); Taille <= ceil(N / K); Range(1, 10 000 000); Target === ceil(sum(N) / K); Mémoire < 2go
Ca c'est c'que j'ai moi déjà publié et je parle même pas de ce que j'ai dans le tiroir...

C'est une notion très théorique et inattaquable par des expériences, uniquement par des preuves mathématiques

Oui mais concurrencée par des démonstrations comme les miennes. D'oû le sujet de ce post.

Une expérience plus intéressante sur tes algos : sont-ils exacts ?

Je n'ai publié sur ces pages que des solutions exactes (et les listes de nombres sont datées du même jour de publication). Ceux qui les ont téléchargées et vérifiées savent...

je suppose que le résultat n'est pas toujours parfait.

Le problème c'est pas qu'il soit parfait mais au moins perfectible.
Tout dépend de l'amplitude (intervalle) des nombres. Même si un algo ne boucle pas parfaitement sur les derniers, une simple correction suffit pour atteindre la perfection.

Mes 2 algos sont au pire Quadratique > O(n²) donc polynomiaux (et nécessitent peu de mémoire). Encore un fois tout dépend pour quels types de cas.

[anapurna]

Salut

selon l'enoncé c'est les 2 cas
le meme nombre d'elements pour chaque categorie
et la meme valeur
ce qui resonnablement semble peu probable a realiser
amoins d'avoir un nombre d'element divisible par le nombre de cathegorie
et une repartition homogene de valeurs

[mllm_so]

Datasets dispo sur: https://github.com/mllmso

Optimal_Multiway_Number_Partitioning (at Scale)

Optimal_Balanced_Multiway_Number_Partitioning (at Scale)

Autre:
Optimal_Balanced_1D_Bin_Packing (at Scale)

[mllm_so]

Datasets dispo:

Optimal_One_Per_Category_Partitioning (variant du balanced number partitioning)

[laurent_ott]

Bonjour,
D'après ce que j'ai compris, vous faites vos analyses sur une plage de données où les éléments sont compris entre "1 à 10 000," pour les répartir, par exemple sur 10 colonnes de 100 éléments.
Le but étant de trouver une solution permettant d'avoir un équilibre de répartition optimale, où au mieux chaque colonne à un écart maximale de 1 par rapport aux autres colonnes.

Je ne suis pas un expert du sujet, mais je pense que la plage entre "1 à 10 000" est trop restreinte. Pour preuve, mon solveur trouve une solution "optimale" en quelque secondes.
Je vous propose donc de changer la plage d'analyse pour passer de "1 à 10 000" à "1 à 100 000 000".

Voir fichier joint (feuille Exemple (1)):
Classeur1 (1).xlsx

Si vous trouvez une meilleure répartition…
Je suis curieux de voir votre solution et comment vous pouvez prouver que c'est la solution optimale ?

Cordialement.

[mllm_so]

Bonjour,

Merci pour votre retour.

Vos 10 sous-ensembles (Exemple 1) comportent des doublons alors que vous avez généré 1000 nombres uniques.

(je n'ai vérifié, rapidement, que 2 sous-ensembles)

Soit vous n'avez pas compris le problème ou alors vous l'avez juste mal exécuté (ainsi que celui qui vous à gratifié d'un pouce vert) .


Explication + illustration en image du problème:

- Nous avons par exemple 3 catégories contenant chacune 4 éléments (de valeurs N).

- Notre objectif est de former des sous-ensembles de somme optimale, en utilisant 1 seul élément de chaque catégorie.

C'est tout.

Disclaimer:
C'est un problème méconnu, parce que (variant de niche) jugé trop complexe d'après ce qu'on peut lire dans les rares sources existantes (Grokipedia, Wikipedia) et d'après mes échanges avec différentes IA (oui je sais, faut pas croire tout ce que raconte les IA mais on fait ce qu'on peut avec ce qu'il y a).

Si vous parvenez à avoir des résultats optimaux pour une plage beaucoup plus large je ne pourrais que vous en féliciter. Vous détenez une contribution intérressante à moins que le problème ne soit en réalité plus facile que ce que rapporte groki, wiki et IA.

Dans mon repo Optimal_Balanced_Multiway_Number_Partitioning se trouve une instance de 1000 nombres [1, 1 000 000 000] parfaitement divisible et divisée en K_12 sous-ensembles:

| 7 | 1,000 | 12 | 84 | [1-1,000,000,000] | k-12-limit-84-target-42280611559 | 100% 🟩 |

Théoriquement je devrais pouvoir obtenir la même optimalité dans sa version OPC.

De manière générale mes résultats publiques ne représente pas forcément le plus haut seuil atteint ou que je puisse atteindre.

ProportionnelLement, (dans mon cas) en taille d'instance ce qui vaut pour petit N vaut pour grand N.

(Pour l'instant une facture d'électricité est bien plus un facteur limitant qu'algorithmique)


Bien à vous.

[EDIT]: je viens de me rendre compte que jl'instance que j'ai donné [7] n'est pas partitionnable en K_12 d'ensembles de même taille (K_12 x 84 != 1000). Elle est juste parfaitement divisible par 12, ça peut toujours servir.

[Guesset]

Bonjour,

Premier message.

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.

Dans ce défi, il n'y a aucun critère d'unicité des valeurs comme ce serait le cas d'une loterie, où on parlerait de tirage au sort et retrait dans une collection de 10 000 000 d'items.

Laurent_ott a simplement respecté le cadre donné.

Par ailleurs, je n'ai vu nulle part (mais je n'ai pas tout lu), les critères de qualification d'une solution opérationnelle. Je présume que c'est l'écart-type ou la variance qui sert d'arbitre.

Tout cela manque singulièrement de rigueur, voire de bonne foi.

Salutations

[mllm_so]

Whaaa...

@Guesse

Bonjour,

Vos questions bien que légitimes arrivent un peu tard et me laisse à penser qu'à aucun moment vous vous êtes donné la peine de vérifier les liens/datas que j'ai donné sinon elles (vos questions) seraient arrivées plus tôt. Donc en matière de bonne foi/honnêteté ça se discute pour l'un et l'autre.

L'instance utilisée avec nombre uniques est celle-ci (je crois): random.org N_500 [1, 10 000 000]

Le partitionnement K_10 que j'ai donné était optimal/exact par rapport aux contraintes mais ne respectait pas la contrainte de somme <=1. J'avais à la place 9 sommes exactes + 1 reste. Mais c'est la même complexité. Vous auriez pu me corrigez mais vous ne l'avez pas fait. (La critique ,même tardive, est toujours plus savoureuse...).

Dans mon repo Optimal_Balanced_Multiway_Number_Partitioning se trouve une instance N_500 [1, 1 000 000 000] qui devrait répondre (j'espère) à vos critères d'unicité et d'optimalité <=1 (vérifiée):

| 6 | 500 | 10 | 50 | [1-1,000,000,000] | k-10-limit-50-target-25596179235 | 100% 🟩 |

Salutations.

[tbc92]

Tu as dit il y a un peu plus d'un an :

il y a un exercice que je sais résoudre, alors que les IA disent que c'est impossible. Qu'en pensez vous.

Hier, on a eu l'énoncé de l'exercice. Bien, on avance.

[laurent_ott]

Bonjour,
J'ai voulu tester une série proposée…
J'ai pris au hasard : https://github.com/mllmso/Optimal_Ba...-50589738.json

Soit 500 données à répartir en 10 groupes de 50 (si j'ai bien compris).
Et devinez-quoi, j'ai trouvé la solution optimale en moins de 10 minutes.
Voir ce classeur : Classeur_500K10.xlsx

Mais j'aimerais bien avoir la réponse à ma dernière question, voir le message numéro 32 du 14/03/2026 à 17h06.
Je proposais une solution et je demandais si vous trouviez mieux.

Cordialement.

[Guesset]

Bonsoir,

Vos questions bien que légitimes arrivent un peu tard et me laisse à penser qu'à aucun moment vous vous êtes donné la peine de vérifier les liens/datas que j'ai donné sinon elles (vos questions) seraient arrivées plus tôt...

Analyser des résultats suppose un problème clairement posé. Ce n'est pas le cas :

1. le défi, par vous défini, est bien celui du message #1. Sauf à croire qu'il y a n définitions à sortir selon l'humeur du jour.
2. la qualification des réponses n'est toujours pas définie. Or sans cela, tout le monde peut monter sur un podium sans crainte.
3. l'incompréhension de la notion de solution optimale reste totale. Une solution optimale ne saurait être relative. Elle doit donc être prouvée. Même la meilleure solution actuelle (selon quels critères ?) ne résout le problème théorique que si elle peut prouver qu'elle est insurpassable.

La processus est simple et générique : on se donne un objectif (votre message #1), on précise la mesure utilisée pour apprécier la tenue de l'objectif (???) et on donne les résultats (relatifs si l'objectif est d'ordre opérationnel ou absolus si on peut démontrer qu'il ne peut y avoir de meilleure solution).

Illustration : soit des résultats qui présentent 10 groupes basés sur un même tirage. Le premier présente 9 groupes égaux et le dernier avec un excédent de 2. Le second présente 8 groupes égaux et 2 groupes avec un excédent de 1. Quelle solution est la meilleure ? Cela dépendant de la mesure. Une mesure de régularité désignera la première solution, car elle a plus de groupes homogènes. Une mesure d'écart-type désignera la seconde, car l'écart-type est sensiblement plus faible.

Si le problème est bien cadré, cela peut mériter d'être étudié. Sinon ce ne sont que des assertions en l'air sans intérêt. Sans des critères d'appréciation clairs, les données, aussi nombreuses soient-elles, ne servent à rien.

Salutations

[mllm_so]

@laurent_ott

J'ai voulu tester une série proposée…
...
Voir ce classeur : Classeur_500K10.xlsx

J'ai checké vite fait votre fichier. Je l'ai pas testé et je sais donc pas sur quelle version du problème vous avez travaillé. BMNP ou OPC ?

Version BMNP: oui je possède aussi cette solution K_10 ainsi que K_25 (mais non présentes dans le repo). C'est une instance uniforme dite "Easy" (à résoudre). De plus les sommes divisibles par 10 sont également plus "faciles". Rien d'étonant/surprenant pour moi (pour celui qui à un bon algo).

Reste à savoir si vous pouvez maintenir cette optimalité à grande échelle (N, K) ou sur différents types d'instances, différents rangs, auquel cas vous avez indéniablement un bon voire un trés bon algo si en plus vous n'êtes pas obligé de recourir à un nombre important de mémoire.

Si vous voulez tester votre algo sur d'autres instances il existe la BPPLIB (orienté bin pack)

Version OCP: vos résultats trahissent la complexité survendue par les quelques sources (groki, wiki, IA). Comme je l'ai dit à part mes félicitations....

Mais j'aimerais bien avoir la réponse à ma dernière question
Je proposais une solution et je demandais si vous trouviez mieux

Mais votre solution contenait des doublons (ou alors c'est moi qui l'ait mal checké). Je l'ai même pas jugé comme une solution approx du problème OPC.

Est ce que je trouve mieux ?
J'ai en partie répndu, sur la partie théorique, dans la pratique à voir..
Pour l'instant c'est pas un objectif et j'avoue avoir un peu rangé "mes outils" (préssé de passé à autre chose et je m'attendais pas à ce qu'on me relance pour de nouvelles datas).

Concernant les ressources (datas) et l'état de l'art du problème OPC en général, y'en a pas ou pas vraiment donc toute contribution optimale est certainnement la bienvenue (mais c'est pas moi qui décide).


@Guesset

La réalité d'hier n'est plus celle d'aujourd'hui.

Aujourd'hui je présente des datas (at scale) dans 3-4 repo distincts dont les solutions ont été vérifiées ce qui est une distinction claire avec prouvées.

Pas de certificat d'optimalité (si c'est ce que vous voulez).
(à tous, demandez à une IA pour plus de détails)

Mathématiquement toutes les solutions répondent aux critères d'optimalité exprimés et il ne peut y avoir meilleures solutions surtout pour celles dont sums / sizes <=1.

Moi à la base j'ai posé une question accompagnée de datas pour un défi proposé par une IA.

A travers mes repos, j'ai répondu moi même à ma propore question en mettant en perspective mes datas (at scale) vs l'état de l'art (voir les docs SOTA inclus dans les repos)

Ca vaut c'que ça vaut. Certificat d'optimalité ou pas mes datas sont optimales !

Cordialement.

[Guesset]

Bonjour,

Au vu du message précédent, il semblerait que les sommes = 0 (modulo le nombre de groupes) soient plus faciles :

De plus les sommes divisibles par 10 sont également plus "faciles".

Pourquoi cela ? Il semble pourtant facile de trouver dans ce cas de figure un contre-exemple avec un optimal apparent non atteignable.

Salutations