linear inequalities using LP solutions not from simplex

Question

I am trying to solve a set of inequalities using linear programming (LP) with objective function set as a constant. Usually this set of inequalities would have many solutions, all of them in the feasible region.

However, the library I am using (python pulp) gives solutions from the simplex, which sometimes make my variables vanish (sets some of the variables to zero). Since my objective function is constant, I would like to receive a random solution from the feasible region, and not just from the simplex. How can I do that?

Is there any constraint to ensure that I get a solution from the internal feasible region - not just simplex? (Can pulp can do it? Can any other python lib?)

Thanks!

Answer 1

I don't know which solver are hooked to Pulp, but a first try would be running an interior-point based algorithm. This will give you a solution in the interior of the feasible set. Actually you won't get a random solution, unless the algorithm implementation is not completely deterministic. To overcome this, why not just randomly generate a random set of costs for the variables?

Answer 2

See "A version of the simplex method for solving linear systems of inequalities and linear programming problems" Evald Übi