Thread Subject:

Algorithm to check feasibility

Hi,

I am looking for an efficient algorithm (or Matlab code) to check for a given matrix A (mxn) and a vector b (mx1), whether there exists a solution to

A*x < b

I can do this using linprog by minimizing c*x and let the program to tell me whether the constrained set is feasible. However, I am looking for something more efficient (i.e., just check feasibility but not doing any optimization). Any help would be greatly appreciated.


Best,

Raymond

"Raymond Kan" <raykan3@gmail.com> wrote in message <grvu7o$1c6$1@fred.mathworks.com>...
> Hi,
>
> I am looking for an efficient algorithm (or Matlab code) to check for a given matrix A (mxn) and a vector b (mx1), whether there exists a solution to
>
> A*x < b
>
> I can do this using linprog by minimizing c*x and let the program to tell me whether the constrained set is feasible. However, I am looking for something more efficient (i.e., just check feasibility but not doing any optimization). Any help would be greatly appreciated.

------------------------

You can run linprog as you describe but for single iteration only by setting the MaxIter option to 1. I'm pretty sure the algorithms used by linprog generate feasible x at every iteration, so this would be sufficient for the test. This is a lot more efficient than running a full optimization, and perhaps only a little less efficient than digging into linprog and duplicating it's feasibility testing method.

"Raymond Kan" <raykan3@gmail.com> wrote in message <grvu7o$1c6$1@fred.mathworks.com>...
> Hi,
>
> I am looking for an efficient algorithm (or Matlab code) to check for a given matrix A (mxn) and a vector b (mx1), whether there exists a solution to
>
> A*x < b
>
> I can do this using linprog by minimizing c*x and let the program to tell me whether the constrained set is feasible. However, I am looking for something more efficient (i.e., just check feasibility but not doing any optimization). Any help would be greatly appreciated.
-----------------

Come to think of it, what exactly is inefficient about what you are doing now? linprog will automatically analyze for feasibility before it attempts any optimization effort, no?

Hi Matt,

Thanks, setting MaxIter=1 would not work since I always get exitflag=0 regardless of whether the constrained set is feasible or not.

I am hoping that once the algorithm discovers that there exists a solution, then it can stop because I am not interested in the minimization, I am just interested in whether the constrained set is feasible or not.

Any help would be greatly appreciated.

Best,

Raymond

"Raymond Kan" <raykan3@gmail.com> wrote in message <gs0g99$n7v$1@fred.mathworks.com>...
> Hi Matt,
>
> Thanks, setting MaxIter=1 would not work since I always get exitflag=0 regardless of whether the constrained set is feasible or not.

It's a little unclear to me why. But if so, why not set MaxIter=2. Surely, it will have to quite with exitflag=-2 if it can't even get through iteration #1 due to infeasibility.

"Matt " <xys@whatever.com> wrote in message <gs7kmj$1ou$1@fred.mathworks.com>...
> "Raymond Kan" <raykan3@gmail.com> wrote in message <gs0g99$n7v$1@fred.mathworks.com>...
> > Hi Matt,
> >
> > Thanks, setting MaxIter=1 would not work since I always get exitflag=0 regardless of whether the constrained set is feasible or not.
>
> It's a little unclear to me why. But if so, why not set MaxIter=2. Surely, it will have to quite with exitflag=-2 if it can't even get through iteration #1 due to infeasibility.

Hi Matt,

Thanks. The problem is that you we not know how many MaxIter is enough.

Try this problem:

A = [1 1; -1 -1];
b = [1 -2]';
There is obviously no x such that A*x<b

In Matlab, if we do this

options = optimset('MaxIter',1)
[x,fval,exitflag] = linprog(zeros(2,1),A,b,[],[],[],[],[],options)

we get an exitflag=0

If we change MaxIter to 2 or 3, we still get exitflag=0. Only if we change MaxIter to 4, we get exitflag=-2. For a general problem, I cannot know how long it takes for the program to find out the problem is infeasible. If I set MaxIter to be too high, then I run the risk that I am wasting a lot of time optimizing for those problems that are feasible.

Here I use the default interior point method. If I switch to the Simplex problem, I have the same problem because I don't know how long the Phase 1 will take.

Wish there is a function that simply returns 1 or 0 for a given A and b so that we know A*x<=b has feasible solution or not.


Best,

Raymond

"Raymond Kan" <raykan3@gmail.com> wrote in message <gsfk55$bsl$1@fred.mathworks.com>...

>
> ... If I switch to the Simplex problem, I have the same problem because I don't know how long the Phase 1 will take.
>
> Wish there is a function that simply returns 1 or 0 for a given A and b so that we know A*x<=b has feasible solution or not.
>

Raymond,

I believe the first step of simplex method does just that: check whereas a feasible vector exists. If it takes too long, then you are already in trouble using Matlab linprog.

It probably a good time to take a look alternative LP solvers.

Bruno

Hi,

I would like to know if you find out something smart. I also need to check feasibility for a set of constraints.

Thank you very much.

"Raymond Kan" wrote in message <grvu7o$1c6$1@fred.mathworks.com>...
> Hi,
>
> I am looking for an efficient algorithm (or Matlab code) to check for a given matrix A (mxn) and a vector b (mx1), whether there exists a solution to
>
> A*x < b
>
> I can do this using linprog by minimizing c*x and let the program to tell me whether the constrained set is feasible. However, I am looking for something more efficient (i.e., just check feasibility but not doing any optimization). Any help would be greatly appreciated.
>
>
> Best,
>
> Raymond

"Miriam" wrote in message <k980f5$gd1$1@newscl01ah.mathworks.com>...
> Hi,
>
> I would like to know if you find out something smart. I also need to check feasibility for a set of constraints.
================

How complicated are the constraints? If it's a low dimensional problem, LCON2VERT will return empty for an infeasible problem

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

I am also trying to solve this problem. Some people here suggested to use lcon2vert. Although this will give the correct answer it will be much slower than doing the full optimization with linprog. I couldn't find a way to tell linprog to terminate as soon as it found a feasible solution. The best speedup I found was to set LargeScale to off. To check for feasibility I found to methods:

1. Feasible solution exists if exitflag is > 0
2. Feasible solution exists if output.constrviolation<eps, where eps is some small value like 1e-9

Note these two methods can sometimes give different results. So you need to check which is one is best for your application. I hope this helps!