Infeasibility and inconsistency¶

When submitting a model to LocalSolver (calling method solve), the expected result is to obtain a feasible solution, and even sometimes an optimal solution. However in some cases the returned solution can be infeasible in the sense that the current assignement of values to variables violates some of the constraints of the problem. Two solution status (see getSolutionStatus) are defined for these infeasibilty cases:

infeasible means that no feasible solution was found to the submitted problem but it could not be proven that no such solution exists. Maybe running a longer search would have produced a feasible solution.
inconsistent means that the solver was able to prove that no feasible solution exists. In this case, LocalSolver offers a functionality for analyzing the causes of this inconsistency.

Note

Note that both status infeasible and inconsistent can also be encountered on problems where no constraint was defined. Indeed some LocalSolver expressions induce an implicit constraint on their operands. For instance sqrt(x) implicitly requires that x takes a non-negative value.

Analyzing inconsistencies¶

Analyzing an inconsistent model amounts to identifying a relatively small inconsistent subproblem. Such a subproblem or inconsistency core is said to be irreductible if it contains no smaller inconsistent subproblem.

The function computeInconsistency computes such a core that is to say a set of expressions (named causes) such that the problem restricted to these expressions and their descendents is inconsistent. Calling this function requires the model to be closed and the solver to be stopped. This inconsistency core is returned as an LSInconsistency object. This object can be printed in a readable form so that the user can easily spot the origin of the inconsistency. It also allows scanning the set of identified causes.

For example, the following model is inconsistent because limiting the cube of y to 250 prevents y from taking values larger than 6, what make the constraint 3*x + y >= 20 impossible to satisfy:

function model() {
    x <- bool();
    y <- int(0,100);
    z <- bool();
    t <- int(0,100);
    constraint 3*x + y >= 20;
    constraint pow(y,3) <= 250;
    constraint 4*z + t <= 18;
    maximize x*t + 8*z*y;
}

The computation of the inconsistency core can be launched in the output function as follows:

function output() {
    iis = computeInconsistency();
    println(iis);
}

The resulting output on the standard console is the following:

...
Run output...
Computing inconsistency core...
Inconsistency core found with 2 causes.
Irreductible inconsistency core found with 2 causes.
2 causes in inconsistency core:
        pow(int(0, 100)#1, 3)  <=  250
        3  *  bool()#0  +  int(0, 100)#1  >=  20

The two constraints responsible for the inconsistency are identified and displayed. Note that expressions are identified by their type and index. It is also possible to assign names to variables in the model function:

x.name = "x";
y.name = "y";
z.name = "z";
t.name = "t";

Having defined these names the inconsistency core reads as follows:

2 causes in inconsistency core:
        pow(y, 3)  <=  250
        3  *  x  +  y  >=  20

Note

In version 6.0, this functionality is offered in beta version: only explicit constraints are considered as potential causes of the inconsistency unless a single non-constraint expression is sufficient to cause the inconsistency. If the inconsistency core is empty it can mean that the problem is consistent or that its inconsistency derives of the combination of several implicit constraints.