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

glutynowy44

glutynowy44

Answered question

2022-07-01

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?

Answer & Explanation

Monserrat Cole

Monserrat Cole

Beginner2022-07-02Added 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.
Holetaug

Holetaug

Beginner2022-07-03Added 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

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?