Wrapper pour CLP (in French)

[gchabert]

Comme indiqué dans l'issue #461, il faut démarrer ce chantier qui est une condition à la réalisation d'un paquet Debian

[raphaelchenouard]

Bonjour,
J'ai commencé à regarder de mon côté. J'ai dupliqué le dossier de soplex et je modifie en m'inspirant du wrapper clp de la version 2.6 et de la doc et des sources de clp. Je ne suis pas sûr ensuite de pouvoir tout bien compilé, car je ne sais pas si je saurai bien définir le fichier cmake. Je reviens ici rapidement pour vous dire comment j'avance.

[cyrilbouvier]

Pour le fichier CMake pour clp, je peux m'en occuper. Je vais esayer d'avoir un premier jet aujourd'hui ou demain

[gchabert]

Super! Et s'il pouvait y avoir un autre volontaire pour aider Raphaël là-dessus, ce serait le top.

[raphaelchenouard]

En attendant de pouvoir compiler voici les 2 fichiers que j'ai définis pour le wrapper clp. Je ne suis pas sûr d'avoir compris le fonctionnement de toutes les méthodes de la classe, donc si vous voyez des choses qui vous semblent étranges, il ne faut pas hésiter à le dire.
ibex_LPLibWrapper.zip

[cyrilbouvier]

Je viens de commiter les fichiers que tu as mis en lien + une première version de scripts CMake pour la détection de Clp. Ca devrait te permettre de tester tes fichiers en passant -DLP_LIB=clp à cmake.
L'installation automatique de Clp s'il n'est pas trouvé n'est pas encore écrit. Il me reste à faire l'installation automatique et à améliorer la détection.

Edit: le message d'erreur que j'obtiens;

[ 33%] Building CXX object src/CMakeFiles/ibex.dir/__/lp_lib_wrapper/clp/ibex_LPLibWrapper.cpp.o
/home/cyril/work/ibex-lib/lp_lib_wrapper/clp/ibex_LPLibWrapper.cpp: In member function ‘void ibex::LPSolver::init(ibex::LPSolver::Mode, double, double, int)’:
/home/cyril/work/ibex-lib/lp_lib_wrapper/clp/ibex_LPLibWrapper.cpp:53:39: error: expected ‘;’ before ‘myclp’
     myclp->setOptimizationDirection(1)
                                       ^
                                       ;
/home/cyril/work/ibex-lib/lp_lib_wrapper/clp/ibex_LPLibWrapper.cpp:55:5:
     myclp->setMaximumIterations(max_iter);
     ~~~~~                              
/home/cyril/work/ibex-lib/lp_lib_wrapper/clp/ibex_LPLibWrapper.cpp: In member function ‘int ibex::LPSolver::add_constraint(double, const ibex::Vector&, double)’:
/home/cyril/work/ibex-lib/lp_lib_wrapper/clp/ibex_LPLibWrapper.cpp:101:31: error: ‘_col1Index’ was not declared in this scope
         myclp->addRow(nb_vars,_col1Index,&(row[0]),lhs,rhs);
                               ^~~~~~~~~~
/home/cyril/work/ibex-lib/lp_lib_wrapper/clp/ibex_LPLibWrapper.cpp:101:59: error: invalid use of non-static member function ‘int ibex::LPSolver::nb_vars() const’
         myclp->addRow(nb_vars,_col1Index,&(row[0]),lhs,rhs);
                                                           ^
In file included from /home/cyril/work/ibex-lib/lp_lib_wrapper/clp/ibex_LPLibWrapper.cpp:1:
/home/cyril/work/ibex-lib/src/numeric/ibex_LPSolver.h:188:9: note: declared here
     int nb_vars() const;
         ^~~~~~~
/home/cyril/work/ibex-lib/lp_lib_wrapper/clp/ibex_LPLibWrapper.cpp:102:16: error: no post-increment operator for type
         nb_rows++;
                ^~
