findiis

R2026b

Find irreducible infeasible subset of linear constraints

Since R2026b

Syntax

is = findiis(A,b)

is = findiis(A,b,Aeq,beq)

is = findiis(A,b,Aeq,beq,lb,ub)

is = findiis(___,Options=options)

is = findiis(prob)

Description

Given an infeasible set of linear constraints and bounds, findiis identifies an irreducible infeasible subset (IIS), which is a minimal subset of constraints that is still infeasible but becomes feasible if any single constraint is removed.

is = findiis(A,b) finds an IIS of the constraints A*x ≤ b.

is = findiis(A,b,Aeq,beq) also includes the equality constraints Aeq*x = beq. Set A = [] and b = [] if no inequalities exist.

is = findiis(A,b,Aeq,beq,lb,ub) defines a set of lower and upper bounds on the variables, so that lb ≤ x ≤ ub. Set Aeq = [] and beq = [] if no equalities exist.

is = findiis(___,Options=options) specifies additional options using any of the input argument combinations in the previous syntaxes. For example, Options=optimoptions("findiis",MaxTime=10) sets a time limit of 10 seconds.

is = findiis(prob) finds an IIS for an optimization problem. findiis ignores any nonlinear constraints in prob.

Examples

Find IIS of Infeasible Linear Program

Identify which constraints make a linear program infeasible by using findiis.

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 on is to see which constraints and bounds belong to the IIS.

show(is)

  InfeasibleSubset :

	members in LinearInequalityUpper:
     (1, 1)

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

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

Specify Time Limit for Finding IIS

Set a time limit for the IIS computation using the Options argument.

Create an infeasible set of linear constraints.

A = [0 -1; 1 0; -1 1];
b = [-6; 4; -1];
Aeq = [1 1];
beq = 5;
lb = [0; 0];
ub = [1; Inf];

Specify options that set a time limit of 0.5 seconds.

options = optimoptions("findiis",MaxTime=0.5);

Call findiis with the options.

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

Irreducible infeasible subset found.

is = 
  InfeasibleSubset with properties:

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

The MaxTime option ensures that findiis stops if the computation takes longer than 0.5 seconds. Examine the result to identify the conflicting constraints.

show(is)

  InfeasibleSubset :

	members in LinearInequalityUpper:
     (1, 1)

       -x(2) <= -6

     (3, 1)

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

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

Determine Infeasibility in Problem-Based Workflow

Create an optimization problem with conflicting constraints.

After the solve function reports infeasibility, pass the problem object to findiis to determine which constraints conflict.

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. solve 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 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."

Display the infeasible subset in a readable format by using show.

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 decide which constraints to relax or remove.

Input Arguments

A — Linear inequality constraints

real matrix

Linear inequality constraints, specified as a real matrix. A is an M-by-N matrix, where M is the number of inequalities, and N is the number of variables.

A encodes the M linear inequalities

A*x <= b,

(1)

where x is the column vector of N variables x(:), and b is a column vector with M elements.

For example, consider these inequalities:

x 1 + 2x 2 ≤ 10 3x 1 + 4x 2 ≤ 20 5x 1 + 6x 2 ≤ 30.

(2)

Specify the inequalities by entering the following constraints.

A = [1,2;3,4;5,6];
b = [10;20;30];

Example: To specify that the x components sum to 1 or less, use A = ones(1,N) and b = 1.

Data Types: double

b — Linear inequality constraints

real vector

Linear inequality constraints, specified as a real vector. b is an M-element vector related to the A matrix. If you pass b as a row vector, solvers internally convert b to the column vector b(:).

b encodes the M linear inequalities

A*x <= b,

(3)

where x is the column vector of N variables x(:), and A is a matrix of size M-by-N.

For example, consider these inequalities:

x 1 + 2x 2 ≤ 10 3x 1 + 4x 2 ≤ 20 5x 1 + 6x 2 ≤ 30.

(4)

Specify the inequalities by entering the following constraints.

A = [1,2;3,4;5,6];
b = [10;20;30];

Example: To specify that the x components sum to 1 or less, use A = ones(1,N) and b = 1.

Data Types: double

Aeq — Linear equality constraints

real matrix

Linear equality constraints, specified as a real matrix. Aeq is an Me-by-N matrix, where Me is the number of equalities, and N is the number of variables. For large problems, pass Aeq as a sparse matrix.

Aeq encodes the Me linear equalities

Aeq*x = beq,

where x is the column vector of N variables x(:), and beq is a column vector with Me elements.

For example, consider these equalities:

x₁ + 2x₂ + 3x₃ = 10
2x₁ + 4x₂ + x₃ = 20.

Specify the equalities by entering the following constraints.

Aeq = [1,2,3;2,4,1];
beq = [10;20];

Example: To specify that the x components sum to 1, use Aeq = ones(1,N) and beq = 1.

Data Types: double

