Infeasible LinearInt constraints on singleton variables are not imposed

[thomasleaute]

Hi,

If you create a new LinearInt constraint by passing it a list of singleton variables that do not add up to the right-hand-side constant, then the constraint is incorrectly not imposed, and the store incorrectly claims to be consistent.

The issue is in commonInitialization(), which collapses all singleton variables into the right-hand-side constant b, which can result in the list of variables x becoming empty, and then impose() returns without imposing the constraint, even though it is violated because b != 0.

Best,

Thomas

[radsz]

Thanks for reporting this issue. The fix is in our private develop branch. Now I need to discuss it within our code dev team how to publish on github.

[radsz]

I pushed a newer version of develop branch that should have a working fix for your problem. Please verify and if it is not fixed for you please reopen this issue.

[thomasleaute]

Hi,

Thanks for providing this fix.

I've tested it, and while I can confirm that the patch in LinearInt.impose() now correctly catches the infeasibility, it does so by throwing a Store.failException. Now, it is quite possible that I am not up to date with the JaCoP philosophy, but I would not normally expect impose() to check consistency. I also find this surprising since impose() returns void and its signature does not suggest that it could throw failExceptions.

Does this mean that I should from now on expect impose() to check consistency and that I need to add try/catch clauses to my code to catch potential failExceptions?

Thanks in advance for your insights,

Thomas

[radsz]

Hi Thomas,

Thanks for your feedback.

Before I start discussion with Kris concerning the current approach I would like to have your feedback.

Throwing an exception from impose function has a benefit as the user is immediately notified that his problem is not solvable and there is no point in imposing other constraints as it will not change the situation. Thus, you have a potential benefit in performance as no work is required to create and impose other constraints. You were concerned about performance in those initial steps like setting up the problem. The current solution does provide you thus possibility for extra performance at the expense of exposing your code to an exception (Store.failException).

I myself have preference to throw an exception than making impose return a flag that indicates if the problem is consistent or not. We introduced this failException as too often we and our users were ignoring inconsistency and tried to do something without removing a level before continuing. Thus, myself I am against changing an exception to returning a value. However, if you prefer this solution I can still discuss it with Kris. If he likes this solution more than existing one we could still change it.

Another option that is acceptable for me is do not throw an exception and allow the user to keep adding constraints/variables and then fail immediately when he tries to run the search. The problem with approach are as follows. It will take more time so performance will be reduced. Moreover, the user lost an opportunity to know a smaller core of the problem that was already unsatisfiable. He will still know the last failed (if we make sure that this attribute of store is set if inconsistency found during impose).

I have a bit of an allergy to checked exceptions as they force the user to explicitly catch exceptions even if normally things like problem inconsistency not happens at this stage. However, in your case you still are forced to use try and catch and have no information that impose can throw failException. Thus, you were a bit suprised. However, in your case, since it is common in your way of using JaCoP then you noticed this unchecked exception quickly (I guess). Therefore, would you prefer to use check exceptions instead of non-checked ones? However, for reasons of backward compatibility I am unlikely to change signature of impose method to throw checked exceptions. Just curious about your preferences.

I agree with you that forcing a user to put try and catch maybe an annoyance but then you loose a possibility for quick gains if your problem is already not satisfied at the imposition stage.

best,
Radek

[thomasleaute]

Hi Radek,

In light of your explanations, this design decision makes sense. I'll make sure that my code is ready to catch failExceptions at constraint imposition stage.

Best,

Thomas

[thomasleaute]

Hi again,

Taking a second look at your patch has revealed that you have forgotten to check the relation type. As a result, and even though I have not tested it, I expect the patch to fail in half of the cases:

Case	JaCoP result
0 = -1	infeasible
0 = 0	feasible
0 = 1	infeasible
0 <> -1	infeasible
0 <> 0	feasible
0 <> 1	infeasible
0 > -1	infeasible
0 > 0	feasible
0 > 1	infeasible
0 >= -1	infeasible
0 >= 0	feasible
0 >= 1	infeasible
0 < -1	infeasible
0 < 0	feasible
0 < 1	infeasible
0 <= -1	infeasible
0 <= 0	feasible
0 <= 1	infeasible

Best,

Thomas

[radsz]

Hi,

There is no relation "<>" in this constraint. Please use "!=" instead.

Can you provide an example of the test that fails? I tried few things and JaCoP is correct and my understanding of your report is not.

Did you try develop branch?

I tried to find a problem and I can not. For example the test below passes. This was the 10th row reported by you as being infeasible but should be feasible. It is feasible as this test that passes shows.

@Test public void testLinearFeasible3() {
    Store store = new Store();
    IntVar x = new IntVar(store, "x", 0, 0);
    store.impose(new LinearInt(new IntVar[]{x}, new int[]{1}, ">", -1));
    assertTrue(store.consistency());
}

best,
Radek

[radsz]

Hi,

It seems you are not using develop branch. Moreover, in the develop branch no exception is thrown.
Please use develop branch.

best,
Radek

[thomasleaute]

Hi Radek,

You're right, I got confused between branches/versions, and by the tentative changes that Krzysztof made in February to attempt to fix this bug, but which he then reverted to propose a different fix.

I can now confirm that it all works as expected in the develop branch, and that no exception is thrown in impose().

Best,

Thomas