/home/cyril/work/ibex-lib/lp_lib_wrapper/clp/ibex_LPLibWrapper.cpp: In member function ‘int ibex::LPSolver::add_constraint(const ibex::Vector&, ibex::CmpOp, double)’:
/home/cyril/work/ibex-lib/lp_lib_wrapper/clp/ibex_LPLibWrapper.cpp:118:17: error: no match for ‘operator==’ (operand types are ‘ibex::Interval(const ibex::Interval&)’ and ‘ibex::CmpOp’)
         if (sign==LEQ || sign==LT) {
             ~~~~^~~~~
/home/cyril/work/ibex-lib/lp_lib_wrapper/clp/ibex_LPLibWrapper.cpp:118:30: error: no match for ‘operator==’ (operand types are ‘ibex::Interval(const ibex::Interval&)’ and ‘ibex::CmpOp’)
         if (sign==LEQ || sign==LT) {
                          ~~~~^~~~
/home/cyril/work/ibex-lib/lp_lib_wrapper/clp/ibex_LPLibWrapper.cpp:119:35: error: ‘_col1Index’ was not declared in this scope
             myclp->addRow(nb_vars,_col1Index,row.raw(),NEG_INFINITY,rhs);
                                   ^~~~~~~~~~
/home/cyril/work/ibex-lib/lp_lib_wrapper/clp/ibex_LPLibWrapper.cpp:119:72: error: invalid use of non-static member function ‘int ibex::LPSolver::nb_vars() const’
             myclp->addRow(nb_vars,_col1Index,row.raw(),NEG_INFINITY,rhs);
                                                                        ^
In file included from /home/cyril/work/ibex-lib/lp_lib_wrapper/clp/ibex_LPLibWrapper.cpp:1:
/home/cyril/work/ibex-lib/src/numeric/ibex_LPSolver.h:188:9: note: declared here
     int nb_vars() const;
         ^~~~~~~
/home/cyril/work/ibex-lib/lp_lib_wrapper/clp/ibex_LPLibWrapper.cpp:120:20: error: no post-increment operator for type
             nb_rows++;
                    ^~
/home/cyril/work/ibex-lib/lp_lib_wrapper/clp/ibex_LPLibWrapper.cpp:122:22: error: no match for ‘operator==’ (operand types are ‘ibex::Interval(const ibex::Interval&)’ and ‘ibex::CmpOp’)
         else if (sign==GEQ || sign==GT) {
                  ~~~~^~~~~
/home/cyril/work/ibex-lib/lp_lib_wrapper/clp/ibex_LPLibWrapper.cpp:122:35: error: no match for ‘operator==’ (operand types are ‘ibex::Interval(const ibex::Interval&)’ and ‘ibex::CmpOp’)
         else if (sign==GEQ || sign==GT) {
                               ~~~~^~~~
/home/cyril/work/ibex-lib/lp_lib_wrapper/clp/ibex_LPLibWrapper.cpp:123:35: error: ‘_col1Index’ was not declared in this scope
             myclp->addRow(nb_vars,_col1Index,row.raw(),rhs,POS_INFINITY);
                                   ^~~~~~~~~~
/home/cyril/work/ibex-lib/lp_lib_wrapper/clp/ibex_LPLibWrapper.cpp:123:72: error: invalid use of non-static member function ‘int ibex::LPSolver::nb_vars() const’
             myclp->addRow(nb_vars,_col1Index,row.raw(),rhs,POS_INFINITY);
                                                                        ^
In file included from /home/cyril/work/ibex-lib/lp_lib_wrapper/clp/ibex_LPLibWrapper.cpp:1:
/home/cyril/work/ibex-lib/src/numeric/ibex_LPSolver.h:188:9: note: declared here
     int nb_vars() const;
         ^~~~~~~
/home/cyril/work/ibex-lib/lp_lib_wrapper/clp/ibex_LPLibWrapper.cpp:124:20: error: no post-increment operator for type
             nb_rows++;
                    ^~
/home/cyril/work/ibex-lib/lp_lib_wrapper/clp/ibex_LPLibWrapper.cpp: In member function ‘ibex::LPSolver::Status ibex::LPSolver::minimize()’:
/home/cyril/work/ibex-lib/lp_lib_wrapper/clp/ibex_LPLibWrapper.cpp:162:35: error: no matching function for call to ‘ClpSimplex::getStatus()’
     clp_status = myclp->getStatus();
                                   ^
In file included from /home/cyril/work/ibex-lib/lp_lib_wrapper/clp/ibex_LPLibWrapper.h:12,
                 from /home/cyril/work/ibex-lib/src/numeric/ibex_LPSolver.h:22,
                 from /home/cyril/work/ibex-lib/lp_lib_wrapper/clp/ibex_LPLibWrapper.cpp:1:
/home/cyril/work/ibex-lib/dependencies/build/Clp-1.15.6/include/coin/ClpSimplex.hpp:1029:20: note: candidate: ‘ClpSimplex::Status ClpSimplex::getStatus(int) const’
      inline Status getStatus(int sequence) const {
                    ^~~~~~~~~
/home/cyril/work/ibex-lib/dependencies/build/Clp-1.15.6/include/coin/ClpSimplex.hpp:1029:20: note:   candidate expects 1 argument, 0 provided
/home/cyril/work/ibex-lib/lp_lib_wrapper/clp/ibex_LPLibWrapper.cpp: In member function ‘ibex::Matrix ibex::LPSolver::rows() const’:
/home/cyril/work/ibex-lib/lp_lib_wrapper/clp/ibex_LPLibWrapper.cpp:299:31: error: invalid use of non-static member function ‘int ibex::LPSolver::nb_rows() const’
     Matrix A(nb_rows,nb_vars,0);
                               ^
/home/cyril/work/ibex-lib/lp_lib_wrapper/clp/ibex_LPLibWrapper.cpp:274:5: note: declared here
 int LPSolver::nb_rows() const {
     ^~~~~~~~
/home/cyril/work/ibex-lib/lp_lib_wrapper/clp/ibex_LPLibWrapper.cpp:305:30: error: invalid use of member function ‘int ibex::LPSolver::nb_vars() const’ (did you forget the ‘()’ ?)
             for (int cc=0;cc<nb_vars; cc++){
                              ^~~~~~~
/home/cyril/work/ibex-lib/lp_lib_wrapper/clp/ibex_LPLibWrapper.cpp:314:30: error: invalid use of member function ‘int ibex::LPSolver::nb_rows() const’ (did you forget the ‘()’ ?)
             for (int rr=0;rr<nb_rows; rr++){
                              ^~~~~~~
/home/cyril/work/ibex-lib/lp_lib_wrapper/clp/ibex_LPLibWrapper.cpp: In member function ‘ibex::Vector ibex::LPSolver::row(int) const’:
/home/cyril/work/ibex-lib/lp_lib_wrapper/clp/ibex_LPLibWrapper.cpp:335:26: error: call of overloaded ‘Vector(int, int)’ is ambiguous
     Vector Ai(nb_vars(),0);
                          ^
In file included from /home/cyril/work/ibex-lib/src/numeric/ibex_LPSolver.h:19,
                 from /home/cyril/work/ibex-lib/lp_lib_wrapper/clp/ibex_LPLibWrapper.cpp:1:
/home/cyril/work/ibex-lib/src/arithmetic/ibex_Vector.h:68:2: note: candidate: ‘ibex::Vector::Vector(int, double*)’
  Vector(int n, double  x[]);
  ^~~~~~
/home/cyril/work/ibex-lib/src/arithmetic/ibex_Vector.h:55:2: note: candidate: ‘ibex::Vector::Vector(int, double)’
  Vector(int n, double x);
  ^~~~~~
/home/cyril/work/ibex-lib/lp_lib_wrapper/clp/ibex_LPLibWrapper.cpp:336:70: error: ‘i’ was not declared in this scope
     const CoinShallowPackedVector& rowi = myclp->matrix()->getVector(i);
                                                                      ^
/home/cyril/work/ibex-lib/lp_lib_wrapper/clp/ibex_LPLibWrapper.cpp:336:70: note: suggested alternative: ‘Ai’
     const CoinShallowPackedVector& rowi = myclp->matrix()->getVector(i);
                                                                      ^
                                                                      Ai
/home/cyril/work/ibex-lib/lp_lib_wrapper/clp/ibex_LPLibWrapper.cpp: In member function ‘ibex::Vector ibex::LPSolver::col(int) const’:
/home/cyril/work/ibex-lib/lp_lib_wrapper/clp/ibex_LPLibWrapper.cpp:358:26: error: call of overloaded ‘Vector(int, int)’ is ambiguous
     Vector Aj(nb_rows(),0);
                          ^
In file included from /home/cyril/work/ibex-lib/src/numeric/ibex_LPSolver.h:19,
                 from /home/cyril/work/ibex-lib/lp_lib_wrapper/clp/ibex_LPLibWrapper.cpp:1:
/home/cyril/work/ibex-lib/src/arithmetic/ibex_Vector.h:68:2: note: candidate: ‘ibex::Vector::Vector(int, double*)’
  Vector(int n, double  x[]);
  ^~~~~~
/home/cyril/work/ibex-lib/src/arithmetic/ibex_Vector.h:55:2: note: candidate: ‘ibex::Vector::Vector(int, double)’
  Vector(int n, double x);
  ^~~~~~
/home/cyril/work/ibex-lib/lp_lib_wrapper/clp/ibex_LPLibWrapper.cpp:367:12: error: cannot convert ‘ibex::LPSolver::col’ from type ‘ibex::Vector (ibex::LPSolver::)(int) const’ to type ‘ibex::Vector’
     return col;
            ^~~
/home/cyril/work/ibex-lib/lp_lib_wrapper/clp/ibex_LPLibWrapper.cpp: In member function ‘ibex::Vector ibex::LPSolver::cost() const’:
/home/cyril/work/ibex-lib/lp_lib_wrapper/clp/ibex_LPLibWrapper.cpp:423:9: error: ‘dcol’ was not declared in this scope
         dcol[i]=rhs_[i];
         ^~~~
/home/cyril/work/ibex-lib/lp_lib_wrapper/clp/ibex_LPLibWrapper.cpp:423:9: note: suggested alternative: ‘col’
         dcol[i]=rhs_[i];
         ^~~~
         col
/home/cyril/work/ibex-lib/lp_lib_wrapper/clp/ibex_LPLibWrapper.cpp: In member function ‘void ibex::LPSolver::set_cost_to_zero()’:
/home/cyril/work/ibex-lib/lp_lib_wrapper/clp/ibex_LPLibWrapper.cpp:468:16: error: ‘class ClpSimplex’ has no member named ‘setObjCoefficients’; did you mean ‘getObjCoefficients’?
         myclp->setObjCoefficients(i,0);
                ^~~~~~~~~~~~~~~~~~
                getObjCoefficients
/home/cyril/work/ibex-lib/lp_lib_wrapper/clp/ibex_LPLibWrapper.cpp: In member function ‘void ibex::LPSolver::reset(int)’:
/home/cyril/work/ibex-lib/lp_lib_wrapper/clp/ibex_LPLibWrapper.cpp:491:30: error: ‘nb_vars’ cannot be used as a function
         Vector dsrow(nb_vars(),0.0);
                              ^
/home/cyril/work/ibex-lib/lp_lib_wrapper/clp/ibex_LPLibWrapper.cpp:493:31: error: invalid conversion from ‘int’ to ‘const int*’ [-fpermissive]
         myclp->addRow(nb_vars,i,dsrow.raw(),NEG_INFINITY,POS_INFINITY);
                               ^
In file included from /home/cyril/work/ibex-lib/dependencies/build/Clp-1.15.6/include/coin/ClpSimplex.hpp:16,
                 from /home/cyril/work/ibex-lib/lp_lib_wrapper/clp/ibex_LPLibWrapper.h:12,
                 from /home/cyril/work/ibex-lib/src/numeric/ibex_LPSolver.h:22,
                 from /home/cyril/work/ibex-lib/lp_lib_wrapper/clp/ibex_LPLibWrapper.cpp:1:
/home/cyril/work/ibex-lib/dependencies/build/Clp-1.15.6/include/coin/ClpModel.hpp:147:47: note:   initializing argument 2 of ‘void ClpModel::addRow(int, const int*, const double*, double, double)’
      void addRow(int numberInRow, const int * columns,
                                   ~~~~~~~~~~~~^~~~~~~
make[2]: *** [src/CMakeFiles/ibex.dir/build.make:98: src/CMakeFiles/ibex.dir/__/lp_lib_wrapper/clp/ibex_LPLibWrapper.cpp.o] Error 1
make[1]: *** [CMakeFiles/Makefile2:1389: src/CMakeFiles/ibex.dir/all] Error 2
make: *** [Makefile:161: all] Error 2

[raphaelchenouard]

J'ai corrigé la 1ère faute stupide que j'avais faite (; manquant...). Par contre, je suis obligé de faire des pull resquest, c'est normal?
Sinon j'ai essayé de compiler de mon côté et j'ai une erreur, car cmake essaye d'installer clp en cherchant la version 4.0.2 (celle de soplex). De mon côté c'est la version 1.17.3 que j'ai sur ma machine (installé avec homebrew sous macos). J'ai modifié ce numéro de version dans le cmakelist, mais ça ne suffit pas. J'ai essayé aussi de passer le chemin vers clp, mais je ne suis pas sûr de le faire de la bonne manière

$ cmake .. -DCMAKE_INSTALL_PREFIX=/usr/local/Cellar/ibex/dev -DLP_LIB=clp -DINTERVAL_LIB=direct -CLP_LIB=/usr/local/Cellar/clp/1.17.3/lib -CLP_INC_DIR=/usr/local/Cellar/clp/1.17.3/include/clp/coin
loading initial cache file LP_LIB=/usr/local/Cellar/clp/1.17.3/lib
CMake Error: Error processing file: /Users/raphaelchenouard/lib/ibex-lib/build/LP_LIB=/usr/local/Cellar/clp/1.17.3/lib
loading initial cache file LP_INC_DIR=/usr/local/Cellar/clp/1.17.3/include/clp/coin
CMake Error: Error processing file: /Users/raphaelchenouard/lib/ibex-lib/build/LP_INC_DIR=/usr/local/Cellar/clp/1.17.3/include/clp/coin
CMake Warning at CMakeLists.txt:4 (message):
  CMake support is in beta, please report all bugs to
  https://github.com/ibex-team/ibex-lib/issues/


-- Configuring Ibex 2.8.9.1
-- Running on system Darwin-19.6.0 with processor x86_64
-- Using CMake 3.19.1
-- C++ compiler: AppleClang 11.0.0.11000033
-- Will build static libraries
-- Library for interval arithmetic: direct
CMake Warning at interval_lib_wrapper/direct/CMakeLists.txt:6 (message):
  Using INTERVAL_LIB=direct may not give exact results


-- Library for linear programming: clp
-- Could NOT find Clp (missing: CLP_INC_DIR)
-- ######## FALSE
-- Will install and use library Clp from 3rd/ subdirectory
-- Clp: extracting clp-1.17.3.tar
CMake Error at cmake.utils/ibex-install-3rd.cmake:92 (message):
  An error occurs while extracting clp-1.17.3.tar

  See also


  /Users/raphaelchenouard/lib/ibex-lib/build/lp_lib_wrapper/clp/log/extract-*.log

[gchabert]

Raphaël, je viens de t'ajouter comme développeur (tu as du recevoir une invitation); tu pourras faire des push directement.

[cyrilbouvier]

Le script CMake que j'ai écrit rapidement ne fait pas encore l'installation automatique (le code que tu as vu est le copié coller du code du fichier CMakeLists.txt de soplex). Par contre si tu as Clp d'installé sur ta machine, le script devrait pouvoir le détecter.

Tu as fait une erreur dans l'argument pour spécifier le chemin de Clp:

-CLP_LIB=/usr/local/Cellar/clp/1.17.3/lib

Il manque le D après le tiret pour spécifier que tu définis une variable (là tu as donnée à CMake l'option -C qui définit le chemin du cache). Et il n'y a qu'un seul chemin à donner: CLP_DIR.
Ta ligne de commande CMake devrait être:

$ cmake .. -DCMAKE_INSTALL_PREFIX=/usr/local/Cellar/ibex/dev -DLP_LIB=clp -DINTERVAL_LIB=direct -DCLP_DIR=/usr/local/Cellar/clp/1.17.3

[cyrilbouvier]

L'installation automatique de Clp va prendre du temps à écrire, mais j'ai pushé un commit pour clarifier le message d'erreur lorsque CMake ne trouve pas Clp.

[raphaelchenouard]

Oui ce n'est pas simple, car de mon côté clp dépend de la lib coinutils et du coup j'ai une erreur de compilation sur un fichier de cette lib qu'il ne trouve pas...

[cyrilbouvier]

J'ai peut être écrit le script trop vite. C'est quoi ton installation exactement ? Tu as quoi comme message d'erreur ?
Quel est le résultat de la commande: pkg-config --libs clp

[raphaelchenouard]

Bon j'ai refait une install propre de clp avec la dernière version à jour directement sur homebrew et pas ce qui est indiqué sur la page de clp.
Voici l'output de cmake qui se passe mieux :

$ cmake .. -DCMAKE_INSTALL_PREFIX=/usr/local/Cellar/ibex/dev -DLP_LIB=clp -DINTERVAL_LIB=direct               [±develop ✓]
CMake Warning at CMakeLists.txt:4 (message):
  CMake support is in beta, please report all bugs to
  https://github.com/ibex-team/ibex-lib/issues/


-- The CXX compiler identification is AppleClang 11.0.0.11000033
-- Detecting CXX compiler ABI info
-- Detecting CXX compiler ABI info - done
-- Check for working CXX compiler: /Library/Developer/CommandLineTools/usr/bin/c++ - skipped
-- Detecting CXX compile features
-- Detecting CXX compile features - done
-- Configuring Ibex 2.8.9.1
-- Running on system Darwin-19.6.0 with processor x86_64
-- Using CMake 3.19.1
-- C++ compiler: AppleClang 11.0.0.11000033
-- Will build static libraries
-- Setting build type to 'Release' as none was specified.
-- Library for interval arithmetic: direct
CMake Warning at interval_lib_wrapper/direct/CMakeLists.txt:6 (message):
  Using INTERVAL_LIB=direct may not give exact results


-- Performing Test COMPILER_SUPPORTS_FROUNDING_MATH
-- Performing Test COMPILER_SUPPORTS_FROUNDING_MATH - Failed
-- Performing Test COMPILER_SUPPORTS_FFLOAT_STORE
-- Performing Test COMPILER_SUPPORTS_FFLOAT_STORE - Failed
-- Library for linear programming: clp
-- Found PkgConfig: /usr/local/bin/pkg-config (found version "0.29.2")
-- Found Clp: /usr/local/Cellar/clp/1.17.6_1/lib/libClp.dylib
-- Found FLEX: /usr/bin/flex (found version "2.5.35")
-- Found BISON: /usr/bin/bison (found version "2.3")
-- Found CppUnit: /usr/local/lib/libcppunit.dylib
-- Configuring done
-- Generating done
-- Build files have been written to: /Users/raphaelchenouard/ibex-lib/build

J'ai cette erreur:

Scanning dependencies of target ibex
[  1%] Building CXX object src/CMakeFiles/ibex.dir/__/interval_lib_wrapper/direct/ibex_IntervalLibWrapper.cpp.o
[  1%] Building CXX object src/CMakeFiles/ibex.dir/__/lp_lib_wrapper/clp/ibex_LPLibWrapper.cpp.o
In file included from /Users/raphaelchenouard/ibex-lib/lp_lib_wrapper/clp/ibex_LPLibWrapper.cpp:1:
In file included from /Users/raphaelchenouard/ibex-lib/src/numeric/ibex_LPSolver.h:22:
In file included from /Users/raphaelchenouard/ibex-lib/lp_lib_wrapper/clp/ibex_LPLibWrapper.h:12:
In file included from /usr/local/Cellar/clp/1.17.6_1/include/clp/coin/ClpSimplex.hpp:16:
In file included from /usr/local/Cellar/clp/1.17.6_1/include/clp/coin/ClpModel.hpp:19:
/usr/local/Cellar/clp/1.17.6_1/include/clp/coin/ClpPackedMatrix.hpp:9:10: fatal error: 'CoinPragma.hpp' file not found
#include "CoinPragma.hpp"
         ^~~~~~~~~~~~~~~~
1 error generated.
make[2]: *** [src/CMakeFiles/ibex.dir/__/lp_lib_wrapper/clp/ibex_LPLibWrapper.cpp.o] Error 1
make[1]: *** [src/CMakeFiles/ibex.dir/all] Error 2
make: *** [all] Error 2

Et voici le résultat de la commande pkg-config:

$ pkg-config --libs clp
-L/usr/local/Cellar/clp/1.17.6_1/lib -L/usr/local/Cellar/coinutils/2.11.4_1/lib -L/usr/local/opt/openblas/lib -lClpSolver -lClp -lCoinUtils -lbz2 -lz -lopenblas -lm

[cyrilbouvier]

Quel est l'output de

$ pkg-config --cflags clp

Tu utilises Clp 1.17.6, je me suis basé sur Clp 1.15.6 pour écrire les scripts CMake, ils ont peut être changé l'architecture du répertoire d'installation entre les deux versions. Je vais essayer de voir.
@gchabert Avec quelles versions de Clp Ibex doit-il être compatible ?

[raphaelchenouard]

Voici:

$ pkg-config --cflags clp
-I/usr/local/Cellar/clp/1.17.6_1/include/clp/coin -I/usr/local/Cellar/coinutils/2.11.4_1/include/coinutils/coin

[cyrilbouvier]

Ok j'ai compris, Clp et coin ne sont pas installés au même endroit, ce qui était le cas chez moi avec Clp 1.15.6, je vais mettre à jour le script de détection pour prendre ça en compte.

[Jordan08]

Salut,
Il me semble qu'il y a déjà des fichier findCLP.cmake de fait, si ça peut t'aider:
https://github.com/nwojke/mcf/blob/master/cmake/FindClp.cmake
https://graphics.rwth-aachen.de:9000/OpenFlipper-Free/OpenFlipper-Free/blob/8ce6a3e055328654a2f1e4f0932fc8f696b74251/cmake/FindCLP.cmake

En plus, j'ai vu un projet pour compiler clp avec cmake:
https://github.com/ycollet/coinor-clp

Pour ubuntu, il n'y a pas besoin de cmake, je pense, car on utilisera le packet "coinor-clp" dans les dépot standart.

a+

[cyrilbouvier]

J'ai mis à jour le script FindClp.cmake (sur la branche develop). On peut maintenant spécifier COINUTILS_DIR et CLP_DIR séparement. Et le script utilise pkg-config en interne, donc si pkg-config arrive à trouver Clp, il n'y a pas besoin d'utiliser les variables COINUTILS_DIR et CLP_DIR.

[gchabert]

Autre proposition encore plus simple:
On normalise les contraintes pour qu'elles soient de la forme a_i.x=b_i avec ||a_i||=1
Soit A la matrice des contraintes actives en x*. On a donc Ax*=b.
En général n contraintes sont actives au minimum d'un LP donc on peut calculer x1 = l'unique solution de A.x=b-(1,...,1). Cela correspond à une restriction supplémentaire uniforme.
La direction x1-x* est notre direction candidate.
Correct?

[bneveu]

Il se passe par ailleurs un phénomène bizarre que je ne comprends pas et qui me semble être un bug.
Si on essaie de résoudre 2 fois de suite (avec la même graine) le problème sambal avec clp.

il se produit un blocage dans la remontee des uplo au bout de 2mn30 environ à une itération différente :
les loups et uplos affichés jusque là sont les mêmes, mais une exécution affiche quelques remontèes de uplo de plus
que l'autre : il ne se passe ensuite plus rien (pas de nouvel uplo affiché) et les 2 éxécutions sont différentes
jusqu'au timeout (ici fixé à 5 mn).

Les 2 executions divergent donc : une trace fine donne au moment de la divergence
./optimizer04 ../benchs/coconutbenchmark-library1/sambal.bch acidhc4 compo lsmearmg bs 1 1.e-7 1.e-6 1000 1

....
�[33m uplo= 3.967518002143619�[0m
current box ([14.34261113063755, 14.50695834797817] ; [2.878554668362062, 2.929308989354859] ; [126.6821786642622, 127.0066374597283] ; [84.27150060440345, 84.4428577994064] ; [52.38014004964642, 52.72406764459789] ; [175.6894853996629, 176.0523033140771] ; [15.92346040958977, 15.98199452033641] ; [137.3313850948323, 137.5178341994382] ; [22.87117599309152, 22.96844392573334] ; [22.11406851941909, 22.25836509344814] ; [35.33090680487631, 35.61946400808752] ; [49.40310107503239, 49.5793477791731] ; [228.4104823911422, 228.6313366976446] ; [176.2232894401556, 176.468272655508] ; [107.1426766074949, 107.4113017351397] ; [3.967538813652091, 3.968218625870579])
current box ([14.35167335174941, 14.42478473930786] ; [2.878554668362062, 2.929308989354859] ; [126.7848880480761, 126.9870984064722] ; [84.1241583583095, 84.27150060440346] ; [52.41917426719658, 52.64759372332833] ; [175.7628886778143, 176.0105004379953] ; [15.92346040958977, 15.98697218918745] ; [137.3670277547869, 137.4986090253444] ; [22.96844392573333, 23.09516399647464] ; [22.11406851941909, 22.25836509344814] ; [35.47518540648191, 35.61946400808752] ; [49.40341495419534, 49.5793477791731] ; [228.4104823911422, 228.5373401792925] ; [176.2589321001094, 176.5155757991555] ; [107.0926022940427, 107.3566999274684] ; [3.967518002143618, 3.96826733289832])
�[33m uplo= 3.967519740647223�[0m

�[33m uplo= 3.967518002143619�[0m
current box ([14.34261113063755, 14.50695834797817] ; [2.878554668362062, 2.929308989354859] ; [126.6821786642622, 127.0066374597283] ; [84.27150060440345, 84.4428577994064] ; [52.38014004964642, 52.72406764459789] ; [175.6894853996629, 176.0523033140771] ; [15.92346040958977, 15.98199452033641] ; [137.3313850948323, 137.5178341994382] ; [22.87117599309152, 22.96844392573334] ; [22.11406851941909, 22.25836509344814] ; [35.33090680487631, 35.61946400808752] ; [49.40310107503239, 49.5793477791731] ; [228.4104823911422, 228.6313366976446] ; [176.2232894401556, 176.468272655508] ; [107.1426766074949, 107.4113017351397] ; [3.967538813652091, 3.968218625870579])
current box ([14.34261113063755, 14.50695834797817] ; [2.878554668362062, 2.929308989354859] ; [126.6821786642622, 127.0066374597283] ; [84.27150060440345, 84.4428577994064] ; [52.38014004964642, 52.72406764459789] ; [175.6894853996629, 176.0523033140771] ; [15.92346040958977, 15.98199452033641] ; [137.3313850948323, 137.5178341994382] ; [22.87117599309152, 22.96844392573334] ; [22.11406851941909, 22.25836509344814] ; [35.47518540648191, 35.61946400808752] ; [49.40310107503239, 49.5793477791731] ; [228.4104823911422, 228.6313366976446] ; [176.2232894401556, 176.468272655508] ; [107.1426766074949, 107.4113017351397] ; [3.967538813652091, 3.968218625870579])

Par comparaison , avec soplex le problème est résolu en 3mn environ et deux exécutions avec les mêmes paramètres sont identiques.

[gchabert]

Il se passe par ailleurs un phénomène bizarre que je ne comprends pas et qui me semble être un bug.
Si on essaie de résoudre 2 fois de suite (avec la même graine) le problème sambal avec clp.

J'ai constaté aussi une non-reproductibilité de ce genre avec CLP

[goldsztejn-a]

Ca me parait correct oui ! Ca fonctionne aussi sans normaliser les contraintes j'ai l'impression non? La normalisation donnerait peut-être une direction plus "centrée vers l'intérieur"? On peut aussi résoudre Ah = -1 et h est la direction: A(x*+h) = Ax* + Ah = b-1 C'est bon aussi? Alex

…

On Mon, Jan 18, 2021 at 10:26 AM Gilles Chabert ***@***.***> wrote: Autre proposition encore plus simple: On normalise les contraintes pour qu'elles soient de la forme a_i.x=b_i avec ||a_i||=1 Soit A la matrice des contraintes actives en x*. On a donc Ax*=b. En général n contraintes sont actives au minimum d'un LP donc on peut calculer x1 = l'unique solution de A.x=b-(1,...,1). Cela correspond à une restriction supplémentaire uniforme. La direction x1-x* est notre direction candidate. Correct? — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#489 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ADF6P2FR3HRLH73K2HTSN2LS2P5E7ANCNFSM4U5D3UVA> .

-- Dr. Alexandre Goldsztejn CNRS - Laboratoire des Sciences du Numérique de Nantes Mobile : +33 6 78 04 94 87 Web: www.goldsztejn.com Email: [email protected] <http://irccyn.ec-nantes.fr/> @ univ-nantes.fr @gmail.com La science a fait de nous des Dieux, avant même que nous soyons dignes d'être des hommes -- Jean Rostand

[gchabert]

Oui tu as raison, résoudre Ah=-1 c'est encore plus simple et en effet, on n'est pas obligé de normaliser.

J'ai codé le truc aujourd'hui. Ca a l'air de bien fonctionner mais il y a une chose qui m'embête: J'ai voulu retirer la restriction supplémentaire qu'on faisait jusqu'ici puisque désormais inutile.
Mais il y a un bench avec égalités linéaires uniquement où je ne parviens plus à corriger le loup. Une difficulté est de savoir détecter quelles sont les n contraintes vraiment actives. Avec des hyperplans parallèles proches à 1e-8 et les erreurs d'arrondis, pas évident et je tombe très souvent sur une matrice A singulière.

A ce sujet, la technique des multiplicateurs n'étaient finalement pas très fiable car certains sont mis à 0 par la PL alors que la contrainte est presque active. Du coup, j'ai utilisé les mesures d'écart des a_i.x-b_i pour détecter les contraintes presque actives.

Note: le problème se pose aussi bien avec CLP que Soplex. J'ai essayé avec et sans normalisation.

[gchabert]

Ce que je constate aussi sur ce bench, c'est que le mode rigor corrige ça très bien, lui! Logique: il n'a pas à gérer des contraintes quasi-redondantes h(x)=+/-eps_h et qu'il fait un Newton pour converger au plus près.

[gchabert]

Excusez-moi, je fatigue un peu : la singularité de A n'a rien à voir avec mon explication car pour une contrainte relâchée h(x)=+/-eps_h je ne sélectionne que l'une des 2 possibilités pour construire la matrice A (celle pour laquelle apparaît une violation, ou sinon, celle pour laquelle l'écart est le plus proche de 0). En fait, les singularités observées sur ce bench sont probablement intrinsèques au problème (il y a des redondances potentielles avec les contraintes de bornes).

J'ai amélioré entre temps la dichotomie et ça se comporte bien désormais!

Je fais quelques tests plus intensifs et je vous dis ce qu'il en est.

[gchabert]

Quelques news.
Les résultats expés sont plutôt décevants. J'ai testé sur les problèmes indiqués par Bertrand où CLP posait problème. Je n'ai fait qu'une exécution par bench (ce qui n'est pas représentatif mais bon...).
Tout d'abord, le post-processing permet en effet à CLP de résoudre certains problèmes qui étaient en timeout avant (ex5_4_4, srcpm, ex6_2_10), et ce sans aucune restriction supplémentaire, donc en elevant la "tolerance" dans XTaylor.

C'est plutôt positif vous me direz mais la déception vient du fait qu'en remplaçant la "tolerance" par un post-processing, j'espérais observer une amélioration avec Soplex, puisqu'on était censé élargir les restrictions intérieures. Or, ça ne se produit que sur un seul bench (sambal) avec un gain d'environ 10% (donc pas significatif vu qu'il n'y a qu'une exécution). Pour le reste, c'est plus mauvais et on a même un timeout qui apparaît sur harker.

En ajoutant la "tolerance" (donc la combinaison tolerance+post-processing), ça ne change pas des masses.

Conclusion: on pourrait envisager de n'activer le post-processing que lorsque CLP est installé mais je trouve ça lourd (et moche). Je vais donc tester un dernier truc, un post-processing très light qui ne corrige que les contraintes de borne, sans dichotomie.

A+

[trombettoni]

Mister Chabs, heureusement qu'on te connaît. Tu es quand-même le seul gars qui peut annoncer des résultats décevants après avoir réglé le problème de la moitié des benches qui partaient dans les choux avec CLP. Je ne m'en lasserai jamais je crois. ;-)

Dans les côtés positifs, alertés par les expés de Bertrand concernant la restriction supplémentaire dans les linéarisations intérieures, on peut dire qu'en assez peu de temps, un problème important (qui semble poser plus de soucis à CLP qu'à Soplex) a été identifié, alors qu'on pensait que le problème venait (exclusivement) d'un problème dans PolytopeHull (linéarisations extérieures et lowerbounding). De plus, ce problème possède maintenant une solution (post-correction) plus carrée, bien claire mathématiquement. Au moins un début de solution en tout cas.

On n'a peut-être pas encore complètement convergé et il faut donc laisser un peu de maturité à cette voie. Sous réserve que le problème avec Harker soit réel (cad pas lié à un bench instable, ce qui n'aurait alors peut-être aucun rapport avec le débat restrictions intérieures versus post-correction, mais juste avec d'autres choix de bissections ou autres qui dégradent les temps...), je ne comprends pas comment ça peut se produire ? La seule explication que je vois serait que la post-correction ne fonctionne pas tout le temps. Est-ce possible ? (on peut le faire afficher je suppose) A cause des singularités que tu signalais Gilles ?

Test simple peut-être pour avancer : accepter les loups non faisables (à titre expérimental j'entends). Si les versions CLP et Soplex se comportent de manière similaire, alors c'est que le problème vient essentiellement de l'upperbouding, ce qui nous encouragera à blinder la post-correction et/ou le truc de restriction intérieure.

Autre test, sans vouloir insister sur mes propositions du WE ;-) : une post-correction faisant un deuxième appel à In-X-Taylor, mais une version light de ma dernière proposition (que je ne retrouvais plus ci-dessus, mais qui est en fait en réponse au message de Jordan ; je ne maîtrise pas encore complètement ce système de forum, mais j'ai l'impression qu'il y a deux possibilités de reply, une seulement au dernier message (on crée donc une branche) et une globale sur le sujet du fil de discussion ("Wrapper pour CLP"...).

Bref, si on ne lance que les étapes 1 (polytopeHull), 2 (inflation : coût peanut) et 6 (In-X-Taylor le retour) de ma dernière proposition, et seulement en post-correction si le point rendu par le solveur LP est infaisable, on va en gros tripler le temps de calcul de cette opération, qui est elle-même largement dominée par les autres opérations. Donc, on ne devrait pas pouvoir voir apparaître des timeouts et on n'a pas les problèmes de singularités que tu signales... Encore une fois, à titre de test.

[gchabert]

C'est sympa de me vouloir consoler Gilles ;) ... mais bon, la correction triviale que j'ai finalement testée marche aussi bien que le post-processing entier actuel. Cette correction triviale fait la chose suivante: si un loup-point est en dehors de la boîte du système, bah, on le ramène dans la boîte, c'est tout! Je vais le commiter dans develop...

on pensait que le problème venait (exclusivement) d'un problème dans PolytopeHull (linéarisations extérieures et lowerbounding)

En fait, sur les problèmes qui restent en timeout avec CLP, on observe clairement qu'au bout du timeout le loup est très proche du minimum et le uplo très à la traîne. Pas sûr que l'upperbounding soit finalement toujours le problème. Il y avait clairement ce souci d'arrondi chez CLP avec les contraintes de bornes mais il doit y avoir d'autres problèmes qu'il faudrait identifier et qui impactent surtout les relaxations.

On pourrait tester ton idée de post-processing Gilles mais je ne sais pas si ce chantier vaut la peine d'être poursuivi.

Bien sûr, c'est un peu énervant car notre upperbouding cumule deux défauts: 1/ le simplexe est une sur-restriction et 2/ on ne sait pas corriger un loup-point qui sort de ce simplexe. Mais bon si ça marche comme ça...

La seule explication que je vois serait que la post-correction ne fonctionne pas tout le temps. Est-ce possible ? (on peut le faire afficher je suppose) A cause des singularités que tu signalais Gilles ?

Oui, elle ne fonctionne pas tout le temps. A cause des singularités en effet, mais aussi les arrondis dans les calculs, notamment de la direction. En théorie cette direction rentre dans le simplexe mais en pratique il arrive qu'on ne parvienne jamais à certifier qu'un point parmi ceux testés satisfait les contraintes. Les problèmes les pires sont ceux avec des égalités linéaires (pas de marge liée à la linéarisation).

[bneveu]

J'en suis arrivé aux mêmes conclusions sur les problèmes résolus avec Soplex restant non résolus avec CLP: il s'agit de problèmes
contenant des équations linéaires et au bout d'un certain temps, on n'arrive plus à remonter le uplo, alors que le loup est proche
de l'optimal. Il doit y avoir aussi un problème de précision dans CLP dans la relaxation XNewton, qui empêche CLP de trouver des boites vides ou de contracter... à étudier.
OK pour la correction triviale de ramener le loup-point dans la boîte, qui est mieux que réduire arbritairement la boîte de epsilon pour la recherche du loup.

[gchabert]

Je vais lancer une trace des Infeasible avec CLP pour voir.

Rien à signaler de particulier. Fausse piste.

[Jordan08]

Juste au cas où, vous avez regardé du coté de ClpPresolve et CoinPresolve ?
Il y a des variables "feasibilityTolerance" et "ClpPresolveTolerance"
J'ai un peu de mal à trouver tout ce qu'ils font avec.

ça peut venir aussi de problème de scaling. Combiné à la tolérance sur les contraintes, ça peut expliquer l'infesabilité des solutions.
Je sais qu'il y a toujours des tolérances sur les contraintes dans les solvers LP.
Dans CPLEX, c'est IloCplex::Param::Simplex::Tolerances::Feasibility et ça doit être compris entre 1.e-1 et 1.e-9.

Vous avez essayé en désactivant les presolve de Clp?

[Jordan08]

Dans une étude sur les solveurs linéaires: https://prod-ng.sandia.gov/techlib-noauth/access-control.cgi/2013/138847.pdf
Ils ont rencontré le même "genre" de problème. Avec l'algo Primal de Clp, CPLEX2.mps retourne un solution alors qu'en réalité il est infaisable.
En changeant "the feasibility tolerance" à 1.e-8, ça réglait le problème.
Néanmoins il est possible, tout comme CPLEX, qu'il y est un valeur seuil pour cette tolérance.
En tout cas, l'algorithme Dual a l'air d'avoir moins de problème, mais sait-on jamais.
L'algo Primal et l'algo Dual ont l'air d'avoir des comportement très différent.
Là dans le code c'est l'algo dual de choisi ligne 128 du Wrapper. Est-ce que le problème a lien avec l'algo Primal?

[raphaelchenouard]

Edit: je n'ai testé que de résoudre le primal plutot que le dual, je n'ai pas changé les tolérances.

En testant rapidement ce que tu suggères Jordan, les tests implémentés ne donnent pas les mêmes résults selon si on résout le primal ou le dual.
Avec le primal:

!!!FAILURES!!!
Test Results:
Run:  18   Failures: 3   Errors: 0


1) test: ibex::TestLinearSolver::kleemin30 (F) line: 138 /Users/raphaelchenouard/lib/ibex-lib/tests/TestLPSolver.cpp
assertion failed
- Expression: false


2) test: ibex::TestLinearSolver::p25fv47 (F) line: 187 /Users/raphaelchenouard/lib/ibex-lib/tests/TestLPSolver.cpp
assertion failed
- Expression: lp.status() == LPSolver::Status::Optimal


3) test: ibex::TestLinearSolver::test_easy_feasible_certified (F) line: 155 /Users/raphaelchenouard/lib/ibex-lib/tests/utils.cpp
assertion failed
- Expression: y_actual!=NEG_INFINITY

Avec le dual:

!!!FAILURES!!!
Test Results:
Run:  18   Failures: 4   Errors: 0


1) test: ibex::TestLinearSolver::kleemin30 (F) line: 138 /Users/raphaelchenouard/lib/ibex-lib/tests/TestLPSolver.cpp
assertion failed
- Expression: false


2) test: ibex::TestLinearSolver::p25fv47 (F) line: 187 /Users/raphaelchenouard/lib/ibex-lib/tests/TestLPSolver.cpp
assertion failed
- Expression: lp.status() == LPSolver::Status::Optimal


3) test: ibex::TestLinearSolver::test_easy_feasible_certified (F) line: 155 /Users/raphaelchenouard/lib/ibex-lib/tests/utils.cpp
assertion failed
- Expression: y_actual!=NEG_INFINITY


4) test: ibex::TestLinearSolver::test_infeasible_certified (F) line: 426 /Users/raphaelchenouard/lib/ibex-lib/tests/TestLPSolver.cpp
assertion failed
- Expression: lp_cert.status() == LPSolver::Status::InfeasibleProved

[raphaelchenouard]

J'ai aussi oublié de répondre à la question concernant l'utilisation du pb dual. Je ne suis pas assez expert et connaisseur de l'usage du solveur LP dans ibex, donc je me suis contenté de faire comme le précédent wrapper. Je laisse Gilles, Bretrand ou autre testé avec le dual s'ils veulent investiguer plus en profondeur. Il suffit de modifier la ligne indiquée par Jordan (128) pour mettre primal() à la place de dual().

[bneveu]

J'ai fait quelques essais avec la résolution primal() au lieu de dual().
Globalement, c'est a peu près équivalent : les problèmes non résolus le restent.
ex8_4_6 ne plante pas, mais converge lentement.

J'ai aussi essayé de jouer avec le paramètre de tolérance, mais sans succès.

La seule modification qui a un peu amélioré (permis de résoudre ramsey) est de doubler la restriction supplémentaire sur la linéarisation des contraintes pour la recherche de loup (2.e-9 au lieu de 1.e-9) : on a peut-être un peu moins de loup-points infaisables.

[gchabert]

J'ai fait quelques essais avec la résolution primal()

Pour info, j'ai essayé aussi avec le "mode 1" (il y a deux modes possibles quand on appelle primal()) et pas de changement drastique non plus.

Peut-être une nouvelle piste:
J'ai réalisé que les problèmes linéaires que l'on génère avec ibex ont une autre particularité importante: le critère qu'on minimise (+/- x_i) est systématiquement colinéaire à deux contrainte du simplexe, les contraintes de bornes l<=x_i<=u. Et quand le critère ne dépend linéairement que d'une seule contrainte, je pense que la conséquence est qu'une face entière du Simplexe est également solution (quand la contrainte en question est active).

Sur un bench-type (où CLP explose), je remarque alors que CLP et Soplex ne fournissent effectivement pas du tout les mêmes solutions et que CLP active systématiquement plus de contraintes, comme s'il retournait quoi qu'il arrive un sommet du simplexe là où Soplex se contente d'un point intérieur (Note: je n'ai pas vérifié, c'est une hypothèse. J'ai juste comparé le nombre de contraintes de bornes actives, qui est toujours supérieur avec CLP sur ce bench).

Il est alors possible que l'heuristique d'Achterberg implantée actuellement (qui visiblement repose justement sur l'activation des contraintes de bornes) soit induite en erreur par ces activations artificielles.
Cela pourrait expliquer que des variables "sautent" et que le filtrage soit incomplet.

Ce serait donc peut-être une explication au fait que le nombre de boîtes explose parfois avec CLP versus Soplex. Si le solveur était juste plus lent, on devrait avoir le même nombre de boîtes. Et s'il était juste moins précis dans les arrondis, cela devrait ne devrait pas (ou peu) jouer avec des critères d'arrêt comme 1e-3.

[bneveu]

L'heuristique d'Achterberg permet d'éviter des appels au Simplexe inutiles. Si une solution du polytope est proche à epsilon près d'une borne, on est sûr qu'on ne pourra pas réduire cette borne de plus de epsilon.
Si on enlève cette heuristique, les temps de calcul augmentent beaucoup (plus d'un ordre de grandeur sur certains problèmes).
J'ai essayé de faire varier cet epsilon, mais sans grand succès.
Sur les problèmes où CLP n'arrive plus à remonter le uplo (ou bien où cette vitesse de remontée devient très lente) à partir d'un certaine valeur du uplo, cette valeur du uplo augmente quand le epsilon de l'heuristique d'Achterberg diminue, mais le blocage finit par arriver. Les problèmes restent non résolus.
Cas particulier encore plus bizarre où la non reproductibilité de CLP apparaît.
pour ex5_4_4 avec eps_h=1.e-6 (au lieu de 1.e-8) et eps_Achterberg=1.e_12 (au lieu de 1.e-8),
certaines exécutions avec la même graine réussissent en 100s et d'autres sont en timeout à 1000s (avec loup bloqué après 100s)

[trombettoni]

Une parenthèse sur l'heuristique de Achterberg et le paramètre eps_Achterberg.

De manière générale, je crois qu'on pourra organiser des Ibex days et ne discuter que de ces epsilons de grande cuisine.

D'autre part, et de manière générale encore, il me semble plus robuste de fixer les epsilons de manière relative à une taille courante (de boîte par exemple) si on peut.

Puisqu'on a la main sur cette heuristique implantée maison (par Bertrand je crois), ne peut-on pas envisager un eps_Achterberg "relatif" (à la taille de x_i) ? Par exemple, ne pas lancer le simplexe sur une dimension i (en minimisation disons) si d_i / w(x_i) < eps_Achterberg (fixé en dur à qque chose entre 1e-3 et 1e-6 après expés), où d_i est la distance entre lb{x_i} et la meilleure (plus petite) borne sur x_i trouvée lors des appels au simplexe sur les dimensions précédentes ?

[bneveu]

C'est déjà le cas. le test est absolu en dessous de 1 et relatif au dessus.

[trombettoni]

Et du coup, Bertrand, pour en avoir le coeur net, si tu (ré)enlevais l'heuristique de Achterberg, en augmentant le timeout d'un facteur 10... ? Juste pour tester les problèmes pathologiques avec CLP...

Si ça fonctionnait, on tiendrait la piste et il sera alors temps de trouver une solution intelligente...

[gchabert]

Merci pour l'explication sur l'heuristique d'Achterberg. Elle est tout à fait logique.
On pourra retravailler les paramètres en effet; mais cela n'explique donc pas les écarts actuels CLP/Soplex.

En continuant à creuser, l'étau se resserre sur le postprocessing de Neumaier-Shcherbina, que j'ai commencé à regarder de près. Et, soit c'est moi qui ai compris tout de travers, soit il y a un gros souci!

Je m'explique. Cet algo repose sur le calcul du résidu du problème dual, qui doit être en théorie un petit intervalle, proche de 0 (en gros, de la taille de la tolérance du solveur PL). Or ce n'est pas du tout le cas! Je vous ai mis plus bas à titre d'exemple la trace intégrale de ces résidus sur un problème très simple.

Cela vient des multiplicateurs eux-mêmes, dont les valeurs sont visiblement souvent aberrantes. J'observe par exemple une situation qui se produit très souvent: tous les multiplicateurs sont à 0 (alors qu'à ma connaissance cela n'a aucun sens en PL, à moins d'avoir un critère nul, ce qui n'est pas notre cas). Et, plus étonnant, j'observe ça aussi bien avec Soplex qu'avec CLP. Et du coup, avec un coût de type -x_i, cela donne automatiquement un résidu de 1 (qu'on voit bien apparaître souvent dans la trace ci-dessous).

C'est assez "grave" car ce résidu se répercute directement sur la qualité de la borne obtenue. Et donc ce comportement pourrait tout à fait expliquer des différences de filtrage. La bonne nouvelle est que la théorie reste correcte et que la borne calculée est safe (on s'en serait aperçu sinon bien sûr...).

Donc ma question est la suivante: ceux qui ont implanté ce post-processing (Bertrand?) avaient-ils observé ces comportements et ont-il une explication à cela?

Et voici la trace. Il s'agit tout simplement de la norme infinie de la variable rest dans neumaier_shcherbina_postprocessing:

rest=0
rest=1
rest=0
rest=1
rest=0.441250102238
rest=1
rest=1
rest=1
rest=1
rest=1
rest=60.845633395
rest=143.906438362
rest=0
rest=0.666525856531
rest=0
rest=0.182992226499
rest=0.361374178914
rest=0.164107112473
rest=1
rest=1
rest=0.579946457544
rest=1
rest=55.9665505459
rest=1
rest=0
rest=1
rest=0
rest=0.311396553941
rest=0.417770864137
rest=0.180435778293
rest=1
rest=1
rest=0.525749017534
rest=1.26829861109
rest=1
rest=1
rest=0
rest=8.88178419701e-16
rest=0
rest=0.422684531212
rest=0.431889382926
rest=0.254014823413
rest=1.20194836255
rest=1
rest=1.18880745418
rest=1
rest=50.9476499382
rest=1
rest=0
rest=1
rest=0
rest=0.532173159394
rest=0.507456364581
rest=0.300294499546
rest=1.19829712172
rest=1
rest=1.54442498676
rest=1
rest=62.4484007153
rest=1
rest=0
rest=1.77635683941e-15
rest=0
rest=0.47043314597
rest=0.565106696284
rest=0.296306137054
rest=3.59895727155
rest=1
rest=1.45135137628
rest=1.50187052531
rest=95.7824522868
rest=1
rest=0
rest=2.66453525911e-15
rest=0
rest=0.576335164567
rest=0.537223556
rest=0.32177008096
rest=3.15767477113
rest=1
rest=1.69342908179
rest=1.51415611757
rest=84.0956483633
rest=1
rest=0
rest=4.44089209851e-16
rest=0
rest=0.578357041048
rest=0.538049912549
rest=0.322585760759
rest=3.15849537455
rest=1
rest=1.69883296049
rest=1.51513611064
rest=84.2735678935
rest=1

[Jordan08]

Salut,
lors des premières versions, on avait bien testé ça.
Dans mes souvenirs, ce genre de problème venait de la solution dual qui n'était pas calculer par le solveur.
Ou que l'on modifiait des bornes ou la matrice du LP sans mettre à jour ce que l'on stockait en local.
En gros, la solution dual doit être celle du problème original et pas celle du problème reformulé par le solver LP, de même pour le calcul du résidu et de l'extraction de la matrice.
A une époque, on stockait ça en local et on la modifiait à chaque modif du LP pour éviter toute embrouille...
Toutes les solutions dual et primal ainsi que la forme de la matrice sont bonnes quand tu as ces écarts?

Pour la formule, j'ai retrouvé mon code de thèse en Fortran! La formule me parrait bonne
`

subroutine CalculBoundSURE(A,b,c,N,M, lambda, epsilon, bound)

	double precision, dimension(:), intent(in) :: A
	double precision, dimension(:), intent(in) :: b
	double precision, dimension(:), intent(in) :: c
	integer, intent(in) :: N , M  ! N : nombre de variables , M: nombre de contraintes >0
	double precision, dimension(:), intent(in) :: lambda
	interval, intent(in) :: epsilon
	interval(8), intent(out) :: bound
	
	interval(8), dimension(M) :: y, b_inf
	interval(8), dimension(N) :: l, u, x, residu
	integer :: i
	
	y = lambda(1:M)
	l = lambda(M+1:M+N)
	u = lambda(M+N+1:M+2*N)
	
	x = epsilon
	
	do i = 1,M
		b_inf(i) = INTERVAL(-b(i),1.D300)
	end do
	
	do i = 1,N
		residu(i) = DOT_PRODUCT(A(i:(M-1)*N+i:N), y) 
	end do
	residu = residu -l +u +c

	
	bound = DOT_PRODUCT(y,b_inf) +DOT_PRODUCT(l,x) -DOT_PRODUCT(u,x) +DOT_PRODUCT(residu,x) 

	
end subroutine CalculBoundSURE`

[gchabert]

Le postprocessing est codé dans la super classe LPSolver qui n'a pas accès aux variables bas niveau des différents solveurs ... je ne pense pas qu'il y ait de souci de cet ordre mais je n'ai peut-être pas tout compris

[bneveu]

J'ai essayé d'enlever le test de Neumaier Shcherbina. Cela ne change pas grand chose pour les problèmes non résolus avec CLP.
Le problème ne vient pas de là non plus.

[gchabert]

Petit scoop!
J'ai eu une petite révélation: j'ai forcé l'arrondi du processeur au plus proche avant les appels aux solveurs LP... et là, ô surprise, ça change tout. Désormais, les différences entre CLP /Soplex ne sont jamais au dessus de 1e-12 (et bizarrement ce n'est que sur les bornes inférieures).
Mais on n'a pas encore résolu totalement notre problème car ça ne fait "que" diviser par 2 le nombre de boîtes avec CLP pour le moment.
Je continue à creuser...

[gchabert]

Un détail, Gilles. Tu as vérifié seulement le PolytopeHull, pas l'upperbounding, sur srcpm ? Ou bien tu as mis le loup initial au coût optimal, histoire de focaliser l'analyse sur le lowerbounding ?

J'applique uniquement PolytopeHull dans la moulinette. Par contre, effectivement, quand je dis que le nombre de boîtes est divisé par 2, c'est sur une résolution de srcpm avec CLP (donc en incluant la recherche de loup) en forçant l'arrondi processeur avant appel au solveur LP

[trombettoni]

Ce que je voulais dire, c'est tu n'as peut-être aucune différence sur les appels CLP/Soplex dans le PolytopeHull (lowerbouding), mais peut-être qu'il y a une différence sur les appels dans In-X-Taylor (upperbounding) et que c'est ça qui pourrait poser souci. En mettant --initial-loup à la meilleure valeur, tu enlèves ce doute (maintenant, il n'y a peut-être pas de doute sur ce bench si on voit que c'est le uplo qui ne remonte pas avec CLP...)

[trombettoni]

Et c'est quoi le ou les paras de tolérance que tu as spécifiés ? Il y a visiblement primal_tolerance, dual_tolerance, mais j'ai trouvé sur une doc de CLP près de 28 paras de type double ! De quoi s'y perdre en effet...

[gchabert]

Je n'ai vu que ces deux types de tolérance dans la doc de CLP (pour le primal et le dual)

[gchabert]

Bon, les écarts de 1e-5 était une erreur d'interprétation. J'appliquais CtcPolytopeHul dans une moulinette et comparais les bornes obtenues entre CLP et Soplex; sauf que j'avais oublié un détail: la linéarisation au début du contracteur faisait intervenir de l'aléatoire (heuristique des coins opposés aléatoires). En changeant par l'heuristique "borne inf" et en faisant une comparaison vraiment systématique sur des centaines de boîtes, l'écart max se situe finalement autour de 2*1e-8 sur srcpm, ce qui est un peu beaucoup par rapport à la tolérance de 1e-9 mais pas si déconnant. Et en diminuant la tolérance, on diminue bien cet écart.

Par contre, CLP est effectivement beaucoup plus sensible que Soplex au mode d'arrondi. Soplex doit avoir un algorithme qui travaille au moins partiellement avec des valeurs exactes (ce qui me fait penser ça est cette publi des auteurs de Soplex https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/5511).

Sur un problème assez facile comme srcpm, j'arrive donc à aligner le nombre de boîtes entre Soplex et CLP, en enlevant Achterberg, le post-processing de Scherbina, l'aléatoire dans LinearizerXTaylor, en utilisant le primal pour CLP et en bidouillant l'arrondi processeur (on peut constater au passage que CLP est plus lent). Ca veut dire que je n'ai pas extrait de preuve du supposé dysfonctionnement de CLP.

La bidouille corrige le tir aussi pour immun mais, sans surprise, ne règle pas les timeout avec CLP sur les problèmes difficiles (sambal, chem, etc.). Peut-être que sur ces problèmes l'écart entre les bornes calculées par CLP et Soplex est plus grand. Mon premier réflexe a été alors de diminuer la tolérance. Ca a un effet mais pas de miracle à la clef, comme déjà dit par Bertrand. Il faudrait donc analyser davantage mais bon... je doute maintenant qu'on puisse, par des réglages de notre côté, rendre CLP compétitif. Mais sans aucune preuve hélas.

Bertrand, j'ai commité (au moins temporairement) ma bidouille pour CLP sur develop, je veux bien que tu me dises ce que ça donne pour toi.

Je vais arrêter là ce travail d'investigation. Je résume ci-dessous les problèmes que j'estime très gênants et qui sont en suspens, pour une âme charitable qui aurait un un jour le courage de le poursuivre (ah, que je suis naïf) :

• ibex+CLP est moins bon que ibex+soplex et au final on ne sait toujours pas exactement pourquoi. Je ne parle pas du temps de calcul mais du nombre de boîtes, qui parfois explose avec CLP
• il y a une non-reproductibilité avec CLP et parfois des crash (ex8_4_6)
• ibexopt fait une sur-restriction pour construire le simplexe intérieur, ce que l'on paie forcément
• on ne sait pas bien corriger un loup-point qui sort de ce simplexe
• il y a des paramètres fixés en dur (tolérance LP, sur-restriction XTaylor, eps-Achterberg) dont on ignore les effets
• le postprocessing de Neumaier-Scherbina ne fait pas les calculs qu'on imagine (ou alors, c'est moi qui n'ai rien compris)

[rilianx]

Salut Gilles, Je comprend pas pourquoi on peut pas corriger le loup-point quand il sort de simplexe.
La technique utilisé dans le mode "rigoureux" marche pas? Pourquoi exactement?

[gchabert]

Salut Ignacio, oui c'est une bonne remarque en fait. Ça se tente...
Bon, d'expérience, la partie "sélection des contraintes" est délicate lorsque le loup-point sort du simplexe; or, le loup-finder du mode rigoureux grosso modo cherche le sous-système de contraintes actives (ou presque) le mieux conditionné et teste seulement après coup les autres inégalités. Il va donc notamment souvent échouer en présence des égalités g(x)=eps et g(x)=-eps (il n'est pas prévu pour être utilisé dans ce cas).
Il faudrait donc repartir de l'algo que j'ai développé dans la branche restrict-postproc, pour conserver la partie "sélection des contraintes" (c.a.d. les lignes 42 à 142 de https://github.com/ibex-team/ibex-lib/blob/restrict-postproc/src/loup/ibex_LoupFinderXTaylor.cpp).
Il suffit ensuite de changer la fin du code. Actuellement, je recherche un point admissible suivant la direction d obtenue en résolvant approximativement un système A x= b-(1,....,1). Il faudrait le remplacer par un Gauss-Seidel intervalle sur le système A x = b jusqu'à contraction stricte de la boîte [x] (=> preuve de solution).
Repartir du système non-linéaire pour le re-linéariser via un Newton me semble inutile.
Si j'ai bien compris ton idée.

[bneveu]

La dernière modif marche chez moi nettement moins bien que la version précédente on arrive effectivement à résoudre srcpm en 15s, mais on n'arrive plus à résoudre avec la précision 1.e-6 en 1000s ex3_1_1, ex2_1_9, ex6_1_1, ex7_2_3, ex7_2_4, ex7_2_8 ex7_2_9
ex8_4_4 ex8_4_5 tous résolus en moins de 100s avant la modif.
les autres problèmes non résolus le restent.

[gchabert]

Merci d'avoir regardé... Je m'y attendais. J'ai rétabli la version d'avant.