beq — Linear equality constraints

real vector

Linear equality constraints, specified as a real vector. beq is an Me-element vector related to the Aeq matrix. If you pass beq as a row vector, solvers internally convert it to the column vector beq(:).

beq encodes the Me linear equalities

Aeq*x = beq,

(5)

where x is the column vector of N variables x(:), and Aeq is a matrix of size Me-by-N.

For example, consider these equalities:

x 1 + 2x 2 + 3x 3 = 10 2x 1 + 4x 2 + x 3 = 20.

(6)

Specify the equalities by entering the following constraints.

Aeq = [1,2,3;2,4,1];
beq = [10;20];

Example: To specify that the x components sum to 1, use Aeq = ones(1,N) and beq = 1.

Data Types: double

lb — Lower bounds

real vector | real array

Lower bounds, specified as a real vector or real array. lb specifies that the solution x satisfies

x(i) >= lb(i) for all i.

(7)

Example: To specify that all x components are positive, use lb = zeros(size(f)), where f is a vector the same size as lb.

Data Types: double

ub — Upper bounds

real vector | real array

Upper bounds, specified as a real vector or real array. ub specifies that the solution x satisfies

x(i) <= ub(i) for all i.

(8)

Example: To specify that all x components are less than 1, use ub = ones(size(f)), where f is a vector the same size as ub.

Data Types: double

prob — Optimization problem

OptimizationProblem object

Optimization problem, specified as an OptimizationProblem object. Create an optimization problem by using optimproblem.

Warning

The problem-based approach does not support complex values in the objective function, nonlinear equalities, and nonlinear inequalities. If a function calculation has a complex value, even as an intermediate value, the final result might be incorrect.

Example: prob = optimproblem; prob.Objective = obj; prob.Constraints.cons1 = cons1;

options — Optimization options

output of optimoptions

Optimization options, specified as the output of optimoptions.

Option	Description
ConstraintTolerance	Feasibility tolerance for constraints, a nonnegative scalar. The default is 1e-7.
Display	Level of display: "final" (default) displays the exit message. "off" or "none" displays no output. "iter" displays output at each iteration.
MaxTime	Maximum amount of time that the algorithm runs. Specify a duration or a scalar, which is interpreted as the number of seconds. The default is Inf.
OptimalityTolerance	Dual feasibility tolerance, a nonnegative scalar. The default is 1e-7.

Example: options = optimoptions("findiis",MaxTime=10,Display="iter")

Output Arguments

is — Irreducible infeasible subset

InfeasibleSubset object

Irreducible infeasible subset, returned as an InfeasibleSubset object with the following properties.

Property	Description
Status	Status of the IIS computation, returned as one of the following: Candidate (–3) — findiis identifies a candidate subset with potential conflict but cannot prove infeasibility. Feasible (–2) — The constraints are feasible. No infeasible subset exists. CannotEstablishInfeasibility ( –1) — findiis cannot establish whether the constraints are infeasible. TimeLimitExceeded (0) — findiis stops because it exceeded the MaxTime limit. The returned subset might not be irreducible. Irreducible (1) — findiis finds an irreducible infeasible subset. Infeasible (2) — findiis finds an infeasible subset, but cannot confirm that it is irreducible.
Message	Reason the search stopped, returned as a string.
Variables	Structure identifying which variable bounds are in the IIS. Solver-based: Contains a field x with subfields Lower and Upper. Each subfield is a logical vector. Problem-based: Field names are given in the optimization problem prob, and these fields have subfields Lower and Upper. Each subfield is a logical vector.
Constraints	Structure identifying which constraints are in the IIS. Solver-based In the solver-based approach, Constraints contains the following fields, each a logical vector: LinearEquality — Equality constraints in the IIS LinearInequalityLower — Lower bounds on inequality constraints in the IIS LinearInequalityUpper — Upper bounds on inequality constraints in the IIS Problem-based In the problem-based approach, Constraints contains field names from the optimization problem prob. Each field is a logical vector.

More About

Irreducible Infeasible Subset

An irreducible infeasible subset (IIS) is a set of constraints and variable bounds that satisfies two conditions:

• The constraints in the set are infeasible, which means that no point satisfies all of them simultaneously.

• The set is irreducible, which means that removing any single constraint or bound makes the remaining set feasible.

Finding an IIS helps you determine why a linear program is infeasible by identifying a minimal conflicting subset of constraints, rather than examining all constraints.

An infeasible problem can have more than one IIS. The findiis function returns one IIS. To make the full problem feasible, you might need to resolve multiple overlapping infeasible subsets by iteratively calling findiis after removing or relaxing constraints.

Algorithms

findiis uses the HiGHS IIS algorithm to identify irreducible infeasible subsets. The algorithm solves a sequence of linear programs, systematically removing constraints to determine a minimal infeasible subset.

Version History

Introduced in R2026b