Is there a linear programming method that is polynomial in the number of variables, constraints and bitlength of numbers?

Question

AFAIK, Interior Point method for solving a system of linear inequations is polynomial in the number of variables and constraints. Probably there are others. I don't need to optimize any function (neither maximize, not even minimize), but I need a solution to the system of inequalities from the Linear Programming method that is polynomial in the number of variables, constraints and the bitlength of the real numbers that it operates on. Here's why it's needed: https://algoextreme.com/2024/04/27/pnp-a-reduction-of-bsat-problem-to-linear-programming-and-long-arithmetic/

Can you suggest any such algorithm, or if it's the Interior Point method, confirm it's not exponential in the bitlength of the real numbers it operates?

• Emil Jeřábek: There is no such thing as "bitlength of real numbers". Real numbers cannot be represented by finite bitstrings. Bitlength makes only sense for integers or rationals.
• Serge Rogatch: @EmilJeřábek every programmer knows that everything in a computer has bitlength. Real numbers are currently approximated with fixed-point or floating-point data types of L bits, every programmer knows most often L=32 (single precision) or 64 (double precision). And when you aim to understand rather than criticize, it's easy to realize what I meant by bitlength of real numbers. Otherwise, if you are more mathematician than programmer, I have to disappoint you that there is no infinity - you just imagine it the way you imagine complex numbers. No offense, find me in messengers and we can talk.
• Emil Jeřábek: Floating point numbers are a particular set of rational numbers. My intention is not to criticize, but to help you use standard terminology in the question.
• Serge Rogatch: @EmilJeřábek, thanks, you are right that to speak exactly mathematically we need to call them so, but then programmers won't understand the article, unfortunately, because many programming languages even have "REAL" data type, while what's meant indeed is what you said - a set of rational numbers.
• Emil Jeřábek: You can call them floating point numbers. This is both mathematically accurate and understandable by programmers.

Answer 1

Interior-point methods such as Khachiyan’s and Karmarkar’s are, indeed, polynomial in the size of the input, i.e., in the number of variables, constraints, and the bitlength of the coeficients. This is why they were such a breakthrough when they were discovered. E.g., as noted in the linked article, if there are $n$ variables, $m$ constraints, and the total bitlength of the coefficients (say, integer or rational) is $l$, then Karmarkar’s algorithm takes $O(n^2m^{1.5}l)$ operations on $O(l)$-bit numbers, thus with total running time $O(n^2m^{1.5}l^2(\log l)^{O(1)})$.

• Serge Rogatch: Then the next question is: cstheory.stackexchange.com/questions/54250/…

Answer 2

One possible way is to write a dummy objective function, such as $$maximize: \sum x_i$$ and let any good LP solver take care of the rest. The same is also suggested here.

• D.W.: But is this polynomial in the number of variables, constraints and the bitlength of the real numbers that it operates on? I don't see any reason to believe it would be, for the solvers I am aware of. This answer seems to miss the point of the question.