ibex-team / ibex-lib Goto Github PK

View Code? Open in Web Editor NEW

67.0 23.0 50.0 81.66 MB

IBEX is a C++ library for constraint processing over real numbers.

Home Page: http://ibex-team.github.io/ibex-lib/

License: GNU Lesser General Public License v3.0

Python 3.48% C++ 82.94% C 0.03% Lex 0.23% Gnuplot 0.03% CMake 2.49% JetBrains MPS 10.79%

ibex-lib's Introduction

ibex-lib

IBEX is a C++ library for constraint processing over real numbers.

It provides reliable algorithms for handling non-linear constraints. In particular, roundoff errors are also taken into account. It is based on interval arithmetic.

The main feature of Ibex is its ability to build strategies declaratively through the contractor programming paradigm. It can also be used as a black-box solver.

Two emblematic problems that can be addressed are:

System solving. A guaranteed enclosure for each solution of a system of (nonlinear) equations is calculated.
Global optimization. A global minimizer of some function under non-linear constraints is calculated with guaranteed bounds on the objective minimum.

Documentation

The documentation is available here

Credits

The Ibex project started in 2007. It grew up after various prototypes developed by Gilles Chabert during its thesis and was mainly developed by him during his tenure at IMT Atlantique in LS2N (UMR 6004) between 2008 and 2018. It is in standy-by since 2020.

Some people brought great help, in particular Luc Jaulin (UMR 6285, ENSTA Bretagne), Gilles Trombettoni (UMR 5506, Univ. Montpellier) and Alexandre Goldsztejn (UMR 6004, CNRS) for the underlying concepts and algorithms, Bertrand Neveu (UMR 8049, ENPC, Paris) for the development of global optimization routines and benchmarking, Cyril Bouvier (UMR 5506, Univ. Montpellier) for the Python installation scripts.

Some people also contributed by developing plugins, such as Jordan Ninin at UMR 6285 (affine arithmetic), Antoine Marendet at UMR 6004 (semi-infinite programming), Benjamin Martin at UMR 6004 (parametric continuation)... Plugins come as separate Github projects, see ibex-team for a more comprehensive list.

ibex-lib's People

Contributors

Stargazers

Watchers

Forkers

jordan08 nicolaje jinxiaosa benensta sansolivier rilianx msis dreal-deps yehudi domensta zenna clementaubry dpsanders dvinc cyrilbouvier schvarcz chrishartmann68 sylvainpion infpucv damirexzael vareyesr ddinria amarendet martinjos yawnyoung benjam-art-in zeta1999 adarshp juliendamers simonrohou lebarsfa liq07lzucn raphaelchenouard trombettoni mlech26l ali-robot sbednarz vishalbelsare tilletj alexandreexpert jgladwig rolitoxdd mo271 mohannad-aldughaim

ibex-lib's Issues

Clarify semantics of assignment operators (=, +=, etc.) in Vector versus Matrix

With vectors, dimensions of both argument must agree, but with matrices, not necessarily (this is due, e.g., to the operator *=).
This is ambiguous.

Do we have to use -ffloat-store in the makfiles with Profil/Bias?

Some tests do not pass without this option.

Bug reformulation affine

voici le code responsable du bug

include "ibex.h"

include

using namespace std; using namespace ibex;

int main(int argc, char** argv) {
SystemFactory f;
Variable x,extra;
f.add_var(x); f.add_var(extra); f.add_ctr(x<=0);
System sys(f);
// if I replace the domain of "extra" by [1,1.1]
// there is no more problem.
double _box[][2] = {{-100,100},{1,1}};
IntervalVector box(2,_box);
LinearRelaxCombo linear_relax(sys,LinearRelaxCombo::AFFINE2);
CtcPolytopeHull polytope(linear_relax,CtcPolytopeHull::ALL_BOX);
polytope.contract(box);
}

Thread safetiness of ibex objects

In many situations the performances of a solver could be vastly improved by parallelizing the application of some contractors.
For this purpose, it would be really great to ensure that the related objects (NumConstraints, Functions...) are thread safe.
See http://www.ibex-lib.org/node/19

Clean the waf script and upgrate to Python 3

