# How can I find all possible solutions to a LP?

4 views (last 30 days)
Arjun M on 23 Aug 2022
Edited: Bruno Luong on 23 Aug 2022
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.

Matt J on 23 Aug 2022
Edited: Matt J on 23 Aug 2022
If the convex hull is a bounded polyhedron, you can use lcon2vert from,
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.
Bruno Luong on 23 Aug 2022
Edited: Bruno Luong on 23 Aug 2022
@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.