Investigate Linear Infeasibilities

R2026b

This example shows how to investigate the linear constraints that cause a problem to be infeasible. For further details about these techniques, see Chinneck [1] and [2].

If linear constraints cause a problem to be infeasible, you might want to find a subset of the constraints that is infeasible, but removing any member of the subset makes the rest of the subset feasible. The name for such a subset is Irreducible Infeasible Subset of Constraints, abbreviated IIS. A problem can have many different IISs, some with different cardinality.

This example shows how to use the findiis function to find and remove IISs.

Infeasible Example

Create a random matrix A representing linear inequalities of size 150-by-15. Set the corresponding vector b to a vector with entries of 10, and change 5% of those values to –10.

N = 15;
rng default
A = randn([10*N,N]);
b = 10*ones(size(A,1),1);
Aeq = [];
beq = [];
b(rand(size(b)) <= 0.05) = -10;
f = ones(N,1);
lb = -f;
ub = f;

Check that problem is infeasible.

[x,fval,exitflag,output,lambda] = linprog(f,A,b,Aeq,beq,lb,ub);

No feasible solution found.

Linprog stopped because no point satisfies the constraints.

Find IIS

Find an IIS by calling findiis.

is = findiis(A,b,Aeq,beq,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."

Examine details of this IIS.

show(is)

  InfeasibleSubset :

	members in LinearInequalityUpper:
     (60, 1)

       1.1174*x(1) - 0.14605*x(2) - 0.90473*x(3) - 1.8543*x(4) - 1.1489*x(5) - 0.58959*x(6) + 0.16851*x(7) - 0.14933*x(8) - 0.36463*x(9) - 0.79385*x(10) - 0.31989*x(11) - 0.18559*x(12) - 0.01276*x(13) + 0.47168*x(14) - 0.4157*x(15) <= -10

	members in variable bounds:
       -1 <= x(1)
             x(2)  <= 1
             x(3)  <= 1
             x(4)  <= 1
             x(5)  <= 1
             x(6)  <= 1
       -1 <= x(7)
             x(8)  <= 1
             x(9)  <= 1
             x(10) <= 1
             x(11) <= 1
             x(12) <= 1
             x(13) <= 1
       -1 <= x(14)
             x(15) <= 1

Remove IIS in a Loop

One way to correct an infeasible problem is to repeatedly find an IIS and remove a constraint in the IIS until the problem becomes feasible.

The removeInfeasibilities function, listed next, removes one constraint at a time from a problem until the problem becomes feasible. The function uses an indexing technique to refer to the original problem constraints so that, as the function removes constraints, the remaining constraints are in a matrix without missing rows.

function [A, b, Aeq, beq, lb, ub] = removeInfeasibilities(A, b, Aeq, beq, lb, ub)
%REMOVEINFEASIBILITIES Iteratively remove constraints to make a linear program feasible.
%   [A, b, Aeq, beq, lb, ub] = removeInfeasibilities(A, b, Aeq, beq, lb, ub)
%   repeatedly calls findiis to find an irreducible infeasible subset, removes
%   one constraint from that subset, and continues until findiis reports the
%   problem is feasible. Returns the modified constraint matrices and bounds.
 
[mIneq, ~] = size(A);
mEq = size(Aeq, 1);
 
% Maps from current row index to original row index
ineqMap = (1:mIneq)';
eqMap = (1:mEq)';
 
% Accumulators for removed original indices
removedIneq = [];
removedEq = [];
removedLB = [];
removedUB = [];
 
% Suppress display
opts = optimoptions("findiis", Display="none");

iter = 0;
while true
    % Find an irreducible infeasible subset (also serves as feasibility check)
    is = findiis(A, b, Aeq, beq, lb, ub, Options=opts);
    if is.Status == "Feasible"
        break;
    end

    iter = iter + 1;
 
    % Identify which constraints are in the IIS
    iisIneqUpper = find(is.Constraints.LinearInequalityUpper);
    iisIneqLower = find(is.Constraints.LinearInequalityLower);
    iisEq        = find(is.Constraints.LinearEquality);
    iisLB        = find(is.Variables.x.Lower);
    iisUB        = find(is.Variables.x.Upper);
 
    % Remove one constraint from the IIS.
    % Priority: inequalities > equalities > bounds.
    if ~isempty(iisIneqUpper)
        idx = iisIneqUpper(1);
        origIdx = ineqMap(idx);
        fprintf('Iteration %d: Removed inequality %d (upper)\n', iter, origIdx);
        removedIneq(end+1) = origIdx; %#ok<AGROW>
        A(idx, :) = [];
        b(idx) = [];
        ineqMap(idx) = [];
    elseif ~isempty(iisIneqLower)
        idx = iisIneqLower(1);
        origIdx = ineqMap(idx);
        fprintf('Iteration %d: Removed inequality %d (lower)\n', iter, origIdx);
        removedIneq(end+1) = origIdx; %#ok<AGROW>
        A(idx, :) = [];
        b(idx) = [];
        ineqMap(idx) = [];
    elseif ~isempty(iisEq)
        idx = iisEq(1);
        origIdx = eqMap(idx);
        fprintf('Iteration %d: Removed equality %d\n', iter, origIdx);
        removedEq(end+1) = origIdx; %#ok<AGROW>
        Aeq(idx, :) = [];
        beq(idx) = [];
        eqMap(idx) = [];
    elseif ~isempty(iisLB)
        idx = iisLB(1);
        fprintf('Iteration %d: Relaxed lower bound on variable %d\n', iter, idx);
        removedLB(end+1) = idx; %#ok<AGROW>
        lb(idx) = -Inf;
    elseif ~isempty(iisUB)
        idx = iisUB(1);
        fprintf('Iteration %d: Relaxed upper bound on variable %d\n', iter, idx);
        removedUB(end+1) = idx; %#ok<AGROW>
        ub(idx) = Inf;
    else
        error('removeInfeasibilities:noProgress', ...
            'findiis returned an empty IIS but the problem is still infeasible.');
    end
end
 
% Print summary
fprintf('\n--- Summary ---\n');
if isempty(removedIneq) && isempty(removedEq) && isempty(removedLB) && isempty(removedUB)
    fprintf('Problem was already feasible. No constraints removed.\n');
else
    if ~isempty(removedIneq)
        fprintf('Removed inequalities: %s\n', joinIndices(removedIneq));
    end
    if ~isempty(removedEq)
        fprintf('Removed equalities: %s\n', joinIndices(removedEq));
    end
    if ~isempty(removedLB)
        fprintf('Relaxed lower bounds on variables: %s\n', joinIndices(removedLB));
    end
    if ~isempty(removedUB)
        fprintf('Relaxed upper bounds on variables: %s\n', joinIndices(removedUB));
    end
    fprintf('Problem is now feasible after %d iterations.\n', iter);
end
 
end
 
function s = joinIndices(idx)
%JOININDICES Format a vector of indices as "2, 4, and 10".
    idx = sort(idx);
    n = numel(idx);
    if n == 1
        s = sprintf('%d', idx);
    elseif n == 2
        s = sprintf('%d and %d', idx(1), idx(2));
    else
        s = strjoin(arrayfun(@num2str, idx(1:end-1), 'UniformOutput', false), ', ');
        s = sprintf('%s, and %d', s, idx(end));
    end
end

Run the removeInfeasibilities function on the problem. Add "f" to each parameter name to indicate the "fixed" version.

[Af,bf,Aeqf,beqf,lbf,ubf] = removeInfeasibilities(A, b, Aeq, beq, lb, ub);

Iteration 1: Removed inequality 60 (upper)
Iteration 2: Removed inequality 97 (upper)
Iteration 3: Removed inequality 114 (upper)
Iteration 4: Removed inequality 64 (upper)
Iteration 5: Removed inequality 2 (upper)
Iteration 6: Removed inequality 54 (upper)

--- Summary ---
Removed inequalities: 2, 54, 60, 64, 97, and 114
Problem is now feasible after 6 iterations.

Verify that the new parameters represent a feasible linear program.

[x,fval,exitflag,output,lambda] = linprog(f,Af,bf,Aeqf,beqf,lbf,ubf)

Optimal solution found.

fval = 
2.2212

exitflag = 
1

output = struct with fields:
         iterations: 4
    constrviolation: 0
            message: 'Optimal solution found.'
          algorithm: 'dual-simplex-highs'
      firstorderopt: 4.4409e-16

lambda = struct with fields:
           lower: [15×1 double]
           upper: [15×1 double]
           eqlin: [0×1 double]
    ineqlinLower: [144×1 double]
         ineqlin: [144×1 double]

References

[1] Chinneck, J. W. Feasibility and Infeasibility in Optimization: Algorithms and Computational Methods. Springer, 2008.

[2] Chinneck, J. W. "Feasibility and Infeasibility in Optimization." Tutorial for CP-AI-OR-07, Brussels, Belgium. Available at https://www.sce.carleton.ca/faculty/chinneck/docs/CPAIOR07InfeasibilityTutorial.pdf.

Investigate Linear Infeasibilities

Infeasible Example

Find IIS

Remove IIS in a Loop

References

See Also

Topics