I think that there is to many bug in this script.
I ask a collegue to help me. He is expert in Python.
But first we must make the interface with C-XSC and update the interface with soplex 2.0
After that, it will be easier to get a stable installation process.

Cleanup the interface and make documentation for LinearRelax and CtcPolytopeHull

bug ex8_5_6

L'optimiseur perd "parfois" la solution de ex8_5_6 (problème assez tordu où l'objectif au départ n'est pas borné (contenant des log de différences pouvant valoir 0))

en particulier l'appel suivant donne un minimum trop élevé (ibex compilé avec gaol sur machine linux 64 bits)
../build/examples/optimizer04 ../benchs/benchs-optim/coconutbenchmark-library1/ex8_5_6.bch 3bcidhc4 compo smearsumrel 1.e-8 1.e-8 1000 1
best bound in: [0.0317535151967,0.0317535251967]
Relative precision obtained on objective function: 3.14925662617e-07 [failed] 1e-08
Absolute precision obtained on objective function: 9.99999899474e-09 [passed] 1e-08
best feasible point (0.166625446472 ; 0.450000001 ; 0.383374542628 ; 0.628052017898 ; 0.475474436029 ; 0.106958155794)
cpu time used 1.440089s.
number of cells 533

si on change un paramètre, c'est bon (acidhc4 au lieu de 3bcidhc4 ou art au lieu de compo)

./build/examples/optimizer04 ../benchs/benchs-optim/coconutbenchmark-library1/ex8_5_6.bch acidhc4 compo smearsumrel 1.e-8 1.e-8 1000 1
best bound in: [-0.00116749324774,-0.00116748324774]
Relative precision obtained on objective function: 8.56543339542e-06 [failed] 1e-08
Absolute precision obtained on objective function: 9.99999899994e-09 [passed] 1e-08
best feasible point (0.0968028522508 ; 0.245116476628 ; 0.658080681022 ; 0.305515608082 ; 0.670455906336 ; 0.120323419407)
cpu time used 6.916433s.
number of cells 2306

../build/examples/optimizer04 ../benchs/benchs-optim/coconutbenchmark-library1/ex8_5_6.bch 3bcidhc4 art smearsumrel 1.e-8 1.e-8 1000 1

best bound in: [-0.00116749259514,-0.00116748259514]
Relative precision obtained on objective function: 8.56543818335e-06 [failed] 1e-08
Absolute precision obtained on objective function: 9.99999899994e-09 [passed] 1e-08
best feasible point (0.0968128082773 ; 0.245120249516 ; 0.658066952107 ; 0.305527898153 ; 0.670443037492 ; 0.12032269187)
cpu time used 4.904307s.
number of cells 3113

Bug on Mac OS Mavericks

I found a bug in src/combinatorial/ibex_Qinter*

It is just a non-C++09 initialization of a vector.

I will correct it

Timer should be thread-safe

A message by Usman Rauf:
"I guess you are right about the timing class, it seems that it does't support several threads, the evidence for this is that, even if I assign differetn threads to different cores (I am using system with 32 cores) and set time_limit to 10 sec it still takes 1:20 secounds to terminate for four solvers. Which is a clear evidence (given the fact that I have tested it multiple times) that multiple instances cannot be executed in parallel. Is it possible to modify that timer class?"

Optimizer: Uplo never calculated if the problem is too easy

Running for instance ./defaultoptimizer ../benchs/ex3_1_3bis.bch 0.01 0.01 100
with filib gives an interval like [-oo,-309...]
because the uplo is never set (the optimizer does not get into the "while" loop and reports 0 cells)

Memory leak CtcAcid

The following array:
double* ctstat= new double[nbvarmax]
is never disallocated.

Seg fault with composition with same "Variable"

Simple ex:

    Variable x,y;
    Function f(x,y,x);
    Function g(x,y,f(x,y));

Optimizer fails with unbounded boxes

This is, in particular, due to monotonicity_analysis that fix variables to some bounds. This leads to intervals like [+oo,+oo] considered as empty.

Tree-structured DAG and Fixpoint flag

For optimization purpose: maybe, it could be useful to add a "is_tree()" function in ExprNode and then activate some "FIXPOINT" flag in CtcFwdBwd.

