I want to solve a system of linear inequalities in Matlab, where the unknowns are x(1), x(2), x(3), x(4). I want the entire set of solutions x(1), x(2), x(3), x(4). Hence, I can't use linprog because it gives me just one feasible point.
Clarification: This question https://stackoverflow.com/questions/37258835/how-to-set-the-objective-function-when-using-linprog-in-matlab-to-solve-a-system was about linprogr which however gives only one possible solution. Here I'm asking how to find the entire set of solutions.
This is the set of inequalities. Any suggestion?
5x(1)+3x(2)+3x(3)+5x(4)<5
-5x(1)-3x(2)-3x(3)-5x(4)<-3
-x(2)-x(3)<0
x(2)+x(3)<1
-x(1)-x(4)<0
x(1)+x(4)<1
-3x(3)-5x(4)<-1
3x(3)+5x(4)>3
x(3)<1
-x(3)<0
x(4)<1
-x(4)<0
-5x(1)-3x(2)<0
5x(1)+3x(2)<2
x(2)<1
-x(2)<0
x(1)<1
-x(1)<0
With continuous variables we basically have zero, one or infinitely many solutions. Of course showing all the solutions is not possible for this. However, there is a concept of corner points in linear programming, and those points we can enumerate, although with much effort.
Here are some links for tools that can do this:
A different approach is to enumerate the optimal bases using extra binary variables. (You have a zero objective so this becomes effectively: enumerating all feasible LP bases). This approach makes the problem a MIP. We can enumerate this by an algorithm like:
Here is a link that illustrates this approach to enumerate all optimal bases of a (continuous) LP problem.
Note that enumerating all integer solutions of a system of inequalities is easier. Many constraint programming tools will do that for you automatically. In addition we can use the "cutting plane" technique described above.