If you have a set of linear inequalities and you just want to know if they are feasible or not, you can form a simple convex optimisation problem or simply a feasibility problem. Say you have a variable vector X = [x, y]
which you want to check the solution for and a set of linear inequalities each of the form a1x + a2y <= b
.
Then you can basically form a matrix A
and a column vector B
by stacking the inequations rowwise, such that each row of A
has the coefficients a1
and a2
for each inequality and the corresponding row of B
has the constant b
. Note that it is better to use either <=
or >=
for all inequalities, so adjust signs accordingly.
Now focus on this problem (assuming all inequalities are in <=
form). You want to solve the following optimization problem, where the objective function has a constant value 0
. This is also known as a feasibility
problem.
minimize 0
subject to AX <= B
Note that if the solution (minimized value) returns infinity
, that means there is no X
which satisfies the above constraints. If the solver returns 0
(which is the value of the constant objective function), that means there is atleast one X
which satisfies the constraints. Hence you can find if there exists any solution to your inqualities.
You can use cvxpy
library for this. Here is a nice tutorial in python
. Also cvxpy
library goes well with numpy
and it takes care of all the internal solver
details for you. You can even restrict your variable X
to take real
or integer
values and also impose bound constraints in terms of linear inequalities like x + 0.y < = a
etc.
CLICK HERE to find out more related problems solutions.