How can I find all possible solutions to a LP?

I have a LP with 4 variables and 12 constriants. How can I get all the possible solutions to this problem? I would ideally like to get them in the form of a matrix or arrays.

Another part of this is, how can I get the extreme points of a convex hull using MATLAB? If there are 4 lines and they form a convex hull, how can I get the extreme points of this?

Thank you for any help.

Answer 1

[Matt J]

If the convex hull is a bounded polyhedron, you can use lcon2vert from,

https://www.mathworks.com/matlabcentral/fileexchange/30892-analyze-n-dimensional-convex-polyhedra

to get its vertices.

To find all possible optimal solutions, you must evaluate the objective function at all the vertices. The set of all possible solutions will be the convex hull of the optimal vertices.

[Arjun M]

Did you mean lcon2vert? Also, when I tried lcon2vert, I am getting null vector.

What do you mean by evaluating at all vertices? Also, I would like to have a method such that it can be applied even if I scale the problem further.

[Matt J]

Did you mean lcon2vert? Also, when I tried lcon2vert, I am getting null vector.

Whoops, yes, lcon2vert. I'm not clear on what you mean by a null vector. If you mean an empty matrix [] was returned, it means the constraints are infeasible, or at least lcon2vert believes so. Make sure you are not using inequality constraints to express equality constraints. For example, x==0 should not be expressed using simultaneous inequality constrains x>=0, x<=0.

What do you mean by evaluating at all vertices?

lcon2vert will normally return a list of the vertices of the convex hull. Your LP has an objective function. The objective function optimum will be attained at one or more of the vertices. By evaluating your objective at the vertices, you can determine which vertices are optimal.

Also, I would like to have a method such that it can be applied even if I scale the problem further.

You may be able to go higher than with lcon2vert. It depends on other factors like how many constraints you have. However, you have no hope of scaling to arbitrary . Imagine the simple constraints 0<=x<=1 in . There are 2^n vertices even in that simple case.

[Arjun M]

Thank you for the reply. Please see the attached image. I got an empty matrix when I tried this. What do you think I must have done wrong?

[Torsten]

And where is the code in which you tried it ? And what is 3* ?

[Bruno Luong]

@Arjun M As written b does not have lower bounds, so the admissibles set is unbounded.

Such set cannot be characterized fully by the vertexes (what you ask), and until you provide the cost gradient f the request of all possible solutions is not possible.

And the question has non sense for a computer to enumerate : the LP either has 0, one solution or inifity solution. Indeed if there are two or more distinct solutions then all the points in the convex combination are solutions, so the set is ininity, impossible to enumerate them.