ibexopt et variables entières #507
Comments
|
Bertrand, |
|
Ok pour cet exemple, exint0.bch ibexopt --rigor exint0.bch warning: too many active constraints, cannot prove feasibility -> loup lost! f* in [0,inf] x* = -- le mode normal marche ibexopt exint0.bch x* = (-1) |
|
l'exemple précédent marche avec le mode rigor et la contrainte integer(x) à la place de x=floor(x) ibexopt --rigor exint0.bch f* in [-0,0] x* in (<-1, -1>) |
|
C'est normal que le mode rigoureux échoue avec la contrainte x=floor(x) qui est singulière sur tout entier x. Pour le warning avec interger(x), je pense que cela doit apparaître lorsqu'il essaye de traiter la borne du domaine x=1. Il faudrait mettre une trace pour en être sûr. |
|
Il faudrait, je pense enlever ce warning, qui peut remplir des pages entières dans la résolution de certains problèmes minlp |
|
Bonjour Gilles, Bertrand est motivé pour faire du mixte depuis notre réunion de mardi avec les gens du CEDRIC qui était très intéressante (on pourra faire un point par mail sur ce que la collaboration peut apporter, notamment grâce à leur expertise sur les systèmes quadratiques - convexes ou non). Juste avant cet échange sur le forum de Github, on avait réfléchi à une variante de IbexOpt assez simple où on ajoutait de manière un peu sale/lourde des appels à du "ctcInteger(x) sur toutes les variables" à différentes étapes, par exemple les grosses étapes de la contraction, après HC4, après ACID(HC4), après polytopeHull et HC4 dans le point-fixe, etc. J'ai l'impression, Gilles, que ton idée est de considérer la cte integer(x) comme les autres ctes numériques, ce qui est effectivement plus élégant. On voit l'avantage sur HC4 où à chaque HC4R d'une cte "normale" qui touche au domaine d'une var entière x, la boucle de propagation remet la cte integer(x) dans la queue... Mais il y a plein de questions du fait que ce n'est pas une cte très classique (continue, dérivable), etc. Je pense que ce serait bien qu'on se fasse une visio avec Bertrand et ceux qui ont implanté cette cte integer(x), au moins toi donc, pour bien comprendre comment elle est implantée, ce que ça implique dans PolytopeHull , dans le mode rigoureux et surtout dans LoupFinder (ce n'est pas implanté dans INHC4 si j'ai bien compris, mais quid de InXTaylor ?). Tu pourrais avoir une petite heure la semaine prochaine sur le sujet ? Bon WE à tous en attendant ! |
|
Bonjour, De notre côté aussi, on regarde des choses sur le mixte. On a commencé à définir un bisecteur adapté, mais ce n'est pas forcément facile de récupérer les variables entières dans un système, car seule la contrainte integer permet de les identifier si on part de minibex. Bon week-end, |
|
Salut les gars, Gilles, voici quelques explications. La contrainte Minibex "integer(x)" est en fait immédiatement traduite dans Ibex par "saw(x)=0" avec "saw" la fonction en vert sur la figure suivante:
Comme tu peux le voir, la fonction est discontinue entre 2 entiers mais tout à fait continue et dérivable autour de chaque entier.
Par contre, en effet, pas d'implémentation pour inHC4, mais je peux regarder si vous voulez. Ca paraît simple mais il y a le cas des points au milieu des entiers qui est un peu pénible à gérer proprement en terme d'arrondi. J'avais d'ailleurs un peu galéré pour le backward. Raphaël, effectivement, il n'y a pas de moyen direct de reconnaître une variable entière dans Ibex mais je dirais que c'est presque le but recherché: on traite tout en continu. Je comprends que ça puisse rendre les choses un peu laborieuses si vous souhaitez traiter différemment les variables en fonction de leur type, typiquement pour un bissecteur. Finalement, je trouve ta solution assez adaptée. On peut prévoir une petite réunion si vous avez encore des questions. |
|
J'ai essayé quelques problèmes MINLP de http://www.minlplib.org/instances.html Pour le problème gear4, ibexopt en mode rigueur trouve la solution pour les variables entières, mais n'arrive pas à la prouver avec une précision de 1.e-6. variables minimize constraints end ../../../bin/ibexopt gear4.bch -a 1.e-6 -r 1.e-6 --trace --rigor -t 100 ************************ setup ************************ warning: inHC4 disabled (unimplemented operator) running............ uplo= 0 time limit 100s. reached f* in [1.64319935212,1.643428474] x* in (<16, 16> ; <19, 19> ; <43, 43> ; <49, 49> ; <-0, 0> ; [1.64342847393734, 1.643428473995548]) relative precision on f*: 0.00013943645017 ../../../bin/ibexopt gear4.bch -a 1.e-6 -r 1.e-6 --trace -t 100 ************************ setup ************************ warning: inHC4 disabled (unimplemented operator) running............ uplo= 0 optimization successful! f* in [1.64319771717,1.64319936037] x* = (18.9999999901 ; 15.9999999901 ; 43.00000001 ; 49.00000001 ; 2.13763573034e-09 ; 1.64319935823) relative precision on f*: 9.99999999902e-07 [passed] |
|
Salut les jeunes, Merci Chabs pour les explications. Très rigolo (et élégant) l'utilisation d'une cte integer(x) et d'une implémentation utilisant cette fonction saw(.)... Qui a inventé ça ?? C'est toi, Chabs ? C'est vrai que c'est "so interval" comme approche... Je pense qu'une réunion pour préciser les conséquences de ce choix sera la bienvenue, mais autant attendre le premier retour sur expérience de Bertrand qui expérimente sur des instances de : http://minlplib.org/instances.html J'aurai déjà deux remarques qu'on pourra discuter à cette réunion : a) Pourquoi utiliser integer(x) := saw(x) == 0 plutôt qu'une fonction continue comme integer(x) := sin(\Pi * x) == 0 ? (ou sin (2 * \Pi * x) ==0) Bertrand a déjà expérimenté et ça semble donner des résultats plutôt meilleurs. Je comprends l'intérêt d'avoir une fonction linéaire par morceau, mais le sinus est pas mal foutu non plus (surtout au voisinage des entiers) et a l'avantage d'être continu, déjà implémenté dans Ibex, etc. b) J'admire l'élégance et la concision de la solution "contrainte integer", mais je ne suis pas entièrement, entièrement convaincu de son efficacité. Pour la "contraction" de integer(x), un arrondi de [x] sur les entiers "fait main" (au dessus pour inf(x) et en dessous pour sup(x)) paraît plus efficace que les calculs sur des fonctions saw ou sin, et éviterait les problèmes de "rigueur" (on peut être rigoureux avec ou sans --rigor), mais l'intérêt de l'implémentation actuelle est surtout le calcul de la dérivée je suppose, dérivée qui offre X-Taylor, In-Xtaylor, voire l'arithmétique affine avec une implémentation par sin(\Pi * x) == 0 (j'imagine pas trop le truc avec saw(x)==0...). Il faudrait peut-être pouvoir avoir le meilleur des deux mondes : des arrondis "faits main" pour la contraction et un passage à saw/sinus pour la dérivée... Bref, pas mal de trucs rigolos à discuter après un petit retour sur expérience... |
|
ces contraintes sont effectivement trop faibles en contraction. |
|
Hum. Et quid avec un "eps-h" dédié à ces contraintes (en mode non rigoureux) très précis, de l'ordre de 1e-100, soit : -1e-100 <= saw(x) <= +1e-100 ? |
|
On se rapproche effectivement de l'optimum de la solution entière en baissant eps-h |
|
J'ai essayé d'ajouter dans optimizer04 l'appel à la contrainte CtcInteger sur les variables. |
|
En implémentant les méthodes is_ineffective et effective_ctrs dans ibex_System, comme suggéré dans les commentaires de ibex_System.cpp et en appelant effective_ctrs dans is_inner à la place de active_ctrs , on arrive à résoudre ces problèmes minlp en acceptant des loup avec des solutions entières. Par ailleurs, il semble toujours utile d'avoir une relaxation numérique de la contrainte d'intégrité. J'ai mis quelques problèmes MINLP (les plus petits en nombre de variables de la base http://www.minlplib.org/instances.html comprenant des variables entières et réelles) traduits à la main en minibex dans un nouveau répertoire benchs/optim/benchs-minlp Je continue à tester ces exemples. |
J'ai vu dans #168 qu'on pouvait utiliser ibexopt avec des variables entières en utilisant la contrainte floor.
les résultats que l'on obtient sont parfois un reel "proche" d'un entier.
Est-ce normal et suffit-il d'arrondir à l'entier le plus proche pour avoir la solution ?
exemple exint.bch
variables
x in [-10 ,1];
minimize x^2+x;
constraints
x= floor(x);
end
ibexopt exint.bch
optimization successful!
f* in [-2.00000001004e-08,-6.43762076979e-09]
(best bound)
x* = (-0.999999993562)
(best feasible point)
relative precision on f*: 0.678118963128
absolute precision on f*: 1.35623793308e-08 [passed]
cpu time used: 0.00458300000001s
number of cells: 12
The text was updated successfully, but these errors were encountered: