Say I have a system of linear equalities and inequalities with integer coefficients in n variables,

glutynowy44 2022-07-01 Answered
Say I have a system of linear equalities and inequalities with integer coefficients in n variables, and let R n be the space of all possible solutions. I know that 0 is a solution.
Is there any efficient algorithm to check if there are any other solutions but zero? In other words, given a linear optimization problem, is there a way to check if the feasible region is a point?
You can still ask an expert for help

Want to know more about Inequalities systems and graphs?

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question

Answers (2)

Monserrat Cole
Answered 2022-07-02 Author has 12 answers
I think the following is pretty much it:
Bring the problem into canonical form (where all variables are greater than zero) and checking for maximum of the function f ( x ) = ( 1 , 1 , . . . , 1 ) x using any LP solver.
Since no variable can be negative, the maximum can only be greater than 0 iff there's no unique solution.

We have step-by-step solutions for your answer!

Holetaug
Answered 2022-07-03 Author has 8 answers
You can use some LP solver to find the min f and max f for some non zero linear function min f = max f = 0 if and only if 0 is the unique point in your feasible region

We have step-by-step solutions for your answer!

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

You might be interested in

asked 2022-06-24
Find the minimum value of C subject to the given constraints
C = 2 x + 5 y
Constraints:
x + y 2
2 x 3 y 6
3 x 2 y 6
A. 42
B. 4
C. 49
D. 10
asked 2022-06-19
find the solution of the following two inequalities for variables p and q:
p < p 2 4 q
p < p 2 4 q
asked 2022-07-07
Is there a real solution to: B A , B C? Namely, is there s = ( α , β , γ , δ ) R 4 such that B ( s ) A ( s ) , B ( s ) C ( s )?
asked 2021-02-06
Sketch the graph of the solution of the system of linear inequlities
-3x+2y<6
x+4y>-2
2x+y<3
asked 2022-06-14
Minimal set of inequalities
I have a set of m linear inequalities in Rn, of the form
A x b
These are automatically generated from the specification of my problem. Many of them could be removed because they are implied by the others.
I would like to find the minimal set of inequalities,
A x b
such that a solution to the first problem is also a solution to the second, and vice versa.
asked 2022-05-26
Suppose that you are trying to solve the optimization problem:
maximize v x subject to A x b A R m × n
(i.e. trying to solve an optimization problem in n variables with m linear inequality constraints).
This problem can be reduced to running a solution finding algorithm on a different system of linear equations in k variables. What is the smallest value of k for which this can be done.
asked 2022-06-15
Let a , b , c be whole numbers so that
1 a 3
2 b 4
3 c 5
Find number of solutions of the equation, a + b + c = 10. Note: Please use FPC/PnC to answer this instead of the binomial theorem

New questions