How can I find all possible solutions to a LP?

Question

Arjun M 2022-8-23

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1784010-how-can-i-find-all-possible-solutions-to-a-lp

编辑： Bruno Luong 2022-8-23

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.

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Matt J 2022-8-23

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1784010-how-can-i-find-all-possible-solutions-to-a-lp#answer_1031180

编辑：Matt J 2022-8-23

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.

5 个评论
显示 3更早的评论隐藏 3更早的评论

Matt J 2022-8-23

编辑：Matt J 2022-8-23

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.

Torsten 2022-8-23

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

Bruno Luong 2022-8-23

编辑：Bruno Luong 2022-8-23

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

请先登录，再进行评论。