Cultiver un ensemble donné des contraintes

Question

J'essaie de résoudre ce qui suit:

Étant donné un ensemble $ s_0 $, trouvez min $ | s | $ où $ s_0 subseseq s $ soumis à:

$ forall s in s $ $ exists $ $ s_a, s_b in s $ $ | $ $ (s_a neq s, s_b neq s) land (s = s_a + s_b lor s = 1 lor s = 2) $

Ou en anglais, pour toute s dans s il existe sa, sb dans s tel que sa! = S, sb! = S et (s = sa + sb ou s = 1 ou s = 2)

Par exemple, si $ s_0 = {7, 9, 13, 22 } $, alors la solution est $ s = {1, 2, 3, 4, 7, 9, 13, 22 } $ comme

1 -> is 1 so allowed
2 -> is 2 so allowed
3 = 1 + 2
4 = 1 + 3
7 = 3 + 4
9 = 7 + 2
13 = 9 + 4
22 = 9 + 13
|S| = 8

$ | S_0 | $ n'est pas particulièrement important, mais les chiffres de $ S_0 $ peuvent être très très importants de sorte que l'exprimer tous les chiffres possibles est irréalisable.

J'ai essayé un ILP et manqué de mémoire exprimant les variables binaires pour chaque numéro de l'ensemble.

Mon approche actuelle (qui donne une assez mauvaise solution) est de choisir le nombre le plus bas qui est violé, choisissez heuristiquement deux numéros et les placons dans l'ensemble. Répétez jusqu'à ce que tous les chiffres respectent les contraintes.

Une solution approximative est bien. Quelqu'un a-t-il des idées?