Is there a way to know if constraints are not too restricitve.

Hi everyone,

I was wondering, given a constraint type a.x =<b

Is there a quick way to know if the boundaries are not too restrictive to allow at least one solution?

Given an easy example:

[0 0 -1 -1 -0.5; -1 -1 0 0 -0.5; -1 -1 -1 -1 -1; 1 1 1 1 1]

Thank you!

[Matt J]

Is your example data the "a" matrix? If so, where's the b vector to go with it?

[Johan]

Sorry, b is the last column.

Answer 1

[Matt J]

If you know it to be a bounded feasible set, you can check if it has a non-empty set of vertices using LCON2VERT in

http://www.mathworks.com/matlabcentral/fileexchange/30892-representing-polyhedral-convex-hulls-by-vertices-or-inequalities

[Johan]

Actually, what I want to know is if is it a boundable feasible set.

[Matt J]

Then you should edit your question, since unboudedness is a very different issue from infeasibility.

[Matt J]

If the problem is now to test for unboundedness, you can use VERT2LCON, which is part of the same package as LCON2VERT,

    [AA,BB,AAeq,BBeq]=vert2lcon(a);

    isUnbounded =  any(BB<=0) || ~isempty(BBeq)

[Johan]

Thank you, I hope it is more clear for everyone.

[Matt J]

No, your question still reads "if the boundaries are not too restrictive to allow at least one solution". But anyway, if the number of constraints is not too large, you might try VERT2LCON as I outlined above.

[Johan]

I think I am hopeless, but it is what I am looking for. I want to know if the fact of putting constraints such as 1*a > 1, 1*b>1, a+b =1. In that case it is impossible to find a solution... Thank you for your answers.

[Matt J]

Then you should restore your question back to its original form. You are asking about whether the feasible set is empty/nonempty, not whether the feasible set is bounded/unbounded.

In any case, you have both answers, but it is practical mainly for low dimensional problems.