Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Algorithm to check feasibility

Subject: Algorithm to check feasibility

From: Raymond Kan

Date: 13 Apr, 2009 17:54:01

Message: 1 of 10

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

Subject: Algorithm to check feasibility

From: Matt

Date: 13 Apr, 2009 20:24:01

Message: 2 of 10

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

Subject: Algorithm to check feasibility

From: Matt

Date: 13 Apr, 2009 20:31:01

Message: 3 of 10

"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?

Subject: Algorithm to check feasibility

From: Raymond Kan

Date: 13 Apr, 2009 23:02:01

Message: 4 of 10

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

Subject: Algorithm to check feasibility

From: Matt

Date: 16 Apr, 2009 16:00:19

Message: 5 of 10

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

Subject: Algorithm to check feasibility

From: Raymond Kan

Date: 19 Apr, 2009 16:40:05

Message: 6 of 10

"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

Subject: Algorithm to check feasibility

From: Bruno Luong

Date: 19 Apr, 2009 17:11:01

Message: 7 of 10

"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

Subject: Algorithm to check feasibility

From: Miriam

Date: 29 Nov, 2012 15:54:13

Message: 8 of 10

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

Subject: Algorithm to check feasibility

From: Matt J

Date: 29 Nov, 2012 19:46:15

Message: 9 of 10

"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

Subject: Algorithm to check feasibility

From: Dmitri Kamenetsky

Date: 21 Mar, 2013 01:03:11

Message: 10 of 10

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!

Tags for this Thread

No tags are associated with this thread.

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us