InfeasibleSubset

R2026b

Irreducible infeasible subset of linear constraints

Since R2026b

expand all in page

Description

An InfeasibleSubset object stores the result of an irreducible infeasible subset (IIS) computation. The object identifies which constraints and variable bounds belong to the irreducible infeasible subset, which is a minimal subset of constraints that is still infeasible but becomes feasible if any single constraint or bound is removed.

Creation

Create an InfeasibleSubset object by calling the findiis function.

is = findiis(A,b,Aeq,beq,lb,ub,Options=options)
% or
is = findiis(prob)

Properties

expand all

This property is read-only.

Status of the IIS computation, returned as one of the following values.

Irreducible

findiis finds an irreducible infeasible subset. Removing any single constraint or bound from the subset makes it feasible.

Feasible

The constraints are feasible. No infeasible subset exists.

Infeasible

findiis finds an infeasible subset, but cannot confirm that it is irreducible.

TimeLimitExceeded

findiis stops because it exceeded the MaxTime limit. The returned subset might not be irreducible.

CannotEstablishInfeasibility

findiis cannot establish whether the constraints are infeasible.

Candidate

findiis finds a candidate subset with potential conflict but cannot prove infeasibility.

This property is read-only.

Exit message describing the result of the IIS computation, returned as a string.

This property is read-only.

Variable bounds in the IIS, returned as a structure. The structure contains a field for each optimization variable.

  • Solver-based: In the solver-based approach, Variables contains a structure x.

  • Problem-based: In the problem-based approach, Variables contains field names from the optimization problem prob.

Each variable field is a structure with the following subfields.

Lower

Logical vector indicating which lower bounds are in the IIS

Upper

Logical vector indicating which upper bounds are in the IIS

For example, if is.Variables.x.Lower is [true; false; true], then the lower bounds on x(1) and x(3) are part of the infeasible subset.

This property is read-only.

Constraints in the IIS, returned as a structure with the following fields. Each field is a logical vector indicating which constraints of that type are in the infeasible subset.

  • Solver-based. In the solver-based approach, Constraints contains the fields listed below.

    LinearEquality

    Logical vector indicating which equality constraints (Aeq*x = beq) are in the IIS

    LinearInequalityLower

    Logical vector indicating which lower bounds on inequality constraints are in the IIS; applies when b is specified as a cell array {bl,b}

    LinearInequalityUpper

    Logical vector indicating which upper bounds on inequality constraints (A*x ≤ b) are in the IIS

  • Problem-based: In the problem-based approach, Constraints contains field names from the optimization problem prob.

For example, if is.Constraints.LinearEquality is [false; true], then the second equality constraint is part of the infeasible subset.

Object Functions

showDisplay information about optimization object

Examples

collapse all

Open Live Script

Use findiis to create an InfeasibleSubset object, and examine the object properties to see which constraints cause infeasibility.

Create an infeasible set of linear inequality constraints and bounds.

A = [1 1; -1 0; 0 -1; 1 0];
b = [1; 0; 0; 5];
lb = [2; 3];
ub = [10; 10];

Call findiis to find an irreducible infeasible subset.

is = findiis(A,b,[],[],lb,ub)
Irreducible infeasible subset found.

is = 
  InfeasibleSubset with properties:

      Variables: [1×1 struct]
    Constraints: [1×1 struct]
         Status: Irreducible
        Message: "Irreducible infeasible subset found."

The returned InfeasibleSubset object shows that findiis found an irreducible infeasible subset. Call show to see a readable display of the contents of is.

show(is)
  InfeasibleSubset :

	members in LinearInequalityUpper:
     (1, 1)

       x(1) + x(2) <= 1

	members in variable bounds:
       2 <= x(1)
       3 <= x(2)

Alternatively, examine the properties directly.

is.Variables.x
ans = struct with fields:
    Lower: [2×1 logical]
    Upper: [2×1 logical]


is.Variables.x.Lower
ans = 2×1 logical array

   1
   1


is.Variables.x.Upper
ans = 2×1 logical array

   0
   0

Both lower bounds are part of the infeasible subset.

Examine the Constraints property to see which inequality constraints are in the IIS. Because the problem has only upper linear inequality constraints, examine is.Constraints.LinearInequalityUpper.

is.Constraints.LinearInequalityUpper
ans = 4×1 logical array

   1
   0
   0
   0

The first inequality constraint (x(1) + x(2) ≤ 1) is the only linear inequality in the IIS. Together with the two lower bounds, these three constraints form the irreducible infeasible subset.

Open Live Script

After solve reports infeasibility, pass the optimization problem to findiis to diagnose which constraints conflict.

Create an optimization problem with conflicting constraints.

x = optimvar("x",LowerBound=0,UpperBound=3);
y = optimvar("y",LowerBound=0,UpperBound=4);
prob = optimproblem(Objective=x+y);
prob.Constraints.sumcon = x + y == 10;

Try to solve the problem. The solver reports that the problem is infeasible.

[sol,fval,exitflag] = solve(prob)
Solving problem using linprog.

No feasible solution found.

Linprog stopped because no point satisfies the constraints.

sol = struct with fields:
    x: []
    y: []


fval =

     []

exitflag = 
    NoFeasiblePointFound

Pass the problem object directly to findiis to identify the conflicting constraints.

is = findiis(prob)
Irreducible infeasible subset found.

is = 
  InfeasibleSubset with properties:

      Variables: [1×1 struct]
    Constraints: [1×1 struct]
         Status: Irreducible
        Message: "Irreducible infeasible subset found."

Use show to display the infeasible subset in a readable format.

show(is)
  InfeasibleSubset :

	members in sumcon:
       x + y == 10

	members in variable bounds:
       x <= 3

       y <= 4

The display shows the specific constraints and bounds that form the irreducible infeasible subset, helping you to decide which constraints to relax or remove.

More About

expand all

Version History

Introduced in R2026b

See Also

| |

Topics