1
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$ Commented Apr 29 at 8:42
  • $\begingroup$ @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. $\endgroup$ Commented Apr 29 at 9:48
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Apr 29 at 10:20
  • $\begingroup$ @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. $\endgroup$ Commented Apr 29 at 14:04
  • $\begingroup$ You can call them floating point numbers. This is both mathematically accurate and understandable by programmers. $\endgroup$ Commented Apr 29 at 14:24

2 Answers 2

2
$\begingroup$

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)})$.

$\endgroup$
1
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Commented Apr 28 at 4:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.