Wrong semantic of precision in Smear-based bisectors

[gchabert]

(in French)
Les bissecteurs Smear ne respectent pas l'interface des bissecteurs (Bsc) car le paramètre de précision 'prec' n'a pas la bonne sémantique.

Normalement, ce paramètre doit correspondre à une précision absolue: on ne bissecte plus [x] si wid([x])<=prec.
Or, dans les cas des bissecteurs Smear, le test fait en réalité semble être wid([x])/|x| <=prec. Ce n'est pas du tout la même chose.

Cela conduit a des comportements inattendus et gênants du solveur.

En effet, la performance de ibexsolve doit être monotone (contrairement à ibexopt), c.a.d. en diminuant la precision, on augmente le temps de calcul et le nombre de cellules. C'est ce qu'on observe avec RoundRobin, mais pas du tout avec SmearSumRelative (le bissecteur par défaut).

Par exemple, lorsqu'on résout le problème suivant avec une précision de 1e-4, on obtient 4 solutions en environ 15 secondes et plus de 30000 boîtes. Lorqu'on le résout avec une précision de 1e-8, on obtient ces 4 solutions en 2.5 secondes et 5000 boîtes !

Constants
	r = 8;
	
Variables
	d1 in [0, r];
	d2 in [0, r];
	d3 in [0, r];
	lambda in [-r, r];
	
Constraints
	-lambda*(- (2*d1^4)/3 + (4*d1^2*d2^2)/3 + (4*d1^2*d3^2)/3 - (2*d2^4)/3 + (4*d2^2*d3^2)/3 - (2*d3^4)/3) = 0;
	(d1 - 5)/3 - 4*lambda*d1*(d2^2 + d3^2 - d1^2)/3 = 0;
	(d2 - 5)/3 - 4*lambda*d2*(d1^2 + d3^2 - d2^2)/3 = 0;
	(d3 - 5)/3 - 4*lambda*d3*(d1^2 + d2^2 - d3^2)/3 = 0;
End

[bneveu]