Augmented Lagrangian

Optimizer: returns INFEASIBLE instead of NO_FEASIBLE_FOUND with obj_init_bound<+oo

L'optimiseur retourne INFEASIBLE lorsque le upperbounding (goal_prec>0) supprime toute solution (chose qui est possible avec un loup initial "utilisateur" < +oo).

Voir le problème TestOptimizer::issue50.

DefaultOptimizer fails with filib.

Running the default optimizer with the following problem works fine with gaol, but fails with filib (gives an interval like [inf,0] for [uplo,loup]. When I comment the last contractor (the one using LinearRelaxXTaylor) and CtcAcid, it is the same.

Gilles
variables
x in [-100,100],
y in [-100,100],

mx in [-100,100],
my in [-100,100];

minimize
mx^2+my^2

constraints
x^2+(2*y)^2=1;
(x-mx)^2+(y-my)^2=1;
end

Sparse Matrices structure in CtcPolytopeHull

To improve the generation of the linear relaxations in CtcPolytopeHull, we must have sparse matrices.
When the size is > 100, the Matrix 100x100 is too big

CtcFwdBwd and empty evaluation

In case of empty interval arithmetic evaluation due to sqrt of a negative interval,
CtcFwdBwd does not detect this impossible case and does not raise an
EmptyBoxException.

Memory leak CtcInverse

In the constructor, the following variable const ExprSymbol& y=ExprSymbol::new_(f.expr().dim) does not seem to be disallocated.

With this simple example :
int main(int argc, char *argv[]){
Variable x,y;
Function f(x,y,x+y);
CtcFwdBwd c(f);
CtcInverse cInv(c,f);
return 0;
}

I got :
==16199== 5 bytes in 1 blocks are definitely lost in loss record 1 of 2
==16199== at 0x402CE68: malloc (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==16199== by 0x4203C30: strdup (strdup.c:43)
==16199== by 0x80C5227: ibex::CtcInverse::CtcInverse(ibex::Ctc&, ibex::Function&) (ibex_CtcInverse.cpp:15)
==16199== by 0x80C1C55: main (main.cpp:21)

Creating NumConstraint directly with string (like currently Function)

Example of what one should be able to do:

NumConstraint dist_ctr("xa","ya","xb","yb","r","pow(xa-xb,2)+pow(ya-yb,2))=r^2")

Add serialization/de-serialization of subpavings

In some cases it is convenient to load/write a subpaving from/to a file.

Optimizer: no way to check for infeasibility!

When the optimizer returns, how the user can be informed that infeasibility occurred (no feasible point at all)?

Remove vibex API

I would prefer to remove vibes.h and vibes.cpp from IBEX repository.
It makes more sense for me if people install vibes and connect both project (vibes & ibex) inside their own code. One typical problem is when someone has installed a release of vibes that is not compatible with the API provided in his relase of IBEX: his program crashes.

Optimizer: Replace the code of optim_simplex by a call to XNewton

The code seems very redundant!

Should we restore Ctc(n) ?

To keep combatibility with the previous version, I'm asking myself if we should come back to the previous architecture?
I think that complicate the interface of some Ctc, such as Ctc3BCid. Before this contractor doesn't need the size of the box.

Pearhaps can we have the both structure?
Is there a contractor which doesn't need the size of the box?

CLP installed by default instead of Soplex if --with-soplex is missing

It was supposed that the installation looks for soplex in the parent directory if --with-soplex was not specified. But the script now installs CLP instead, and it seems that CLP installation fails on some platforms (MacOS).

Integrating C-XSC

Now, in IBEX, we can use 3 differents implementation of the interval arithmetic:

Profil/Bias
Goal
Filib++
But none of them are still in development. And since the last version of OSX, a lot of warning start to rise.
So I think that integrate a new implementation can be a good idea.

I found the library C-XSC : http://www2.math.uni-wuppertal.de/~xsc/xsc/cxsc.html

This librairy is still in development (last release in 02/2014)
It is compatible with Linux/Mac/Win.
The installation is very easy and detail
You can install it in a software emulations mode for directed rounded floating-point operations. This mode is independant from tha rchitecture of your processor

Defaultsolver: add vector of precisions

Windows: waf install gets frozen

Observed while compiling FILIB.

Clean CellOptimHeap and OptimCell

Due to the management of two heaps
Many think has been introduce.
I will clean it

Merge Dim::vec_size et Dim::max_index

Seems redundant.

CtcForAll: update the code (like it has been done with CtcExist)

Memory fault LinearRelaxXTaylor

When cleaning up data in the defaultoptimizer, I get a following memory fault.
To reproduce the problem, uncomment the following line in ibex_DefaultStrategy.cpp_:
//if (relax) delete relax;
and run "valgrind ./defaultoptimizer etc."

The result is:
Invalid read of size 4
ibex::LinearRelaxXTaylor::~LinearRelaxXTaylor() (ibex_LinearRelaxXTaylor.cpp:67)
ibex::LinearRelaxXTaylor::~LinearRelaxXTaylor() (ibex_LinearRelaxXTaylor.cpp:70)
ibex::LinearRelaxCombo::~LinearRelaxCombo() (ibex_LinearRelaxCombo.cpp:72)
ibex::LinearRelaxCombo::~LinearRelaxCombo() (ibex_LinearRelaxCombo.cpp:73)
ibex::(anonymous namespace)::Memory::~Memory() (ibex_DefaultStrategy.cpp_:53)
ibex::DefaultOptimizer::~DefaultOptimizer() (ibex_DefaultOptimizer.cpp:95)
main (defaultoptimizer.cpp:58)

Evaluation of a Function with an AffineForm only

We should add these functions :
Affine2 eval_affine2(const Affine2Vector& box) const;
Affine2Vector eval_affine2_vector(const Affine2Vector& box) const;
Affine2Matrix eval_affine2_matrix(const Affine2Vector& box) const;

Memory cleanup in DefaultSolver/Optimizer

There are some memory leaks.

is_strict_subset has changed

According to one student, there is a bug in this function for an IntervalVector.
But I don't find it.

Windows: sys.times.h not found

Waf install fails with this message:
<sys.times.h> : no such file or directory

Comment by M. Kieffer (Frenche):
times.h ne fait pas partie de la distribution de MinGW sous windows. J'ai l'impression que cette fonction est nécessaire dans un bout du code que vous n'avez pas développé pour initialiser un générateur pseudo-aléatoire. Cela ne me semble pas complètement indispensable d'utiliser une teille artillerie. Les fonctions de time.h devraient suffire.

LinearRelaxCombo::COMPO fails

The default solver, in particular, fails with this option.

You can try for instance with this example:

Variables
x in [-10,10],y in [-10,10];

Constraints
y=-0.1;
1.5_x^2+1.5_y^2-x*y=0.2;
end

It should give
sol 1 nb_cells 2 ([0.3194335081419453, 0.3194335081419455] ; <-0.1000000000000001, -0.1>)
sol 2 nb_cells 2 ([-0.3861001748086122, -0.386100174808612] ; <-0.1000000000000001, -0.1>)
number of solutions=2

But it doesn't.
NOTE: While it is not fixed, I have replace this option with LinearRelaxCombo::XNEWTON in the default solver.

Gilles

Function: Use BitSet for used_vars

Many linking warnings appearing on a MacOS 64bits platform

/opt/local/bin/ranlib: file: src/libibex.a(ibex_Tube.cpp.3.o) has no symbols

/opt/local/bin/ranlib: file: src/libibex.a(ibex_AmplInterface.cpp.3.o) has no symbols

/opt/local/bin/ranlib: file: src/libibex.a(ibex_Backtrackable.cpp.3.o) has no symbols

/opt/local/bin/ranlib: file: src/libibex.a(ibex_SubPaving.cpp.3.o) has no symbols

[182/200] cxxprogram: build/examples/optimizer04.cpp.12.o -> build/examples/optimizer04

[183/200] cxxprogram: build/examples/doc-tutorial.cpp.8.o -> build/examples/doc-tutorial

[184/200] cxxprogram: build/examples/solver02.cpp.19.o -> build/examples/solver02

[184/200] cxxprogram: build/examples/doc-arithmetic.cpp.3.o -> build/examples/doc-arithmetic