Unexpected behavior with simple arithmetical constraint (+Java)

[cprudhom]

Dear developers,

I encounter a strange result while calling ibex.contract(...) on the following example (in Java):

Ibex ibex = new Ibex(new double[]{1.e-1});                    
ibex.add_ctr("{0}>=1.");                                      
ibex.build();                              
double[] domains = new double[]{0.15, 85.0};                  
ibex.contract(0, domains);
out.printf("%s\n", Arrays.toString(domains));                 

This prints [1.0, 85.0] when domains = new double[]{0.15, 85.0};
But, when upper bound is greater or equal to 86.0 it prints [0.15, 86.0] (f-ex, domains = new double[]{0.15, 86.0};).

Any ideas how to fix this ?

Best,
CP

[gchabert]

Strange, indeed.Thanks for reporting. It will be fixed by tomorrow.

[gchabert]

Ok, I see.
When the upper bound is >=86, the contraction is less than 1% of the domain so it is ignored, and the return code is NOTHING.
Removing this threshold and returning CONTRACT is not a good option. You would fall into long contraction loops with very tiny reductions.
Returning NOTHING and keeping the domain contracted is worse as this would be an inconsistent behavior (error-prone on Choco side).
Maybe should I return NOT_SIGNIFICANT in the case of contraction < 1% (like for the inflation). And maybe this threshold could be setable from Java?
What do you think ?

[schmittjoaopedro]

Hello,

I'm interested in this issue because I've found the error on choco-solver. Could you explain how ibex developers work around this problem, I mean, no one deal with such interval reductions that not achieve 1% of significance? This is a common issue, if not, why not?

Thanks in advance,

[gchabert]

Hello,
This is not an issue because the branching process (would it be that of choco or ibex) ensures that the widths of intervals go to zero. And this is why, so far, we did not need to make a distinction between "no contraction at all" and "not a signification contraction".
However, the threshold of 1% is a bit coarse. In the ibex solver, we rather use a combination of absolute and relative threshold and people typically set both to 1e-3.

[cprudhom]

Hi,

I suppose that NOT_SIGNIFICANT will be a good answer, and that Choco can manage it.
Let me know when Ibex handles that.

Best

[schmittjoaopedro]

We are starting a important project using the choco-solver in the company. Would be nice if such feature could be released until the end next month.
For while, there is another way to define the relative threshold to 1e-3 that doesn't depends of choco?

Thanks,

[gchabert]

Sure, I can make the update quickly; it's a minor thing. I let you know.
PS: @schmittjoaopedro , would you mind signing the guest book of Ibex?

[gchabert]

Thinking again about this topic, I am not sure that we really need two different status for contraction: NOTHING and NOT_SIGNIFICANT. Would you distinguish both? If, say, a contraction only removes a single float in a domain, what difference would that make comparing to nothing removed at all?
My suggestion is to leave the return status as today and just to give the posiblity to set the threshold from java. Agreed?

[cprudhom]

Indeed, NOT_SIGNIFICANT is currently not used. NOTHING triggers no specific action, as expected. So I suppose the best option is to set the threshold programmatically.

[gchabert]

Ok, it's done in the 'develop' branch and it will be integrated in the next release. You can test meanwhile with 'develop'.
Now 'contract' requires an additional argument: the threshold as a relative ratio (see comments in ibex.java).

[cprudhom]

Is this published in 2.8.7 or still under development ?

[gchabert]

It is still under "develop" and ready for the next release.

[cprudhom]

Ok, well I encounter another issue, related to this, I bet.
I would like to talk to you about the situation.

I have the following model:

Ibex ibex = new Ibex(new double[]{0.001});
        ibex.add_ctr("{0}=2.");
        ibex.add_ctr("{0}=2.");
        ibex.build();
        double[] domains = new double[]{1.0, 3.0};
        Assert.assertEquals(Ibex.CONTRACT, ibex.contract(0, domains));
        Assert.assertEquals(Ibex.ENTAILED, ibex.contract(1, domains, Ibex.FALSE_OR_TRUE));

The first assert is satisfied, but not the second.
Could you enlighten me ?

[gchabert]

This is not related to this issue. The "problem" is that ibex only proves entailment for inequality constraints. This is because, in the realm of continuous constraints, entailment does not make much sense for equations ... except on very special situations like the one you're testing, i.e., equations x=some_constant or x*y=0, etc.

Note that with equations, however, we can prove the existence of a solution and this is what the return code SOLUTION of next_solution stands for.

It's possible to make a hack in the java plugin for some constraints like x=some_constant, but I'm not enthusiast. This kind of constraint could be directly handled by Choco. Tell me what you think.

[schmittjoaopedro]

I would like to give an opinion about this situation.

@cprudhom I've made a question on gitter some time ago asking the possibility about a more performant way to define equality constraints over real numbers. The related problem to this question was:

In the following code, increasing the numVars from 10 to 1000 linearly (in increments of 10) causes the propagation time increasing exponentially. Differently from IntVar that executes [very] more efficiently.

Model model = new Model();
RealVar[] vars = model.realVarArray(numVars, lb, ub, precision);
 for (int i = 0; i < numVars; i++) {
         vars[i].eq(100.0).ibex(precision).post();
}
model.getSolver().propagate();

In a problem with thousands of RealVars, where many of then will be constrained with equality, how it can be made more efficiently? What about the possibility of create a Java propagator to define direct constraints as =, !=, >, <, >= and <=?

[schmittjoaopedro]

I would like to give an opinion about this situation.

@cprudhom I've made a question on gitter some time ago asking the possibility about a more performant way to define equality constraints over real numbers. The related problem to this question was:

In the following code, increasing the numVars from 10 to 1000 linearly (in increments of 10) causes the propagation time increasing exponentially. Differently from IntVar that executes [very] more efficiently.

Model model = new Model();
RealVar[] vars = model.realVarArray(numVars, lb, ub, precision);
 for (int i = 0; i < numVars; i++) {
         vars[i].eq(100.0).ibex(precision).post();
}
model.getSolver().propagate();

In a problem with thousands of RealVars, where many of then will be constrained with equality, how it can be made more efficiently? What about the possibility of create a Java propagator to define direct constraints as =, !=, >, <, >= and <=?

I've made some tests with a custom propagator, if it's interest you, I could share my implementation. Then choco-team can analyse this possibility.

[cprudhom]

@schmittjoaopedro

I profiled the execution, and most of the time is spent in Ibex.build():

double lb = 1.0;
double ub = 200.;
double precision = 0.001;
Model model = new Model();
RealVar[] vars = model.realVarArray(numVars, lb, ub, precision);
for (int i = 0; i < numVars; i++) {
    vars[i].eq(100.0).ibex(precision).post();
}
model.getSolver().propagate();

numVars = 50
execution time: 0.782s, 
Ibex build: 0,510s

numVars = 100
execution time: 2.745s, 
Ibex build: 2,438s

numVars = 200
execution time: 18.88s, 
Ibex build: 17,78s

@gchabert any ideas where this comes from ?
(BTW, should we open a new issue ?)

[gchabert]

I am not surprised that building a constraint is slow. The building process first goes through JNI, the syntax is then parsed and a bunch of objects are built on C++ side. This may takes time and this part of Ibex has not been optimized at all, simply because models are usually fairly small to be exhaustively solvable.
This might be another argument to let Choco deal with basic constraint like assignments.