D'après les logs, c'est effectivement moi qui ai fait cette modif en 2012. Je pense que c'était pour l'optim, mais je ne sais plus exactement pourquoi.
Je vais regarder si avec les derniers ajouts (LSmear et conditions de prise en compte de l'objectif dans les calculs) c'est encore utile et s'il faut 2 variantes de cette stratégie de bissection.

Pour info,
avec mon solver par défaut, (0.01, acidhc4n, compo, smearsumrel)
il n'y a pratiquement aucune différence avec les 2 précisions (3000 boites et 1.7s)

avec celui avec les paramètres du defaultsolver (0.01, acidhc4n, xn, smearsumrel)
la différence de comportement est beaucoup plus faible que celle que tu as obtenue
et le nombre de boites de l'ordre de 6000 et le temps autour de 3.5s , mais effectivement en faveur de la précision 1.e-8

---

résultats avec compo
./solver04 exsmear.bch 0.01 acidhc4n compo smearsumrel 1.e-8 100
file exsmear.bch
time limit 100
filtering acidhc4n
bisection smearsumrel
[solution] (<5, 5> ; <5, 5> ; <5, 5> ; <-0, 0>)
[solution] ([6.666666666666663, 6.666666666666671] ; [3.333333333333331, 3.333333333333335] ; [3.333333333333331, 3.333333333333336] ; [-0.002812500000000003, -0.002812499999999996])
[solution] ([3.333333333333331, 3.333333333333335] ; [6.666666666666663, 6.666666666666671] ; [3.333333333333331, 3.333333333333335] ; [-0.002812500000000003, -0.002812499999999996])
[solution] ([3.333333333333331, 3.333333333333335] ; [3.333333333333331, 3.333333333333336] ; [6.666666666666662, 6.666666666666671] ; [-0.002812500000000003, -0.002812499999999996])
solving successful!

number of solution boxes: 4
number of boundary boxes: --
number of unknown boxes: --
number of pending boxes: --
cpu time used: 1.697593000000001s
number of cells: 3185

number of cells=3185
cpu time used=1.697593000000001s.
nbcidvar 4

---

./solver04 exsmear.bch 0.01 acidhc4n compo smearsumrel 1.e-4 100
file exsmear.bch
time limit 100
filtering acidhc4n
bisection smearsumrel
[solution] (<5, 5> ; <5, 5> ; <5, 5> ; <-0, 0>)
[solution] ([6.666666666666663, 6.666666666666671] ; [3.333333333333331, 3.333333333333335] ; [3.333333333333331, 3.333333333333336] ; [-0.002812500000000003, -0.002812499999999996])
[solution] ([3.333333333333331, 3.333333333333335] ; [6.666666666666662, 6.666666666666671] ; [3.333333333333331, 3.333333333333335] ; [-0.002812500000000004, -0.002812499999999997])
[solution] ([3.333333333333331, 3.333333333333335] ; [3.333333333333331, 3.333333333333335] ; [6.666666666666663, 6.666666666666671] ; [-0.002812500000000003, -0.002812499999999996])
solving successful!

number of solution boxes: 4
number of boundary boxes: --
number of unknown boxes: --
number of pending boxes: --
cpu time used: 1.699233000000001s
number of cells: 3183

number of cells=3183
cpu time used=1.699233000000001s.

---

resultats avec xnewton

./solver04 exsmear.bch 0.01 acidhc4n xn smearsumrel 1.e-8 100
file exsmear.bch
time limit 100
filtering acidhc4n
bisection smearsumrel
[solution] (<5, 5> ; <5, 5> ; <5, 5> ; <-0, 0>)
[solution] ([6.666666666666663, 6.66666666666667] ; [3.333333333333331, 3.333333333333335] ; [3.333333333333331, 3.333333333333336] ; [-0.002812500000000003, -0.002812499999999997])
[solution] ([3.333333333333331, 3.333333333333335] ; [6.666666666666662, 6.666666666666671] ; [3.333333333333331, 3.333333333333335] ; [-0.002812500000000004, -0.002812499999999997])
[solution] ([3.333333333333331, 3.333333333333335] ; [3.333333333333331, 3.333333333333336] ; [6.666666666666662, 6.666666666666671] ; [-0.002812500000000003, -0.002812499999999996])
solving successful!

number of solution boxes: 4
number of boundary boxes: --
number of unknown boxes: --
number of pending boxes: --
cpu time used: 3.364483000000001s
number of cells: 5671

number of cells=5671
cpu time used=3.364483000000001s.

precision 1.e-4
../solver04 exsmear.bch 0.01 acidhc4n xn smearsumrel 1.e-4 100
file exsmear.bch
time limit 100
filtering acidhc4n
bisection smearsumrel
[solution] (<5, 5> ; <5, 5> ; <5, 5> ; <-0, 0>)
[solution] ([6.666666666666663, 6.66666666666667] ; [3.333333333333331, 3.333333333333335] ; [3.333333333333331, 3.333333333333335] ; [-0.002812500000000003, -0.002812499999999997])
[solution] ([3.333333333333331, 3.333333333333335] ; [6.666666666666663, 6.666666666666671] ; [3.333333333333331, 3.333333333333335] ; [-0.002812500000000003, -0.002812499999999996])
[solution] ([3.333333333333331, 3.333333333333335] ; [3.333333333333331, 3.333333333333336] ; [6.666666666666662, 6.666666666666671] ; [-0.002812500000000003, -0.002812499999999996])
solving successful!

number of solution boxes: 4
number of boundary boxes: --
number of unknown boxes: --
number of pending boxes: --
cpu time used: 3.762299000000002s
number of cells: 6093

number of cells=6093
cpu time used=3.762299000000002s.

[bneveu]

Je pense que j'avais ajouté cette condition pour prendre en compte les différences d'ordres de grandeur possibles entre variables : cela permettait d'avoir une condition d'arrêt pour la bissection plus robuste (absolue en dessous de 1 et relative au dessus, continue en 1) sans avoir besoin de déclarer des précisions absolues par variable.
Dans le cas de cet exemple, cela semble contre-productif.

J'ai vérifié pour l'optim ce qui se passe si on remplace cette double condition par la condition simple
(!too_small(box,j)) : les résultats restent les mêmes (sauf pour quelques exemples instables).

Il faudrait aussi vérifier pour tous les exemples du solver.
On pourrait alore simplifier le code en ne gardant qu'une condition d'arrêt avec une précision absolue.

[gchabert]

Merci Bertrand, je vais faire la modification.
En fait, ton idée d'utiliser un critère d'arrêt relatif pour la bissection est assez pertinente; après tout, c'est ce qu'on fait quand on coupe sur le critère en optim. Et l'idéal serait sûrement de pouvoir définir 2 critères de précision en bissection (absolu + relatif) comme en optimisation.
Mon problème est plutôt une question d'uniformité des définitions (avec les autres bisseteurs et le solveur). Mais on peut imaginer de tout changer pour aller dans ton sens.
Je ne sais pas si ça en vaut la peine. Peut-être pas dans l'immédiat mais à garder en tête ?

[gchabert]

Juste un commentaire: c'est effectivement important d'avoir la même définition partout de "précision d'une variable" mais il s'avère que les fluctuations que j'observais dans les temps de calculs n'étaient pas lié qu'à ça. Il y a aussi un problème lié à la définition-même de bissecteur, je vais mettre du coup un autre ticket sur le sujet.

[bneveu]

Il y a aussi des fluctuations qui peuvent être dues au coté aléatoire de X-Newton (choix des coins).
qui peuvent parfois donner un peu plus de noeuds même avec une précision plus grossière

[gchabert]

Oui en effet, l'aléatoire fait perdre aussi la monotonie des arbres de recherche mais c'est moins grave, les fluctuations sont minimes (hormis sur les benchs instables comme bearing...)
En tout cas, si les contracteurs n'ont pas d'aléatoire, le comportement attendu est clairement qu'en diminuant la précision on augmente la taille de l'arbre de recherche. Et là, on observe l'inverse de façon assez "énorme".
Note: il y a aussi le critère d'arrêt du Newton actuellement dans le DefaultSolver qui dépend de la précision, c'est un truc à changer également.